Std:: vector minutes

vector explain

template < class T, class Alloc = allocator<T> > class vector; // generic template

vector Is a sequence container that represents an array that can be resized .

It's like an array ,vector Use contiguous storage locations for their elements , This means that their elements can also be accessed using offsets on regular pointers to their elements , And the efficiency is the same as that of arrays . But unlike arrays , Their size can be changed dynamically , Its storage is handled automatically by the container .

vector Use dynamically allocated arrays internally to store its elements . When you insert a new element , You may need to reallocate the array to increase its size , This means allocating a new array and moving all elements to that array . In terms of processing time , This is a relatively expensive task , therefore , Every time you add an element to a container ,vector Will not be reassigned .

In its place , contrary , Vector containers can allocate some additional memory to accommodate possible growth , Therefore, the container can have a larger actual capacity than the strictly required memory to contain its elements （ namely , Its size ）. Libraries can implement different growth strategies , To balance memory usage and reallocation , But in any case , Reallocation should only occur at logarithmic growth intervals of size , So that the constant time complexity of allocation can be provided when inserting a single element at the end of the vector .

therefore , And arrays comparison ,vector Consume more memory in exchange for the ability to manage storage and dynamically grow in an efficient manner .

With other dynamic sequence containers （deques, lists and forward_lists） comparison , vector Can access its elements very effectively （ It's like an array ）, And relatively effectively add or remove elements from their ends . For operations involving inserting or deleting elements outside the end , Their performance is worse than other operations , And the consistency of iterators and references is worse than that of lists and forwarding lists .

vector A brief description of the structure

vector yes Typical Realization . vector It's just a data structure , It has a pointer , This pointer points to the stored in “ object ” Actual data in .

vector Follow these principles ：

template <typename Val> class vector
{
public:
  void push_back (const Val& val);
private:
  Val* mData;
}

The above is obviously pseudo code , But you know . When one vector On the stack （ Or pile ） The distribution of ：

vector<int> v;
v.push_back (42);

Memory may end up looking like this ：

+=======+        
| v     |
+=======+       +=======+
| mData | --->  |  42   |
+=======+       +=======+

When you push_back To a complete vector, The data will be redistributed ：

+=======+        
| v     |
+=======+       +=======+
| mData | --->  |  42   |
+=======+       +-------+
                |  43   |
                +-------+
                |  44   |
                +-------+
                |  45   |
                +=======+

And point to the new data vector The pointer to will now point here .

vector Layout introduction

Be careful ： std::allocator In fact, it is likely to be an empty Class, std::vector Instances of this class may not be included . For any allocator , Maybe not .

std :: vector Layout

In most implementations , It consists of three pointers , among

• begin Point to the pile vector The beginning of the data store of （ without , Is always on the heap ） nullptr)
• end Point to vector A storage location after the last element of data -> size() == end-begin
• capacity Point to vector A point on a memory location after the last element in memory -> capacity() == capacity-begin

On the stack Vector

We declare a variable of type std::vector<T,A> , T It's any kind of , A Is the allocator type T (i.e. std::allocator<T>).

std::vector<T, A> vect1;

Nothing happened on the pile , But variables take up the memory needed by all the members on the stack . There? , It will always be there , until vect1 Out of range , because vect1 Just like any other type of object double, int What about him . It will sit on its stack , Waiting to be destroyed , No matter how much memory it processes on the heap .

vect1 Don't point the pointer anywhere , because vector It's empty. .

On the pile vector

Now we need a point vector The pointer to , And use some dynamic heap allocation to create vector.

std::vector<T, A> * vp = new std::vector<T, A>;

our vp Variables are on the stack ,vector On the pile . Again ,vector Itself will not move on the heap , Because its size is constant . Pointer only （ begin, end, capacity） If reallocation occurs , Will follow the data location in memory .

vector Additive elements

T a;
vect1.push_back(a);

Single push_back After that std :: vector

Variable vect1 Still in place , But the memory on the heap has been allocated to contain an element T.

What happens if you add another element ？

vect1.push_back(a);

The second time pushback after std :: vector

• There will not be enough space allocated on the heap for data elements （ Because so far , It's just a memory location ）.
• A new memory block will be allocated to two elements
• The first element will be copied / Move to new storage .
• Old memory will be freed .

We see ： The new memory location is different .

To gain more insight , Let's see what happens when we destroy the last element .

vect1.pop_back();

The allocated memory does not change , But the last element will call its destructor , And the end pointer moves down one position .

2 Time pushback and 1 Time popback After std :: vector

As you can see ： capacity() == capacity-begin == 2 Even though size() == end-begin == 1

Test growth

Here I borrow a picture of Comrade Houjie

std::vector<int> my_vec;
auto it=my_vec.begin();
for (int i=0;i<10000;++i) {
    auto cap=my_vec.capacity();
    my_vec.push_back(i);
    if(it!=my_vec.begin()) {
        std::cout<<"it!=my_vec.begin() :";
        it=my_vec.begin();
    }
    if(cap!=my_vec.capacity())std::cout<<my_vec.capacity()<<'\n';
}

it!=my_vec.begin() :1
it!=my_vec.begin() :2
it!=my_vec.begin() :4
it!=my_vec.begin() :8
it!=my_vec.begin() :16
it!=my_vec.begin() :32
it!=my_vec.begin() :64
it!=my_vec.begin() :128
it!=my_vec.begin() :256
it!=my_vec.begin() :512
it!=my_vec.begin() :1024
it!=my_vec.begin() :2048
it!=my_vec.begin() :4096
it!=my_vec.begin() :8192
it!=my_vec.begin() :16384

Common mistakes

  vector<int>v(4);
  std::cout << v[0] << std::endl;
  std::cout << v[1] << std::endl;
  std::cout << v[2] << std::endl;
  std::cout << v[3] << std::endl;
  ///>-1  A cross-border visit 
  /** --1.1 std::vector::operator[]  Boundary checks are not performed ,
   *  Typical undefined behavior (Undefined Behavior),
   *  In this case, the exception mechanism (try/thorw/catch) It doesn't work .
  */
  std::cout << v[4] << std::endl;// Transboundary 
  /** --1.2 std::vector::at,
   *  It performs a boundary check , If you cross the border , Will throw out  std::out_of_range  abnormal .
  */
  try {
    std::cout << v.at(4) << std::endl;
  } catch (out_of_range e) {
    std::cout << e.what() << std::endl;
  }
  ///> -2  Reallocate memory 
  try {
    std::vector<int> v1;
    v.resize(v1.max_size() + 5);
  } catch (length_error e) {
    std::cout << e.what() << std::endl;
  }

notes ： In the actual operation, the security （ Use at() Abnormal monitoring ） And execution speed （ Use an array to represent ） Choose between -- To quote 《C++ primer plus 6》.

reference

• [1] vector reallocation C++
• [2] c ++ Vector, Whenever it expands on the stack / When reassigning , What's going to happen ？
• [3] c ++ Vector