Table of Contents
1.Introduction and use of vector
1.1 Introduction to vector
1.2 Use of vector
1.2.1 Definition of vector
1.2.2 Use of vector iterator (iterator)
1.2.3 Vector space growth problem
1.2.4 Addition, deletion, modification and query of vector
1.2.5 Vector iterator failure problem. (emphasis)
2.Vector in-depth analysis and simulation implementation
2.1 Simulation implementation of reserve
Introduction and use of 1.vector
Introduction to 1.1 vector
C++ official website vector document introduction
- A vector is a sequence container that represents a variable-sized array.
- Just like arrays, vectors also use continuous storage space to store elements. This means that you can use subscripts to access the elements of the vector, which is as efficient as an array. But unlike an array, its size can be dynamically changed, and its size will be automatically handled by the container.
- Essentially, vector uses a dynamically allocated array to store its elements. When new elements are inserted, the array needs to be resized. In order to increase storage space, allocate a new array and then move all elements to this array. In terms of time, this is a relatively expensive task, because every time a new element is added to the container, the vector does not re-allocate the size every time.
- Vector allocation space strategy: vector allocates some extra space to accommodate possible growth because the storage space is larger than the actual storage space required. Different libraries use different strategies to trade off space usage and reallocation. But in any case, the reallocation should be logarithmically increasing in interval size, so that inserting an element at the end is done in constant time.
- Therefore, vector takes up more storage space in order to gain the ability to manage storage space and grow dynamically in an efficient manner.
- Compared with other dynamic sequence containers (deque, list and forward_list), vector is more efficient when accessing elements, and adding and deleting elements at the end is relatively efficient. For other deletion and insertion operations that are not at the end, the efficiency is even lower. It is better to use unified iterators and references than list and forward_list.
There are three realms of using STL: being able to use it, being able to understand it, and being able to expand it. So let’s learn vector next. We will also learn it in this way.
Use of 1.2 vector
When learning vector, you must learn to check the documentation: vector’s documentation introduction, vector is very important in practice. In practice, we only need to be familiar with common interfaces. The following lists which interfaces we should focus on mastering.
1.2.1 Definition of vector
| (constructor) constructor declaration | Interface description |
| vector( )(Key point) | No-argument construction |
| vector (size_type n, const value_type & amp; val = value_type()) | Construct and initialize n val |
| vector (const vector & amp; x); (Key point) | Copy construction |
| vector (InputIterator first, InputIterator last); | Use iterator for initialization construction |
1.2.2 Usage of vector iterator
| Usage of iterator | Interface description |
| begin + end (emphasis) |
Get the iterator/const_iterator of the first data position, and get the next position of the last data The iterator/const_iterator |
| rbegin + rend | gets the reverse_iterator of the last data position, and gets the reverse_iterator of the previous position of the first data reverse_iterator |
Code example:
void test_vector1()
{
vector<int> v1;
vector<int> v2(10,0);
vector<int> v3(v2.begin(), v2.end());
string s1("hello world");
vector<int> v4(s1.begin(), s1.end());
//You can use the iterator range of other containers
//vector is a template
vector<int> v5(v4);//copy construction
//Traverse
//1.for loop
for (size_t i = 0; i < v2.size(); i + + )
{
cout << v2[i] << " ";
}
cout << endl;
//2.Iterator
//auto it = v5.begin();
vector<int>::iterator it = v5.begin();
while (it != v5.end())
{
cout << *it << " ";
it++;
}
cout << endl;
//3. Range for
for (auto & ch : v5)
{
cout << ch << " ";
}
cout << endl;
}
1.2.3 Vector space growth problem
| Capacity space | Interface description |
| size | Get the number of data |
| capacity | Get the capacity |
| empty | Judge whether it is empty |
| resize (key) | Change the size of the vector |
| reserve (emphasis) | Change the capacity of vector |
- When the capacity code is run under vs and g++ respectively, you will find that the capacity increases by 1.5 times under vs and 2 times by g++. This issue is often investigated. Don’t rigidly believe that the vector capacity is increased by 2 times. The specific increase is defined based on specific needs. vs is the PJ version STL, g++ is the SGI version STL.
- Reserve is only responsible for opening up space. If you know for sure how much space is needed, reserve can alleviate the cost problem of vector expansion.
- Resize will also initialize while opening space, which affects size.
void test_vector3()
{
vector<int> v1;
//v1.reserve(100);//size = 0;capacity = 100;
v1.resize(100);//size = 100; capacity = 100;
for (int i = 0; i < v1.size(); i + + )
{
v1[i] = i;
}
for (auto i : v1)
{
cout << i << " ";
}
cout << endl;
v1.shrink_to_fit();//Shrink the capacity, let capacity = size, it will find another space of size and copy it, generally not used
//v1.front();//The first element
//v1.back();//The last element
//v1.data();//Array pointer
}
1.2.4 vector addition, deletion, modification and query
| vector addition, deletion, checking and modification | Interface description |
| push_back (key) | Tail insertion |
| pop_back (key point) | Tail deletion |
| find | Find. (Note that this is an algorithm module implementation, not a member interface of vector) |
| insert | Insert val before position |
| erase | Delete the data at position position |
| swap | Exchange the data space of two vectors |
| operator[] (emphasis) | Access like an array |
void test_vector4()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.insert(v1.begin(), 0);
v1.push_back(5);
for (auto i : v1)
{
cout << i << " ";
}
cout << endl;
v1.pop_back();
for (auto i : v1)
{
cout << i << " ";
}
cout << endl;
vector<int>::iterator it = find(v1.begin(), v1.end(), 3);
if (it != v1.end())
{
v1.insert(it, 50);
}
for (auto i : v1)
{
cout << i << " ";
}
cout << endl;
it = find(v1.begin(), v1.end(), 50);
if (it != v1.end())
{
v1.erase(it);
}
for (auto i : v1)
{
cout << i << " ";
}
cout << endl;
v1.clear();
//v1.shrink_to_fit();
cout << v1.size() << endl;
cout << v1.capacity() << endl;
}
1.2.5 Vector iterator failure problem. (emphasis)
The main function of an iterator is to allow the algorithm to not care about the underlying data structure. The underlying layer is actually a pointer, or it encapsulates the pointer, such as: vector iterator It is the original ecological pointer T*. Therefore, the failure of an iterator actually means that the space pointed to by the corresponding pointer at the bottom of the iterator is destroyed, and using a space that has been released will cause the program to crash (that is, if you continue to use the expired iterator, the program may crash).
Operations on vector that may cause its iterator to become invalid include:
1. Operations that cause the underlying space to change may cause the iterator to fail, such as: resize, reserve, insert, assign, push_back, etc.
Reason for the error: The above operations may cause the vector to expand, which means that the underlying principle of the vector the old space is released, and when printing, it still uses When operating the it iterator, the old space between releases is actually a piece of space that has been released, causing the code to crash during runtime.
Solution: After the above operation is completed, if you want to continue to operate the elements in the vector through the iterator, you only need to reassign it. You can use the return value of insert: the position of the newly inserted element.
2. Delete the element at the specified position–erase
After erase deletes the element at pos position, the elements after pos position will be moved forward, without causing changes in the underlying space. Theoretically, the iterator should not be invalid, but: if pos happens to be the last element, after deletion, pos happens to be The position of end, and there is no element at the end position, then pos is invalid. Therefore, when deleting an element at any position in the vector, vs considers the iterator at that position to be invalid.
You can use the return value of erase, which will return the position of the next element to be deleted. After the data is moved forward, it will still be the position to be deleted.
3. Note: Under Linux, the g++ compiler is not very strict in detecting iterator failure, and the processing is not as extreme as vs.
4. Similar to vector, after string insertion + expansion operation + erase, the iterator will also become invalid.
Solution to iterator failure: Just reassign the iterator before use
2.vector in-depth analysis and simulation implementation
The internal members of vector have three pointers, _start, _finish, _end_of_storage. Use these three pointers to operate data.
The iterator begin() is equivalent to the position of _start, and end() is equivalent to the position of _finish.
Simulation implementation of 2.1 reserve
If reserve(n), n>capacity(), then you need to open space, then copy the data, and then release the previous space. We simulate the implementation below. When copying space, you will encounter some deep and shallow copy problems:
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];//Throw exception on failure
size_t sz = size();
if (_start != nullptr)
{
//memcpy(tmp, _start, sizeof(T) * sz); //Copy data
//The data copied here is only a shallow copy, if the string is stored inside the vector
//When you want to release the original space
//The destructor of vector will call the destructor of string and release the content pointed to by the original string.
//Here memcpy just copies the value of the pointer, and the original space is released after delete.
//The _str of string in the expanded space have become wild pointers
//deep copy
for (size_t i = 0; i < size(); i + + )
{
tmp[i] = _start[i];
//If it is a built-in type, their assignment overloaded function and deep copy will be automatically called.
//The benefits of reference counting shallow copy can be shown here
//Because it will make a deep copy of the original data and then release the original data.
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
For other function simulation implementations, please check my gittee link
This article is over!