28
\$\begingroup\$

I'm learning C++, so I decided to make a simpler clone of std::vector.

Concerns:

  • I have seen people defining methods outside of the class, and only prototyping them inside the class. Should I be doing this too?
  • I'm new to lower-level languages that require memory management, so there might be leaks.
  • Are there any performance optimizations I could make?
  • Is my general style good?

My code:

#include <iostream>
#include <algorithm>

template <class element>
class Vector {
  private:
  int len, cap;
  element* arr;

  void allocate_to_len() {
    int new_cap = min(cap, 1); // size-0 vectors wont loop infinitely
    while (len > new_cap) {
      new_cap *= 2;
    }
    resize(new_cap);
  }

  public:
  Vector() : Vector(10) {}

  Vector(int size) {
    len = 0;
    cap = size;
    arr = new element[size];
  }

  Vector(const Vector<element>& v) {
    len = v.length();
    cap = v.capac();
    arr = new element[cap];
    for (int i = 0; i < len; i++) {
      arr[i] = v.get_value(i);
    }
  }

  ~Vector() {
    delete[] arr;
  }

  element& operator[](int index) {
    if (index < 0 || index >= len) {
      throw "Index out of range";
    }
    return arr[index];
  }

  int length() const {
    return len;
  }

  int capac() const {
    return cap;
  }

  element get_value(int index) const {
    if (index < 0 || index >= len) {
      throw "Index out of range";
    }
    return arr[index];
  }

  void resize(int size) {
    cap = size;
    element* newarr = new element[size];
    len = std::min(len, cap);
    for (int i=0; i < len; i++) {
      newarr[i] = arr[i];
    }
    arr = newarr;
  }

  void append(element item) {
    len += 1;
    allocate_to_len();
    arr[len - 1] = item;
  }

  void extend(Vector<element> d) {
    int length = d.length();
    int old_len = len;
    len += length;
    allocate_to_len();
    for (int i=0; i < length; i++) {
      arr[i + old_len] = d[i];
    }
  }
};

int main() {
  // Tests:

  Vector<int> d;

  d.append(1);
  d.append(2);
  d.append(3);

  for (int i=0; i<d.length(); i++) {
    std::cout << d[i] << "\n";
  }
  std::cout << "\n";

  Vector<int> d2;

  d2.append(4);
  d2.append(5);
  d2.append(6);

  d.extend(d2);

  for (int i = 0; i < d.length(); i++) {
    std::cout << d[i] << "\n";
  }
  std::cout << "\n";

  d.resize(4);

  for (int i = 0; i < d.length(); i++) {
    std::cout << d[i] << "\n";
  }
}
\$\endgroup\$
14
\$\begingroup\$

First of all, lets answer the questions you have:

  1. Yes, no, maybe. Some people do it one way, some the other. Personally, I prefer splitting declarations and definitions up so that I have an overview of what my class offers at the top. Some people argue, however, that this method tends to be very verbose (and it can be, especially with multi-layer templates), so either way is fine.
  2. Yes, there is at least one memory leak in resize(). This is evident by the fact that you're allocating memory there, but not freeing the old memory. After the method returns, the internal pointer points to the newly allocated array while the old one is left abandoned and unreachable in the depths of the heap. To correct this, just delete[] the old array before you assign arr = newarr.
  3. Probably, but I don't want to go into those here as
    • you do not seem to have measured any performance characteristics of the code, and as long as you don't benchmark you don't care about performance
    • this implies that you don't actually care too much about performance (if you did, you would have measured it) and
    • your code does not have anything that screams "I'm going to be really slow" at me, so there's little reason to optimize anyway.
  4. Depends on what you mean by "general style". If you mean correct indentation, variable names etc. I'd say yes. If you mean use of the STL and standard algorithms, I'd say there's still work to do.

Taking a closer Look

You did not ask for this kind of review, so if you're not interested, feel free to simply ignore this part of the answer.

