[C + +] vector of STL container


C + + introduces the idea of object-oriented. Compared with C language, a class can better manage and operate some data structures.

In C language, we use fixed length array and dynamic array from malloc to maintain a continuous set of data of the same type

In C + +, based on the idea of object-oriented, the class used to manage spatially continuous data sets of the same type came into being. In essence, the vector class is a sequence container of encapsulated variable size arrays


1. Introduction to vector

When we learn STL, documents are our sharp weapon. Learning to check documents will get twice the result with half the effort. Here are two C + + document websites:

Document introduction of vector:

  1. vector is a sequence container that represents a variable size array.
  2. Like arrays, vectors use continuous storage space to store elements. This means that the elements of vector can be accessed by subscript, which is as efficient as array. But unlike an array, its size can be changed dynamically, and its size will be automatically processed by the container.
  3. Essentially, vector uses dynamically allocated arrays to store its elements. When new elements are inserted, the array needs to be resized to increase storage space. This is done by allocating a new array and then moving all the elements to this array. In terms of time, this is a relatively expensive task, because the vector does not reallocate the size every time a new element is added to the container.
  4. Vector space allocation strategy: vector will allocate some additional space to accommodate possible growth, because the storage space is larger than the actual storage space. Different libraries use different strategies to balance the use and reallocation of space. But in any case, the redistribution should be logarithmically increasing interval size, so that when inserting an element at the end, it is completed in constant time complexity.
  5. Therefore, vector takes up more storage space. In order to obtain the ability to manage storage space and grow dynamically in an effective way.
  6. Compared with other dynamic sequence containers (deques, lists and forward_lists), vector is more efficient when accessing elements, and it is relatively efficient to add and delete elements at the end. For other deletion and insertion operations that are not at the end, the efficiency is lower.

STL as a model of generic programming, our vector class is naturally a class template

template <class T>
class vector{

The template parameter T is obviously the type of the element we want to insert into this dynamic array. It can be built-in type data such as int and char, or user-defined type data such as string and vector

vector<int> v1;
vector<char> v2;
vector<vector<int>> v3;
vector<string> v4;

Let's take another look at the member variables of the vector class. We know that string uses:

size_t _size; ------>Number of valid characters
size_t _capacity; ------>Total space size
T* _str; ------>String pointer

To maintain the dynamic space and string properties

Of course, vector can completely apply the above three variables. However, we can achieve the same purpose by using three pointers to maintain vector this time:

T* _start; ------>Point to data block header
T* _finish; ------>Point to the tail of valid data (i.e. the address of the next position of the last valid element)
T* _endOfStorage; ------>Point to the end of the storage space

So by analogy:

_size == _finish - _start
_capacity == _endOfStorage - _start
_str = _start

2. Common interface and Simulation Implementation of vector

2.1 common constructions of string class objects

Function namefunction
vector()Nonparametric structure
vector(int n, const T& x = T())Construct and initialize n x (the default value of X is 0)
template <class InputInerator> vector(InputInerator first, InputInerator last)Initializing constructs using iterators
vector(const vector&v)copy constructor
operator=Assignment overload: assign a vector object to another vector object

Use of multiple constructors:

void Teststring()
	std::vector<int> first; // Nonparametric structure
	std::vector<int> second (4,100); //Construct and initialize 4 100
	std::vector<int> third (second.begin(),second.end()); // Using iterator interval construction of second
	std::vector<int> fourth (third); // copy construction 

It is worth mentioning that since the iterator of vector is the pointer of T, the pointer is the natural iterator of vector, so we can use the front and back pointers of the array as the left and right intervals of the iterator to initialize vector

int arr[] = {1,2,3,4,5,56,1};
vector<int> a(arr,arr + 2);

Analog implementation of interface:

