1, About vector:
1. vector is a sequence container that represents a variable size array.
2. just like array, vector also adopts
Continuous storage space
To store elements. This means that you can use subscripts to access the elements of a vector, which is as efficient as an array. But unlike an array, its size can be dynamically changed, 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,
Allocate a new array, and then move all the elements to this array
. This is a relatively expensive task in terms of time, 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 reallocation should be a logarithmically increasing interval size, so that the insertion of an element at the end is completed in constant time complexity.
5. therefore, the 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\u lists), vector is more efficient when accessing elements, and it is relatively efficient to add and delete elements at the end. For other delete and insert operations that are not at the end, the efficiency is lower. Compared with lists and forward_lists uniform iterators and references are better.
2, Establishment and output of vector
#include <vector>
void TestVector1()
{
vector<int> v1;
vector<int> v2(10, 5);
int array[] = { 1, 2, 3, 4, 5 };
vector<int> v3(array, array + sizeof(array) / sizeof(array[0]));
vector<int> v4(v3);
// C++11
vector<int> v5{ 1, 2, 3, 4, 5 };
// Traversal of vector
// 1. for+ subscript
for (size_t i = 0; i < v2.size(); ++i)
cout << v2[i] << " ";
cout << endl;
// 2. scope for
for (auto e : v3)
cout << e << " ";
cout << endl;
// 3. forward iterator
vector<int>::iterator it = v4.begin();
while (it != v4.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 4. reverse iterator
// vector<int>::reverse_iterator rit = v5.rbegin();
auto rit = v5.rbegin();
while (rit != v5.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
}
int main()
{
vector<vector<int>> vv(5);
TestVector1();
//TestVector2();
return 0;
}The output result is:
be careful:
void resize(size_t newsize, const T& val = T())
Assume that the number of elements of the current object is oldsize and the size of the underlying space is capacity
1. oldsize < newsize < capacity
Without capacity expansion, fill the newsize oldsize element set to val at the end of the vector
newsize > capacity
Capacity expansion - vecot can always fill in newsize oldsize elements set to val
2. newsize < oldsize directly reduces the number of effective elements to newsize
3. pay attention to the difference between resize and reverse. Resize is to reset the number of effective elements, and reverse is to reset the capacity (only increase but not decrease)
#include <vector>
void TestVector2()
{
vector<int> v{ 1, 2, 3, 4, 5 };
v.reserve(10);
cout << v.size() << endl; //5
cout << v.capacity() << endl; //10
v.resize(8, 6);
cout << v.size() << endl; //8
cout << v.capacity() << endl; //10
v.resize(20, 7);
cout << v.size() << endl; //20
cout << v.capacity() << endl; //20
v.resize(10);
cout << v.size() << endl; //10
cout << v.capacity() << endl; //20
v.resize(3);
cout << v.size() << endl; //3
cout << v.capacity() << endl; //20
}
int main()
{
vector<vector<int>> vv(5);
//TestVector1();
TestVector2();
return 0;
}The output result is:
3, Use of iterators
Note that end points to the next position of the last element.
#include <iostream>
#include <vector>
using namespace std;
void PrintVector(const vector<int>& v) {
// Const object uses const iterators for traversal printing
vector<int>::const_iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
int main()
{
// Using push_back insert 4 data
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
// Traversal printing using iterators
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// Modify using iterators
it = v.begin();
while (it != v.end())
{
*it *= 2;
++it;
}
// Use reverse iterator to traverse and print
vector<int>::reverse_iterator rit = v.rbegin();
while (rit != v.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
PrintVector(v);
return 0;
}The result of the above code is:
IV. vector space growth (and size and reverse usage)
capacity
The code for
vs
and
g++
It will be found that,
The capacity is increased by 1.5 times in vs and 2 times in g++ (linux)
. Do not think that the capacity increase of the sequence table is 2
Times, the specific growth is defined according to the specific demand. vs
yes
PJ
edition
STL
，
g++
yes
SGI
edition
STL
.
reserve
Only responsible for opening up space. If you know how much space you need,
reserve
Can alleviate
vector
The cost defect of capacity expansion. resize initializes while opening space, affecting
size
.
#include <iostream>
#include <vector>
int main()
{
size_t sz;
std::vector<int> foo;
sz = foo.capacity();//Value is 0
std::cout << "making foo grow:\n";
for (int i = 0; i < 100; ++i) {
foo.push_back(i);
if (sz != foo.capacity()) {
sz = foo.capacity();
std::cout << "capacity changed: " << sz << '\n';
}
}
}
resize usage:
// vector::resize
#include <iostream>
#include <vector>
int main()
{
std::vector<int> myvector;
// set some initial content:
for (int i = 1; i < 10; i++)
myvector.push_back(i);
myvector.resize(5);
for (int i = 0; i < myvector.size(); i++)
{
cout << myvector[i] << " ";
}
cout << endl;
myvector.resize(8, 100);
//Set the number of effective elements to 8. Note that the original value will not be overwritten, but more elements than the original value will be supplemented with 100
for (int i = 0; i < myvector.size(); i++)
{
cout << myvector[i] << " ";
}
cout << endl;
myvector.resize(12);
for (int i = 0; i < myvector.size(); i++)
{
cout << myvector[i] << " ";
}
cout << endl;
std::cout << "myvector contains:";
for (int i = 0; i < myvector.size(); i++)
std::cout << ' ' << myvector[i];
std::cout << '\n';
return 0;
}
reverse usage:
// vector::reserve
#include <iostream>
#include <vector>
int main()
{
size_t sz;
std::vector<int> foo;
sz = foo.capacity();
std::cout << "making foo grow:\n";
for (int i = 0; i < 100; ++i) {
foo.push_back(i);
if (sz != foo.capacity()) {
sz = foo.capacity();
std::cout << "capacity changed: " << sz << '\n';
}
}
cout << "-----------------------------" << endl;
std::vector<int> bar;
sz = bar.capacity();
bar.reserve(100); // this is the only difference with foo above
std::cout << "making bar grow:\n";
for (int i = 0; i < 100; ++i) {
bar.push_back(i);
if (sz != bar.capacity()) {
sz = bar.capacity();
std::cout << "capacity changed: " << sz << '\n';
}
}
return 0;
}The code result is:
V. addition, deletion, modification and query of vector
// push_back/pop_back
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int a[] = { 1, 2, 3, 4 };
vector<int> v(a, a + sizeof(a) / sizeof(int));
vector<int>::iterator it = v.begin();
while (it != v.end()) {
cout << *it << " ";
++it;
}
cout << endl;
v.pop_back();
v.pop_back();
it = v.begin();
while (it != v.end()) {
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
// find / insert / erase
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
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);
// Insert 30 before pos position
v.insert(pos, 30);
vector<int>::iterator it = v.begin();
while (it != v.end()) {
cout << *it << " ";
++it;
}
cout << endl;
pos = find(v.begin(), v.end(), 3);
// Delete pos location data
v.erase(pos);
it = v.begin();
while (it != v.end()) {
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}The result of the above code is:
//swap
// New for+auto traversal of vector in operator[]+index and C++11
// It is convenient for vector to use these two traversal methods.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int a[] = { 1, 2, 3, 4 };
vector<int> v(a, a + sizeof(a) / sizeof(int));
// Read and write position 0 through [].
v[0] = 10;
cout << v[0] << endl;
// Traverse vector by [i]
for (size_t i = 0; i < v.size(); ++i)
cout << v[i] << " ";
cout << endl;
cout << "----------------" << endl;
vector<int> swapv{5,5,5};
swapv.swap(v);
cout << "v data:";
for (size_t i = 0; i < v.size(); ++i)
cout << v[i] << " ";
cout << endl;
cout << "swapv data:";
for (size_t i = 0; i < swapv.size(); ++i)
cout << swapv[i] << " ";
cout << endl;
cout << "------------------" << endl;
// New range for traversal supported by C++11
for (auto x : v)
cout << x << " ";
cout << endl;
return 0;
}
Vi. vector iterator failure
The main function of iterator is to make the algorithm do not care about the underlying data structure
It's actually a pointer
, or encapsulate the pointer. For example, the iterator of vector is the primitive pointer T*. So the iterator fails,
In fact, the space pointed to by the corresponding pointer at the bottom of the iterator is destroyed, and a freed space is used
, the result is that the program crashes (that is, if you continue to use an iterator that has expired, the program may crash).
The operations that may invalidate a vector's iterators are:
1. any operation that may cause the underlying space to change may be the iterator failure, such as: resize, reserve, insert, assign, 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 be expanded 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 the 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, 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 it erator, you just need to re
Assign value.
*/
while(it != v.end())
{
cout<< *it << " " ;
++it;
}
cout<<endl;
return 0; }
2. 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 position invalidates the pos iterator.
v.erase(pos);
cout << *pos << endl; // Illegal access may result here
return 0;
}
After erase deletes the pos position element, the element after the pos position will be moved forward without changing the underlying space. Theoretically, the iterator should not become invalid. However, if pos happens to be the last element, and 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.