While your overall code makes a pretty good impression on me, there are some things that don't look and feel right and, to my mind, deserve another thought or two:

  1. While you say that your container is a simple clone of std::vector, its behavior differs gravely from the standard container when it comes to allocating and managing elements. The issue is that your container cannot reserve any memory without (default -) constructing elements. However, if you take a look at std::vector, you will find that it offers a reserve interface that lets you allocate memory in advance without actually constructing any elements. This kind of behavior is a little more difficult to realize in code, though, so you might want to stick with your current version if you're still in the process of getting a good hold of C++, especially if you don't feel safe working with low-level memory routines.
  2. Although I tend to iterate on this point again and again, int is not the right type for index and iteration variables. First of all, it is a signed type, which allows it to take negative values (a fact which your dereference methods brace against). Secondly, on a modern x86_64 system (which happens to be what most desktop users are running), int is likely to only be a 32bit data type, which means that you are limiting yourself to about 4 gigabytes of memory for your vector, and running into the risks of overflows with high indices. Instead, C++ offers the type std::size_t, which lends itself very well to size- and index-variables, as the name suggests. It is unsigned, and, on a typical 64bit platform, is usually 64 bits in size.
  3. It's a bad practice to force exceptions on users. One reason for this is that exceptions are really slow when they happen. Another reason is that exceptions are not readily available on all systems, especially not in the embedded development sector. My suggestion for you is to kind of follow the std::vector design pattern: Make operator[] unchecked and have undefined behavior on out-of-bounds access, and provide a at() method which does bounds checking and throws on out-of-bounds. This may also lead to increased performance, as the index validation can no be avoided if the index is known to be in bounds.
  4. As I already mentioned in the answer to question four, there is some potential to use standard algorithms, in particular std::copy and std::move in places where you are copying/moving data from one array to another. In general, if you have a simple for loop over a range of elements that does nothing too complicated in its body, it is possible to replace the loop with a function call to something from algorithm or numeric.
  5. Avoid magic numbers. For example, in Vector() : Vector(10) {}, what does the 10 mean? Why 10? Every time you find yourself writing a magic number, refactor it to a constant and give it a name. In this case, vector_default_size or something of the sort would be fitting.
  6. Although this might partly be because this is a code review question, the interface your class offers is kind of meager. What I find especially lacking is support for iterators, i.e. begin() and end(). In the case of your vector, those would not be hard to implement at all, since every raw pointer automatically meets the requirements for a RandomAccessIterator.
  7. Speaking of raw pointers, the way your class is currently implemented it lends itself very well to the use of std::unique_ptr. This will have the added benefit that you don't really need to worry about move constructor and destructor any more, because those will be automatically be taken care of by the unique pointer. In general, you should try to avoid raw pointers as much as possible, since they have no ownership semantics and are prone to mbe misused.

Parts of this answer were written before Martin York posted his answer. Thus, there may be some points which overlap. If you find any of those points appealing, please give the credit to Martin York as he was faster than me.

\$\endgroup\$
  • 1
    \$\begingroup\$ Point 2: I completely disagree with the int is not the right type for index and iteration variables. I think int is the better data type exactly because it can be negative. The trouble with unsigned types they auto convert negative values without so much as a hickup (and you end up with a very large positive value usally). By allowing negative values you can actually check for them and spot errors more easily. \$\endgroup\$ – Martin York Feb 13 '18 at 0:50
  • \$\begingroup\$ Point 7: I disagree but not that much. I think smart pointers and containers are trying to achieve the same thing. Though i can see the argument for using a smart pointer as it simplifies the container, and this will work for very simple containers, but I believe that when you get down into the details of implementing the container those advantages disappear as the container is managing the memory for the container and all the elements in it. \$\endgroup\$ – Martin York Feb 13 '18 at 0:57
  • \$\begingroup\$ Your answer is much more elegant and refined than mine. Thats why I was able to hammer out a response quickly. \$\endgroup\$ – Martin York Feb 13 '18 at 1:20
  • 2
    \$\begingroup\$ @MartinYork Thanks for the praise! To address your points: Point 2: I guess there's two sides to the medal here. Even so, I don't think int is the right choice for indices and sizes because of its size limitations. If you prefer signed variables, std::ptrdiff_t would probably be the best choice, no? Point 7: In general, I agree with what you're saying. Maybe I didn't express this clearly enough, but I meant that the current, very simple container implementation would lend itself well to smart pointer usage since it's basically just managing a dynamic-size array. \$\endgroup\$ – Ben Steffan Feb 13 '18 at 8:30
  • \$\begingroup\$ Point 4: Unfortunately, there is no equivalent to std::move_if_noexcept in ranges terms, which is really annoying. Managing yourself the set of conditions is asking for troubles. \$\endgroup\$ – Matthieu M. Feb 13 '18 at 15:30