  • Constructor
//non-parameter constructor 
basic_string(const T* s = "")
	_str = new T[_size + 1];
	strcpy(_str, s);
//Construct and initialize n x
vector(int n, const T& x = T())
    :_start(new T[n])
    , _finish(_start + n)
    , _endOfStorage(_start + n)
    for (size_t i = 0; i < n; i++) {
        _start[i] = x;
//Using iterator interval construction
template <class InputInerator>
vector(InputInerator first, InputInerator last) 
    : _start(nullptr)
    , _finish(nullptr)
    , _endOfStorage(nullptr)
    while (first != last) {
  • copy construction
vector(const vector& v) 
    , _finish(nullptr)
    , _endOfStorage(nullptr) 
    vector tmp(v.cbegin(), v.cend());
  • Destructor
~vector() {
    delete[] _start;
    _start = nullptr;
    _finish = nullptr;
    _endOfStorage = nullptr;
  • Assignment overload
//Assignment overload
vector& operator=(vector v) {
    return *this;

2.2 capacity operation of vector class object

Interface nameInterface function
size()Returns the number of elements in the array
capacity()Returns the amount of space currently allocated to the array
empty()Determine whether the array is empty
reserve(n)Reset the size of the space allocated to the array and reserve space for the array
resize(n, x)Reset the array elements, change the number of array elements to n, and fill the extra space with x

be careful:

  1. For the increase of array capacity, the capacity under vs is increased by 1.5 times, and that of g + + is increased by 2 times. Vs is the PJ version STL, and g + + is the SGI version STL.
  2. Reserve is only responsible for opening up space. If you know how much space you need, reserve can alleviate the cost defect of vector capacity expansion.
  3. resize initializes while opening space, affecting size.

Analog implementation of interface:

  • size()
//size() interface
size_t size() const {
    return _finish - _start;
  • capacity()
//capacity() interface
size_t capacity() const {
    return _endOfStorage - _start;
  • empty()
// Air judgment
bool empty() {
    return size() == 0;
  • reserve(n)
void reserve(size_t n) {
    size_t sz = size();
    T* tmp = new T[n];
    memcpy(tmp, _start, size()*sizeof(T));
    delete[] _start;
    _start = tmp;
    _finish = _start + sz;
    _endOfStorage = _start + n;
  • resize(n, x)
void resize(size_t n, const T& x = T()) {
    if (n <= size()) {
        _finish = _start + n;
    else {
        if (n > capacity()) {
        for (size_t i = size(); i < n; i++) {
            _start[i] = x;

2.3 vector class object obtains the interface between element and iterator

Interface nameInterface function
operator[ ]Position of pos element returned
begin()Returns the iterator of the first valid element
end()Returns the iterator at the next position of the last element

Analog implementation of interface:

  • operator[]
//Overload []
T& operator[](size_t pos) {
    assert(pos < size());
    return _start[pos];
const T& operator[](size_t pos) const {
    assert(pos < size());
    return _start[pos];
  • begin() and end()
typedef T* iterator;
typedef const T* const_iterator;
iterator begin() {
    return _start;
iterator end() {
    return _finish;
const_iterator cbegin() const {
    return _start;
const_iterator cend() const {
    return _finish;

2.4 modifying element interface of string class object

Interface nameInterface function
iterator insert(iterator pos, const T& xInsert an element at the pos address
push_back()Insert 1 element at the end
erase()Delete element
pop_back()Delete an element at the end
clear()Clear all elements and set size to 0
swap()Swap two class objects

Analog implementation of interface:

  • insert()
//Insert element
iterator insert(iterator pos, const T& x) {
    assert(pos >= _start && pos <= _finish);
    if (_finish == _endOfStorage) {
        size_t len = pos - _start;
        size_t new_capacity = (_start == _finish) ? 4 : 2 * (_endOfStorage - _start);
        pos = _start + len;
    for (iterator i = _finish; i >= pos + 1; i--) {
        *i = *(i - 1);
    *pos = x;
    return pos;
  • push_back()
//push_ Insert an element at the end of back
void push_back(const T& x) {
    insert(_finish, x);  
  • erase()
iterator erase(iterator pos) {
    for (vector::iterator i = pos; i < end() - 1; i++) {
        *i = *(i + 1);
    return pos;
  • pop_back()
void pop_back() {
  • clear()
void clear() {
    erase(begin(), end());
  • swap()
void swap(vector& v2) {
    ::swap(_start, v2._start);
    ::swap(_finish, v2._finish);
    ::swap(_endOfStorage, v2._endOfStorage);

3. How to get familiar with the interface - brush questions

Brushing questions must be the best way for beginners to master STL. Replace learning with questions and get twice the result with half the effort. Here are some vector exercises



4. Iterator failure of vector

The main function of iterator is to make the algorithm do not care about the underlying data structure. Its underlying layer is actually a pointer or encapsulates the pointer. For example, the iterator of vector is the original ecological pointer T*

Therefore, the failure of the iterator is actually the destruction of the space pointed to by the corresponding pointer at the bottom of the iterator and the use of a space that has been released. The consequence is that if you continue to use the failed iterator, the program may crash

Iterators fail in two ways:

  1. Illegal access to freed memory
  2. The meaning of iterators has changed

For vector, the operations that may cause its iterator to fail are:

  1. The operation that will cause the change of its underlying space may be the failure of the iterator, such as resize, reserve, insert, assign and push_back et al
#include <iostream>
using namespace std;
#include <vector>
int main()
	vector<int> v{1,2,3,4,5,6};
	auto it = v.begin();
// Increase the number of effective elements to 100, fill the extra positions with 8, and the bottom layer will expand during the operation
// v.resize(100, 8);
// The function of reserve is to change the expansion size without changing the number of effective elements. The underlying capacity may change during operation
// v.reserve(100);
// During element insertion, the original space may be released due to capacity expansion
// v.insert(v.begin(), 0);
// v.push_back(8);
// Assigning a new value to the vector may cause the underlying capacity to change
	v.assign(100, 8);
Error reason: the above operations may lead to the expansion of the vector, that is, the old space of the underlying principle of the vector is released,
When printing, it also uses to release the old space between them. When operating on the IT iterator, the actual operation is a piece of space that has been released
 Space, causing the code to crash at runtime.
Solution: after the above operations are completed, if you want to continue to operate the elements in the vector through the iterator, you just need to re-enter it
 Assignment is enough.
	while(it != v.end())
		cout<< *it << " " ;
	return 0;
  1. Delete the specified location element – erase
#include <iostream>
using namespace std;
#include <vector>
int main()
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	// Use find to find the iterator where 3 is located
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
	// Deleting the data at the pos location will invalidate the pos iterator.
	cout << *pos << endl; // This will result in illegal access
	return 0;

After erase deletes the pos position element, the element after the pos position will move forward without changing the underlying space. Theoretically, the iterator should not fail
However, if pos happens to be the last element, after deletion, pos happens to be the end position, and the end position has no element, then pos will become invalid. Therefore, when you delete an element at any position in the vector, vs considers the position iterator invalid.

The function of the following code is to delete even numbers in the array. Code 1 has the problem of iterator failure, and code 2 is correct

❗❗❗❗❗ Solution to iterator failure: reassign the iterator before use ❗❗❗❗❗

Code one

int main()
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
		if (*it % 2 == 0)
	return 0;

Code 2

int main()
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
		if (*it % 2 == 0)
			it = v.erase(it); //Reassign to iterators
	return 0;

5. Two dimensional dynamic array

To build a two-dimensional dynamic array, the idea is the same as that of the two-dimensional array learned before:

Just treat each row as a one-dimensional array

vector<vector<int>> vv;

Suppose we construct a 5 × 5 and assign all elements to 1

  1. From the perspective of two-dimensional array, create five rows, that is, five one-dimensional arrays
  1. From the perspective of one-dimensional array, each row is given 5 1s
for(int i = 0; i < vv.size(); i++)
	vv[i].resize(5, 1);

6. Other words

  1. Simulating stl is a boring and time-consuming process, but it can help us deeply understand pointers, data structures, object-oriented programming, logical thinking ability and code ability

  2. "STL source code analysis" -- Hou Jie. I'm going to read it

  3. All codes of this blog: github,gitee

Keywords: C++ Container STL

Added by fangfang on Fri, 04 Feb 2022 02:25:47 +0200