3
\$\begingroup\$

I've made my own std::vector but it's the first time that I work with template and new/delete. The code works, but surely there are a lot of things that are wrong. Can you read the code and say me if I have coded it the right way?

(main is a test.)

#ifndef __STDVECTOR__
#define __STDVECTOR__

#include <iostream>

using namespace std;

template <typename T>
    class StdVector{
        private:
            T *buffer;
            unsigned int capacity;
        public:
            //Constructor.
            StdVector(){
                capacity=0;
                buffer=new T[capacity];
            }
            //Copy constructor.
            StdVector(const StdVector &asv){
                int i;

                capacity=asv.getCapacity();
                buffer=new T[asv.getCapacity()];
                for (i=0; i<capacity; i++){
                    buffer[i]=asv[i];
                }
            }
            //Destructor.
            ~StdVector(){
                delete []buffer;
            }
            void push_back(T obj){
                StdVector oldSV(*this);
                int i;

                capacity++;
                delete []buffer;
                buffer=new T[capacity];
                for (i=0; i<oldSV.getCapacity(); i++){
                    buffer[i]=oldSV[i];
                }
                buffer[i]=obj;
            };
            T getBuffer() const{
                if (capacity==0){
                    throw exception();
                }
                return *buffer;
            };
            T &operator[](int index) const{
                if (index>=capacity){
                    //Out of range.
                    throw exception();
                }
                else{
                    return buffer[index];
                }
            }
            StdVector &operator=(const StdVector &obj){
                capacity=obj.getCapacity();
                delete []buffer;
                buffer=new T[capacity];
                buffer=obj.getBuffer();
                return *this;
            }
            unsigned int getCapacity() const{
                return capacity;
            };
    };

#endif

