Vector class

[ResidentBiscuit]

Made my own vector. Go judge the hell out of it:
https://sourceforge.net/projects/datastructs/

[Lachlan Easton]

Line 37, is capacity meant to be _capacity? capacity is a member function not an int. Also I think it should fail to make a vector if a negative initial size is passed in (possibly throw an exception?) though I don't remember what the standard vector would do. I'd also look into the C function realloc instead of looping through twice in order to move the vector.

[naraku9333]

Reallocate is pretty inefficient, you copy the vector resize then copy again. Just create the temp with the new size, copy the data delete the old array and set data pointer to temp.

Edit: typos on lines 52 and 148 (missing under scores)

[ResidentBiscuit]

Missing underscores I'm sure are there. I changed the naming of some internal members and had to go and change all of them. Was watching TV during that and figured I'd miss some. I wasn't sure if I wanted to add bounds checking and sanity checks to this class, or leave it up the theoretical "user" (application programmer) to deal with that. What are your thoughts?

@naraku,
You know when I wrote this I was thinking I was doing too much, but wasn't sure why. It's so obvious now.

[Lachlan Easton]

You could put bounds checking etc. omitted from release using #ifdef DEBUG

[ResidentBiscuit]

Trying to get around copying data twice, I came to this. Though I'm pretty certain this leads to memory leaking a fair amount.

template <typename T>
void MyVector<T>::reallocate()
{
    _capacity = _capacity * 2;
    T* temp = new T[_capacity];
    for(int i = 0; i < _size; i++)
    {
        temp[i] = data[i];
    }
    delete[] data;
    data = 0;
    data = temp;

    std::cout << "Reallocation successful.\n";
}

The other way I tried (and failed) was deleting temp at the end of all this. Obviously that led to bad.

[naraku9333]

I see no memory leak.

[ResidentBiscuit]

Will temp not leak?

[chrisname]

No because data is being reassigned to point to the memory that temp points to. Since they both point to the same memory location to deallocate one is to deallocate both, so as long as you deallocate data in your destructor, it will deallocate the memory that temp pointed to. Also, there's no need to assign 0 to data before pointing it to temp. If you assign a value to a variable twice in a row, only the second assignment "counts".

[ResidentBiscuit]

Ooh duh that makes sense. Thanks for the explanation!

I just got into the habit of assigning 0 after deletion awhile ago. I guess it's not really needed here

[chrisname]

Change it into a habit of assigning _something_ after deletion, that way assigning temp to data will count towards your habit.

[ne555]

Classes need a default constructor in order to be used with your container.
Try to fix that

[ResidentBiscuit]

@chris,

I believe I'll start doing this :)

@ne555,

Interesting, I'd never even thought of that issue. But now I'm pretty stumped on how to fix that

[cire]

http://stackoverflow.com/questions/222557/what-uses-are-there-for-placement-new

[naraku9333]

Interesting, I'd never even thought of that issue. But now I'm pretty stumped on how to fix that

Maybe use malloc to allocate the capacity. I went ahead and did it myself (with your code), don't look if you want to do it yourself. http://ideone.com/BSgoCK

Edit: Using placement new as cire suggested is likely a better idea, especially since my experience with malloc is extremely limited so I may have missed something critical.

[helios]

Classes need a default constructor in order to be used with your container.

"Fixing" this would involve either:
a) some way of passing the constructor parameters to resize() in a generic manner (perhaps by way of boost::bind?), or
b) not guaranteeing that new elements added by a resize() operation are constructed.
I think requiring a default constructor isn't such a big restriction.

[zb0S216C]

ResidentBiscuit wrote:

"Go judge the hell out of it"

With pleasure :)

General Programming Practices and Design Choices

1) In "MyVector::MyVector( )" and "MyVector::MyVector( int capacity )", you're doing something wrong: you're setting the capacity before allocating the memory for the vector, but what happens when the allocation fails? You're going to be left with misleading information, specifically, "_capacity" will have a valid value but no corresponding memory as "MyVector::data" will be null. It would be best to set the capacity upon allocation success.

2) Again, just like the above point, "MyVector::reallocate( )" suffers the same issue.

3) In function "MyVector::get( )", you're not validating "index"; whether this was intended I don't know because of the lack of documentation. Also, why not make "index" constant? You seem to qualify "index" of "MyVector::operator []( )" with "const".