30
\$\begingroup\$

Issues

Your vector assumes that the type being stored has a default constructor.

arr = new element[size];

Also this is really inefficient for expensive to create classes where you don't use all the size members. You want to design your class so that the objects in the vector are only constructed when the element is first added.

Bug

You don't implement the rule of three.

By default the compiler creates three methods for you. Copy Constructor/Copy Assignment/Destructor. You have not implemented the Copy Assignment operator. This means you will have a bug (because of the shallow copy issue) if there is an assignment.

Design Issue

Return values by reference:

element get_value(int index) const;

Here you return a copy of the element. This may be very expensive. So it would be nice if you return by reference (in this case const reference). This way you can read the data without actually making a copy of the data first.

Design Issue

There is no point in checking index ranges when you can guarantee that the index is in bounds. You should design your class to allow expert users unfettered access (ie no checks) but also provided a checked interface for people still testing and using unvalidated input.

element& operator[](int index) {
  if (index < 0 || index >= len) {
    throw "Index out of range";
  }
  return arr[index];
}

This is the design used by std::vector.

T& std::vector::operator[](index);   // Does not check index
T& std::vector::at(index);           // Does check that index is valid

So in the case:

for(int loop = 0; loop < v.length(); ++loop) {
    std::cout << v[loop];
}

In this very standard situation I know that loop is always within the bounds. So doing a check on the bounds is not required. This is exactly why std::vector<> has two interfaces for accessing elements.

Const Issues

A lot of interfaces pass object by const reference. This allows you to pass an object without copying it and without giving write access to the object (this is called const correctness).

As a result a lot of the accesses interfaces also have a const version.

T const& std::vector::operator[](index) const;   // Does not check index
T const& std::vector::at(index)         const;   // Does check that index is valid

Memory Leak

  void resize(int size) {
    cap = size;
    element* newarr = new element[size];
    len = std::min(len, cap);
    for (int i=0; i < len; i++) {
      newarr[i] = arr[i];
    }

Fix Here

    // before you can overwrite `arr`
    // You need to deallocate the array and all its members.
    std::swap(arr, newarr);  // So swap the values.
    delete [] newarr;        // Now you can delete the old array.
  }

Notes

I wrote a series of articles about writing a vector.

Vector - Resource Management
Vector - Copy and Swap
Vector - Resize
Vector - Simple Optimization
Vector - The other stuff

\$\endgroup\$
  • 3
    \$\begingroup\$ Regarding bounds-checking: I do like using assert in operator[], to help catch mistakes earlier... \$\endgroup\$ – Matthieu M. Feb 13 '18 at 14:15
  • 2
    \$\begingroup\$ "doing a check in the interface is gratuitously expensive". So how much do you figure the performance overhead is going to be in standard use cases? 20%? 15%? Or maybe more 0.1% if at all? And at what level of performance overhead is introducing security and correctness problems worth it? \$\endgroup\$ – Voo Feb 13 '18 at 14:20
  • 1
    \$\begingroup\$ @voo If we look t the standard implementation of vector (std::vecter). You will see there are two interfaces. A checked interface and an unchecked interface. The reason for the difference is we don't want to restrict choice. For those that have done the appropriate validation we want to provide the optimal code, for those that that need to have runtime validation there is that option. Doing a quick test. gist.github.com/anonymous/03af79051d59bf3dce3ca366c1d66493 I see a difference in 0.35% (obviously simplistic test). \$\endgroup\$ – Martin York Feb 13 '18 at 16:18
  • 1
    \$\begingroup\$ @Nik-Lz: 1) NRVO reduces the number of copies to one but it does not eliminate them. Returning by const reference eliminates all copies. For a container why have a copy at all if you don't need it. \$\endgroup\$ – Martin York Oct 22 '18 at 10:20
  • 1
    \$\begingroup\$ @Nik-Lz 2 2) Sure you can make assumptions. But there is no need to make this one. Do I have to have a default (zero argument constructor) constructor to put things in std::vector. Why would your limit your class that way if you don't need to. \$\endgroup\$ – Martin York Oct 22 '18 at 10:23
