How is vector implemented in C++

by

it is a simple templated class which wraps a native array. It does not use malloc/realloc. Instead, it uses the passed allocator (which by default is std::allocator).

Resizing is done by allocating a new array and copy constructing each element in the new array from the old one (this way it is safe for non-POD objects). To avoid frequent allocations, often they follow a non-linear growth pattern.

UPDATE: in C++11, the elements will be moved instead of copy constructed if it is possible for the stored type.

In addition to this, it will need to store the current “size” and “capacity”. Size is how many elements are actually in the vector. Capacity is how many could be in the vector.

So as a starting point a vector will need to look somewhat like this:

template <class T, class A = std::allocator<T> >
class vector {
public:
    // public member functions
private:
    T*                    data_;
    typename A::size_type capacity_;
    typename A::size_type size_;
    A                     allocator_;
};

The other common implementation is to store pointers to the different parts of the array. This cheapens the cost of end() (which no longer needs an addition) ever so slightly at the expense of a marginally more expensive size() call (which now needs a subtraction). In which case it could look like this:

template <class T, class A = std::allocator<T> >
class vector {
public:
    // public member functions
private:
    T* data_;         // points to first element
    T* end_capacity_; // points to one past internal storage
    T* end_;          // points to one past last element
    A  allocator_;
};

I believe gcc’s libstdc++ uses the latter approach, but both approaches are equally valid and conforming.

NOTE: This is ignoring a common optimization where the empty base class optimization is used for the allocator. I think that is a quality of implementation detail, and not a matter of correctness.

More Related Contents:

  1. How do I compare chars (or strings) using void functions, also comparing chars that were taken from a struct array
  2. How to get the maximum number after erasing n digits from the number [closed]
  3. Visual C++ equivalent of GCC’s __attribute__ ((__packed__))
  4. What does C++ struct syntax “a : b” mean
  5. Why does the C++ STL not provide any “tree” containers?
  6. Looking for C++ STL-like vector class but using stack storage
  7. Vectors, structs and std::find
  8. iterate vector, remove certain items as I go
  9. Is there a way to access the underlying container of STL container adaptors?
  10. Trie implementation [closed]
  11. Relative performance of std::vector vs. std::list vs. std::slist?
  12. A proper way to create a matrix in c++
  13. How to store extremely large numbers?
  14. what is the difference between set and unordered_set in C++?
  15. what is “stack alignment”?
  16. Efficiency of the STL priority_queue
  17. adding list items or nodes in linked list
  18. Passing array of structures to function c++
  19. Does a standard implementation of a Circular List exist for C++?
  20. TMP: how to generalize a Cartesian Product of Vectors?
  21. Why would anyone use set instead of unordered_set?
  22. Easiest way of using min priority queue with key update in C++
  23. How to clone object in C++ ? Or Is there another solution?
  24. Why can’t I use a “break” statement inside a ternary conditional statement in C++?
  25. Data structure padding
  26. Why does using push_back on a vector declared with size result in a vector of zeros?
  27. Calling erase with iterator vs const_iterator
  28. What should the ‘pop()’ method return when the stack is empty? [duplicate]
  29. C++ Class or Struct compatiblity with C struct
  30. Order Statistic Tree in C++

Leave a Comment