4) The constant "MyVector::operator []( )" is useless. If a "MyVector" was declared constant, you wouldn't be able to add or remove any elements anyway. Therefore, the state of the object wouldn't change so there would be no need to access the elements because they'd never change anyway.

5) In regards to "MyVector::capacity( )", two things are on my mind: why is the function non-constant? and why are you not ensuring that the capacity is valid? As I said in the first point, if an allocation fails, there's no memory and therefore is no capacity. This misleading information can lead to devastating situations.

6) In function "MyVector::empty( )", a simple equality check would fit nicely -- the amount of "if" statements is too excessive.

Efficiency: My Favourite Field

1) There's no explicit in-lining. Some of the function implementations are good candidates for in-lining, but you fail to even reference in-lining.

2) Your method of memory allocation is interesting given the design. "::new T[n]" allocates a group of contiguous objects and then constructs each one if the allocation succeeds. However, because you're implementing a container, this isn't exactly a smart choice for one reason:

"T" may well be a constant type. In order for your implementation to work, "T" must be copy-assignable. With your allocation method, all constant objects would've been constructed at the point of allocation and any future modifications to the elements after that point would be in violation of the "const" qualifier. Oops!

3) Allocating memory is a time-consuming process. Because your initial capacity is so low, given the usage, re-allocations would be a frequent occurrence, thereby reducing the overall speed of the vector. I would suggest upping the value, but the implementation is too general to give a suitable suggestion.

4) In function "MyVector::reallocate( )", there's room for optimisation: the loop's body. A faster approach would be using pointers and to avoid using "X[n + 1]".

5) If "T" was a scalar type, you'd be losing some performance due to passing-by-reference. Passing scalar types by reference decreases performance. There's no attempt to rectify this issue.

6) Back in "MyVector::empty( )" swapping the body with a single equality check will reduce the amount of branch predictions.

[Edit]To all who suggest the use of "std::malloc( )":
If you're going to suggest the use of "std::malloc( )", please make sure that you mention the possibility that "std::malloc( )" will return a misaligned pointer and that it needs to be addressed. Also, please prefer the "new" alternative instead:

void *Raw_Memory_( ::operator new( 30 * sizeof( double ) ) );
::operator delete( Raw_Memory_ );

_Wazzak

[Catfish3]

Minor style issue: since this is a template class, you might as well have defined the member functions inside the class body.

No use "fixing" it now, after the work is already done, but for future projects it will spare you a fair amount of typing.

And another minor style issue, you should end names with underscores, not begin them (i.e. capacity_ instead of _capacity).
http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier

Also what's the use for the else branch in the code below?
I almost never put curly braces around single statements, except if the compiler warns about it, which happens in GCC for

if() if() else

and I end up with:

if() { if() else }

1 2 3 4 5 6 7 8 9 10 11 12

template <typename T> bool MyVector<T>::empty() { if(size > 0) { return false; } else { return true; } }

template <typename T> bool MyVector<T>::empty() { if(size > 0) return false; return true; }

... which I'd rather write as:

template <typename T>
bool MyVector<T>::empty() const
{
    if (size == 0)
        return true;

    return false;
}

And Framework would take that further and write:

template <typename T>
bool MyVector<T>::empty() const
{
    return size == 0;
}

[coder777]

... which I'd rather write as:

Or even more simplified:

template <typename T>
bool MyVector<T>::empty() const
{
    return (size == 0);
}

Minor style issue: since this is a template class, you might as well have defined the member functions inside the class body.

The problem is that it will bloat the interface. An alternative is to put the implementation of the function in it's own file (that must not be touched by the compiler) and #include it at the end of the header

[cire]

Framework wrote:

1) In "MyVector::MyVector( )" and "MyVector::MyVector( int capacity )", you're doing something wrong: you're setting the capacity before allocating the memory for the vector, but what happens when the allocation fails? You're going to be left with misleading information, specifically, "_capacity" will have a valid value but no corresponding memory as "MyVector::data" will be null. It would be best to set the capacity upon allocation success.

When new fails, an exception is thrown. The object is never created.
It is a valid point for reallocate, though.

Framework wrote:

4) The constant "MyVector::operator []( )" is useless. If a "MyVector" was declared constant, you wouldn't be able to add or remove any elements anyway. Therefore, the state of the object wouldn't change so there would be no need to access the elements because they'd never change anyway.

Erm.. really? You never inspect elements of a constant object?