5
\$\begingroup\$

I have not seen the other answers talk enough about how you manage vector sizes.

Design Issue

You are declaring int len, cap; but at least you are using int consistently. This would normally be using size_t. (see Ben Steffan's answer point 2)

Implementation bug

allocate_to_len has a bug. Specifically, if len > INT_MAX / 2, you are overflowing cap which leads to undefined behaviour for int and overflow for size_t. The standard implementation of vector offers a method max_size that returns the largest implementation defined capacity. Reserving or increasing the vector beyond that size throws a length_error.

Similarly, in append you might overflow len.

Naming

capac should be called capacity. get_value is at. length is size. append is called push_back in C++. This leads me to my last point.

Adhere to the container concept

If you want your vector to be reusable in other contexts, you should adhere to the container concept. This would allow other libraries, e.g. <algorithm> to use your container.

Part of this would be to change void extend(Vector<element> d) (note also that you should be taking this argument by const reference) to template <class InputIterator> void insert (iterator position, InputIterator first, InputIterator last); aswell as implementing an iterator for your container.

\$\endgroup\$
  • 1
    \$\begingroup\$ As mentioned in the comments to the other answer, signed types are fine here, and are in fact the consensus of the committee nowadays. They concede that using unsigned types were a mistake, and, going forward, the standard will probably include a signed type std::index_t for indices and sizes. \$\endgroup\$ – Konrad Rudolph Feb 13 '18 at 12:35
5
\$\begingroup\$

Just wanted to point out 2 more things that I saw that don't seem to have been mentioned yet.

Append Resizes the Vector Every Time

I see that you differentiate capacity and length. The general idea behind this is that the vector will always have some spare room to grow into without having to reallocate memory, copy elements, and de-allocate memory every single time. Within the append method you call allocate_to_len() regardless of whether or not more memory is needed. You should only call allocate_to_len() when, after incrementing len, len >= cap

i.e.

void append(...) {
    len += 1;
    if (len >= cap)
        allocate_to_len();
    ...
}

Capacity Computation Loop is Unnecessary

When computing the new capacity, you double the current capacity until it is greater than the current length. If you follow my above suggestion, then the capacity is guaranteed to be at least the length, if not larger. Doubling it once is enough, so the loop can be removed. Furthermore, you can also simply compute the new capacity as double the length. I believe this is the standard allocation behavior of std::vector

cap = len*2;

Is enough, barring ensuring that you haven't exceeded the maximum length as pointed out by another answer.

Overall great job! I'm just nitpicking. Rewriting standard containers and algorithms is incredibly helpful and something I did as well when I was first learning.

\$\endgroup\$
5
\$\begingroup\$

Exception Safety

Your container is not exception safe.

The first difficulty of writing a container in C++ is handling the memory when everything goes well. Other answers already address this point so I won't reiterate it.

The second difficulty of writing a container in C++ is handling the memory when the user is being adversarial. It is possible, in C++, to throw an exception:

  • in a default constructor,
  • in a copy constructor,
  • in a copy assignment operator,
  • in a move constructor,
  • in a move assignment operator,
  • in a destructor...

Any time you invoke user logic, it may throw.

You have to decide how to handle this behavior:

  • Not accounting for exceptions is not an option, you can cop out by tagging your methods noexcept1 though your users may not appreciate,
  • At the very least, you should NOT leak (Basic Exception Guarantee); if you are using new/delete memory handling, you are more likely to fail this,
  • You should always attempt to provide the Strong Exception Guarantee, which means that if the user-defined operation throws your container is left unmodified.

Note that the Strong Exception Guarantee would sometimes require expensive operations (copy and swap). In this case, it is better to stick to the Basic Exception Guarantee and document the behavior.

1 If an exception attempts to "leave" a noexcept method, the program terminates abruptly. It's better than corrupting memory, but still very annoying.


With that in mind, please consider the following start:

template <typename T>
class Vector {
public:
    Vector() = default;

    //  WARNING:
    //  The COPY CONSTRUCTOR, COPY ASSIGNMENT OPERATOR and DESTRUCTOR
    //  are missing and should be defined. Correctly.

    void push_back(T&& e);
    void push_back(T const& e);

private:
    using Raw = typename std::aligned_storage<sizeof(T), alignof(T)>::type;

    void grow_by(std::ptrdiff_t n);

    T* raw();

    std::ptrdiff_t mCapacity = 0;
    std::ptrdiff_t mLength = 0;
    std::unique_ptr<Raw[]> mStorage;
};


template <typename T>
void Vector<T>::push_back(T&& e) {
    this->grow_by(1);

    new (this->raw() + mLength) T{std::move(e)};
    ++mLength;
}

template <typename T>
void Vector<T>::push_back(T const& e) {
    this->grow_by(1);

    new (this->raw() + mLength) T{e};
    ++mLength;
}

template <typename T>
void Vector<T>::grow_by(std::ptrdiff_t n) {
    if (mLength + n <= mCapacity) { return; }

    //  Prepare new storage
    auto newCapacity = std::max(mCapacity, 1);
    do {
        newCapacity *= 2;
    } while (mLength + n > newCapacity);

    Vector next;
    next.mCapacity = newCapacity;
    next.mStorage.reset(new Raw[newCapacity]);

    //  Transfer objects:
    //  1. if T's move constructor is noexcept, use it!
    //  2. otherwise, if T has a copy constructor, use it!
    //  3. otherwise, use T's move constructor.
    //
    //  Cases 1 and 2 offer the Strong Exception Guarantee; case 3
    //  unfortunately offers only the Basic Exception Guarantee.
    for (auto& t : *this) {
        next.push_back(std::move_if_noexcept(t));
    }

    //  "Commit" the change.
    std::swap(*this, next);
}

template <typename T>
T* Vector<T>::raw() { return reinterpret_cast<T*>(mStorage.get()); }

There are two std features of note here:

  1. The use of std::aligned_storage<>::type gives us raw storage of suitable size and alignment: this obviates the need for default constructors of T!
  2. The use of std::move_if_noexcept allows us to offer the best possible Exception Guarantee with little code.

Also, note how both grow_by and push_back are organized to provide the Strong Exception Guarantee (when possible):

  1. Do the operations that may throw without modifying the object,
  2. Commit the work.

In the case of push_back, you can see the length is only incremented if construction of the object is successful, for example.

In the case of grow_by, note how it reuses the current Vector class to handle the destruction of already copied/moved elements if an exception is thrown in the loop.


I will not lie, exception safety can be hard in vectors.

Inserting a range of elements in the middle of the vector is a nightmare when the move constructor/move assignment operator may throw.

\$\endgroup\$
  • \$\begingroup\$ I would change: At best, you should provide to You should always attempt to provide (when acceptable), \$\endgroup\$ – Martin York Feb 14 '18 at 17:07
  • \$\begingroup\$ Careful of overflow here: newCapacity *= 2;. This seems like a bug mLength + n > newCapacity \$\endgroup\$ – Martin York Feb 14 '18 at 17:14
  • \$\begingroup\$ @MartinYork: There is indeed a risk of overflow, I'd rather not deal with it right here though as it is not the purpose of the sample. In a complete solution, I would advise against using the loop anyway; it's not bad (O(log N)), but there are more efficient ways of finding the next bigger power of 2 with intrinsics (__builtin_clz gives you a leg up). \$\endgroup\$ – Matthieu M. Feb 14 '18 at 18:22
  • \$\begingroup\$ @MartinYork: I think mLength + n > newCapacity is right, any particular concern? \$\endgroup\$ – Matthieu M. Feb 14 '18 at 18:29

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.