int main(){
    try{
        StdVector<int> test;
        StdVector<string> test2;
        unsigned int i;

        test.push_back(5);
        test.push_back(4);
        test.push_back(3);
        test.push_back(2);
        test.push_back(1);
        test.push_back(0);
        test.push_back(-1);
        test.push_back(-2);
        test.push_back(-3);
        test.push_back(-4);
        test.push_back(-5);
        for (i=0; i<test.getCapacity(); i++){
            cout << test[i] << endl;
        }
        test2.push_back("Hello");
        test2.push_back(" ");
        test2.push_back("World");
        test2.push_back(".");
        cout << "---------------" << endl;
        for (i=0; i<test2.getCapacity(); i++){
            cout << test2[i];
        }
        cout << endl;
    }
    catch(...){
        cout << "Exception." << endl;
    }
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Idk if it is just me, but calling your class StdVector seems kind of misleading. MyVector or Vector seems fine, but the Std prefix makes me think that it is part of the standard library. You are, however, trying to imitate it though... So maybe it does make sense to call it StdVector... \$\endgroup\$ – Dair Aug 10 '16 at 22:59
  • \$\begingroup\$ So... the code is it rigth??? The name don't care to me, i only want to know if the use of new/delete and if the code in general is rigth to imitate the std::vector. And thanks for your answer :) \$\endgroup\$ – Cristian García Aug 10 '16 at 23:08
  • \$\begingroup\$ You might want to use operator new instead of the new operator to allocate memory. That's because new T[n] will allocate memory + default construct each element in the array if T is of class type. \$\endgroup\$ – Blazo Aug 11 '16 at 2:16
  • \$\begingroup\$ I don't see anything obviously broken about this, so voting to leave open. \$\endgroup\$ – Dannnno Aug 11 '16 at 3:31
  • \$\begingroup\$ @Dannnno operator = doesn't compile. buffer=obj.getBuffer() assigns T to T*. \$\endgroup\$ – Emily L. Aug 11 '16 at 11:48
6
\$\begingroup\$

Don't use double underscore.

#ifndef __STDVECTOR__
#define __STDVECTOR__

Identifiers with double underscores are reserved for the implementation.
see: What are the rules about using an underscore in a C++ identifier?

Stop using

using namespace std;

This kind of thing can break so much code. Putting it in your header file will get you banned from open source projects as you corrupt the global namespace of any compilation unit that includes your header. Even in your own source files it is a bad idea as it potentially introduces hard to spot errors.
see: Why is “using namespace std” in C++ considered bad practice?

Don't build objects that have not been added.

Your current design is flawed.

    template <typename T>
    class StdVector{
            T *buffer;
            ...
                buffer=new T[capacity];

Because you only have one size value (a capacity) your code becomes tremendously inefficient (as we see when we get to push back).

You should have two sizes.

  1. The capacity: The amount of space allocated for objects in your vector.
  2. The size: The number of objects in the vector.

Without both these sizes they have to be the same value. This means you can not pre-allocate space and each time you add or remove elements you must resize the vector and this includes both allocating new space and copying all the elements into the newly allocated space

I go into a lot of detail in my article:
Vector - Resource Management Allocation

Prefer to use initializer list.

        StdVector(){
            capacity=0;
            buffer=new T[capacity];
        }

This is totally fine and works. But it is a bad habit. If you change the types of the members you are potentially making your class inefficient as the members are constructed before the body of the class is entered. You then modify them in the body.

        StdVector()
            : buffer(new T[capacity])
            , capacity(0)
        {}

Rule of three

Your assignment operator is way down in your code. I initially thought you were violating the rule of three. Put your assignment operator close to the constructors.

Assignment operator not exception safe.

This assignment operator is the classic first attempt.

            StdVector &operator=(const StdVector &obj){
                capacity=obj.getCapacity();
                delete []buffer;
                buffer=new T[capacity];
                buffer=obj.getBuffer();
                return *this;
            }

But it is prone to leaking and leaving the object in an inconsistent state if there are exceptions (in the constructor of T).

You should use the copy and swap idiom.

            StdVector &operator=(StdVector tmp) // notice the pass by value
            {                                   // this creates a copy.
                tmp.swap(*this);
                return *this;
            }
            void swap(StdVector& other) noexcept
            {
                using std::swap;
                swap(capacity,   other.capacity);
                swap(buffer,     other.buffer);
            }

I cover this in a lot of detail in:
Vector - Resource Management Copy Swap

Push back ineffecient

You are making a copy of the whole vector each time you add an element. But you are doing it twice to make even more inefficient that the original inefficiency imposed by your design.

            void push_back(T obj){
                StdVector oldSV(*this);
                int i;

                capacity++;
                delete []buffer;
                buffer=new T[capacity];
                for (i=0; i<oldSV.getCapacity(); i++){
                    buffer[i]=oldSV[i];
                }
                buffer[i]=obj;
            };

You can get rid of one copy like this:

            void push_back(T obj){    
                int newCapacity = capacity + 1;
                T*  newBuffer   = new T[newCapacity];

                for (int i = 0; i < capacity; ++i){
                    newBuffer[i]=capacity[i];
                }
                swap(capacity, newCapacity);
                swap(buffer,   newBuffer);
                delete [] newBuffer;
            };

Still not very good. But better than the original.

For Loops incrementing iterators.

  1. Prefer to declare the loop variable inline.
  2. Prefer to use prefix increment (not all iterators are as efficient as int).

Like this:

                for (int i = 0; i < capacity; ++i){
                    newBuffer[i]=capacity[i];
                }

Badly named method.

This does not get the buffer.

            T getBuffer() const{
                if (capacity==0){
                    throw exception();
                }
                return *buffer;
            };

It returns a copy of the first element in the vector.

Efficiency.

Normally in C++ the operator[] does unchecked access to the elements. Because there is no need to pay for the check in the method if the calling code already does the check.

             T &operator[](int index) const{
                if (index>=capacity){
                    //Out of range.
                    throw exception();
                }
                else{
                    return buffer[index];
                }
            }

To give us checked accesses we usually implement the function T& at(int index). This provides checked access to the vector for situations where the calling code does not check.

for(int loop = 0;loop < v.size(); ++loop)
{
    v[loop] = stuff(); // no need to check `loop` is in bounds.
                       // we know it is in bounds because of the context.
}

int index;
std::cin >> index;
std::cout << v.at(index) << "\n"; // here we want checked access.

I would write:

T& operator[](int index)  {return buffer[index];}
T& at(int index)          {checkIndex(index);return buffer[index];}

Const correctness

             T &operator[](int index) const

This function is not const correct. You promise not to mutate the object by marking the function as const but then return a reference that is not const thus allowing the object to be mutated.

 void bla(StdVector<int> const& data)
 {
     data[5] = 8; // You just mutated a const object.
 }

You should define two versions of this operator one for const and one for non const usage.

  T const&  operator[](int index) const;
  T&        operator[](int index);
\$\endgroup\$
  • \$\begingroup\$ Wow, this review has made me open my eyes, i make a lot of wrong practices, but it's ok, now i'll do better. Ty so much! \$\endgroup\$ – Cristian García Aug 11 '16 at 15:08
4
\$\begingroup\$
  • operator=

    Obviously, this part of the code has never been exercised. An attempt to use operator= fails to compile:

    error: invalid conversion from ‘int’ to ‘int*’ [-fpermissive]
             buffer=obj.getBuffer();
    

    and indeed getBuffer returns T.

    What's worse, operator= badly leaks memory:

            buffer=new T[capacity];
            buffer=obj.getBuffer();
    

    and whatever has been allocated with new is lost forever.

    What was probably intended is

            buffer = new T[capacity];
            std::copy(obj.buffer, obj.buffer + capacity, buffer);
    

    (same as you do in a copy constructor).

  • operator[]

    returns a non-const pointer, that is

    foo[x] = y;
    

    will compile even if foo is a const vector. To work correctly with const objects you need two flavors of a subscript operator:

    T& operator[](int);
    const T& operator[](int) const;
    

    BTW, an index argument shall be of size_t. Integers are not suited to express what index is. Along the same line, you throw exception() if the index is above capacity, but allow access with a negative index.

\$\endgroup\$
  • \$\begingroup\$ I'm really thankful! These tips have helped me a lot! \$\endgroup\$ – Cristian García Aug 11 '16 at 1:49
3
\$\begingroup\$

Use of new []

At least in my opinion, this provides a good demonstration of why the array form of new should normally be avoided.

The problem in this case is that when you allocate space with buffer = new T[capacity];, you not only allocate space but also create objects occupying all that space.

Then when you do (for example) a push_back, it doesn't create a new object as a copy of whatever you pass to push_back. Instead, it assigns the value of what you pass to push_back over the object that was already there.

This means, among other things, that all the objects you store in this collection must support default construction, rather than (for example) only copy construction or move construction like std::vector can support.

Support for iterators

You only support access to the contents of the collection by index, not by iterator. This means (among other things) that you can't use any of the standard algorithms with it. At least in my opinion, that's quite a serious handicap.

Exceptions

When you receive an out of range subscript, you throw an exception. That's a good idea. Unfortunately, you throw just about the most generic possible exception--std::exception. That doesn't tell a user much about what went wrong. I'd rather throw a more specific exception, and (especially) one that supports a description of the problem. In this case, it seems to me that it would make a lot more sense to throw an std::out_of_range exception:

    if (index>=capacity){
        throw out_of_range("Bad subscript");
    }

This pretty much eliminates any need for the out of range comment you had there as well.

getBuffer()

I'd almost rather eliminate this completely. Using a pointer to an object's internal state tends to be a problem. On the other hand, that is only a tendency, not an absolute certainty, so while I'd rather provide alternatives that render this unnecessary, removing it without providing alternatives may be premature.

operator []

Personally, I'd generally prefer to return a proxy in this case. The problem is that even with the overload suggested by @vnp, you can run into problems. What you'd normally like is that given some code like:

a[i] = b[i];

...that the left side use the non-const overload, and the right side use the const overload. That's not quite how things work though. Instead, what happens is that the overload that gets used is based solely on whether this is a T * or a T const *. As shown by std::vector, that works out well enough most of the time, but we can still do better.

With a proxy, we can overload operator T and operator= to get exactly the behavior we really want.

Buffer Growth Strategy

Right now, every single time you use push_back, you re-allocate the buffer and copy the entire old buffer to the new one. This means push_back has linear complexity on the number of items already in the collection. That, in turn, means that creating a collection of N items has a complexity of \$O(N^2)\$.

We can do quite a lot better than that. In fact, we can make each push_back (amortized) constant complexity, so creating a collection of N items has a (amortized) complexity of \$O(N)\$. To do that, the buffer growth needs to follow a geometric progression instead of an arithmetic progression--that is to say, instead of adding some fixed amount each time it needs to grow, we instead multiply the size by some fixed factor. There's room for argument over the truly optimum factor, but most real implementations use either 1.5 or 2 (personally, I tend to favor 1.5).

Note that this will require changing a few other parts as well. Right now, you're tracking the size of the buffer. With this change, you'll need to keep track of both the size of the buffer itself, and the number of items in that buffer that are currently in use. You only resize the buffer if push_back is called and the entire buffer is currently in use. When only part of the buffer is in use, you can create the new object in that empty space without reallocating or copying other objects.

\$\endgroup\$
  • \$\begingroup\$ Could you expand a little more on comments about operator[]? What I understood is that rhs should be logically const whenever possible? \$\endgroup\$ – Incomputable Aug 11 '16 at 9:48
1
\$\begingroup\$
#ifndef __STDVECTOR__
#define __STDVECTOR__

Avoid Leading/Double Underscores. From the C++ Standard:

17.6.4.3.2 Global names [global.names]

Certain sets of names and function signatures are always reserved to the implementation:

  • Each name that contains a double underscore __ or begins with an underscore followed by an uppercase letter is reserved to the implementation for any use.
  • Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace.

#include <iostream>

#include as little as possible and avoid #include <iostream> in library code. Most implementations will include static constructors into every translation unit whenever you #include <iostream>. Don't impose this cost on those that use your library. <iostream> is used your test code, so you should relocate #include <iostream> there.


unsigned int capacity;

Consider std::size_t instead of unsigned int. From the standard,

18.2 Types [support.types]

  1. The type size_t is an implementation-defined unsigned integer type that is large enough to contain the size in bytes of any object.

StdVector(){
    capacity=0;
    buffer=new T[capacity];
}

Spacing helps distinguish different language constructs. Consider adding spaces where appropriate (e.g. before the { and surrounding the =).

You should prefer member initialization lists instead of assignment in a constructor body. You'll get a performance increase from non-POD types, increased readability from the uniform initialization across all members (const/references require member initialization), and prevent common errors (e.g. use before set errors).


void push_back(T obj){
    StdVector oldSV(*this);
    int i;

    capacity++;
    delete []buffer;
    buffer=new T[capacity];
    for (i=0; i<oldSV.getCapacity(); i++){
        buffer[i]=oldSV[i];
    }
    buffer[i]=obj;
};

Consider what types of values can be passed into the function. While things like primitive types and small objects (2-3 words) are cheap to copy, not everything will be cheap. In the case of a templated type, you don't know the size of the object passed in. Pass the object by const-reference.

Don't introduce a variable until you actually need to use it. int i doesn't need to be declared at the top of the function and all you are doing is asking readers to track variables that aren't needed until later in the function. Declare it before the for loop.

Consider offering users the strong exception guarantee (should failure to append have side effects?). What happens if new throws some variation of the std::bad_array_new_length exception?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.