vector
Foreword
In the past few days, I have used STL a lot when writing code, and I have also felt the power of STL, so I reviewed the content of STL again, and summarized and extracted some basic things and important content. This is a vector article . C++’s STL provides us with many available containers. Vector is one of the most commonly used containers. The basic contents that vector should master include constructors, insertion and deletion of elements, assignments, access and other operations. The key content should be to master the expansion mechanism of vector, the principle of memory size change, etc.
1. Introduction to vector
- The vector container is a variable-length array (dynamic array), and elements can be inserted and deleted at any time.
- Vector is called a vector container because the container is good at inserting or deleting elements at the tail, which can be completed in O(1) time; and if you want to insert array elements at the head or middle of the container, it will take O(N) time. , because he needs to move the following elements back. (In fact, the principle is similar to the sequence table we learned in data structure and algorithm)
- The biggest difference between vector and ordinary array is that array is a static array (array with fixed capacity), while vector can be dynamically expanded. That is, containers can be inserted and deleted. During this process, the vector will dynamically adjust the space occupied.
- Vector access elements must also abide by the rules that cannot cross the boundary, otherwise it will cause memory security risks.
2. Constructor
(1) Function: used to create vector containers
(2)Method:
1. vector<T> v;//Default no-parameter construction 2. vector<T> v{<!-- -->elem1, elem2, elem3...}//Specify element construction 3. vector<T> v(n, elem)//Copy n elem into element construction 4. vector<T> v2(v1)//Copy another vector construct 5. vector<T> v2(v1.begin(), v1.end())//Interval construction, assign the elements from begin() to end() in the v1 interval to v2; //Two-dimensional construction initialization vector<vector<int>> v; vector<vector<int>> v(n + 1, vector<int>(m + 1, 0));//two-dimensional construction
Example:
#include<iostream> #include<vector> using namespace std; //Print vector void printVector(vector<int> & amp; v) {<!-- --> for (vector<int>::iterator it = v.begin(); it != v.end(); it + + ) {<!-- --> cout << *it << " "; } cout << endl; } //vector container construction void test01() {<!-- --> vector<int> v1; for (int i = 0; i < 10; i + + ) {<!-- --> v1.push_back(i); } printVector(v1); vector<int> v2{<!-- --> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; printVector(v2); vector<int> v3(v1.begin(), v1.end()); printVector(v3); vector<int> v4(11, 4); printVector(v4); vector<int> v5(v4); printVector(v4); } int main() {<!-- --> test01(); return 0; }
operation result:
3. Assignment operation
(1) Function: assign value to vector container
(2)Method:
1. vector & amp; operator = (const vector & amp;vec);//Overloading the equal sign operator 2. v.assign(v1.begin(), v1.end()) uses assign to perform interval assignment 3. v.assign(n, elem), assign n elem copies to elements
Example:
#include<iostream> #include<vector> using namespace std; //Print vector void printVector(vector<int> & amp; v) {<!-- --> for (vector<int>::iterator it = v.begin(); it != v.end(); it + + ) {<!-- --> cout << *it << " "; } cout << endl; } void test02() {<!-- --> vector<int> v1; for (int i = 0; i < 10; + + i) {<!-- --> v1.push_back(i); } printVector(v1); vector<int> v2; v2 = v1; printVector(v2); vector<int> v3; v3.assign(v1.begin(), v1.end()); printVector(v3); vector<int> v4; v4.assign(11, 4); printVector(v4); } int main() {<!-- --> test02(); return 0; }
operation result:
4. Capacity and size
(1) Function: Manipulate the capacity and size of vector containers
(2)Method:
1. v.empty();//Used to determine empty 2. v.capacity();//Used to obtain the size of the number of elements in the container 3. v.size();//Used to obtain the current number of elements in the container 4. v.resize(int num);//Used to re-specify the length of the container. If it becomes shorter, it will be deleted in stages. 5. v.resize(int num, int elem);//Used to re-specify the length of the container and fill it with elem
Example:
#include<iostream> #include<vector> using namespace std; //Print vector void printVector(vector<int> & amp; v) {<!-- --> for (vector<int>::iterator it = v.begin(); it != v.end(); it + + ) {<!-- --> cout << *it << " "; } cout << endl; } //capacity, size void test03() {<!-- --> vector<int> v1; for (int i = 0; i < 10; i + + ) {<!-- --> v1.push_back(i); } printVector(v1); if (v1.empty()) {<!-- --> cout << "v1 is empty" << endl; } else {<!-- --> cout << "v1 is not empty" << endl; cout << "capacity:" << v1.capacity() << endl; cout << "The size of v1 is:" << v1.size() << endl; //resize v1.resize(14); //If the respecified length is longer than the original, the new position will be filled with 0 by default. printVector(v1); v1.resize(11, 45); //Overloaded, parameter 2 can specify the default filling value printVector(v1); v1.resize(4); //If the respecified one is shorter than the original one, the excess part will be truncated. printVector(v1); } } int main() {<!-- --> test03(); return 0; }
operation result:
Additional:
- The capacity in vector refers to the capacity, that is, the maximum number that can be saved without allocating more memory, and size is the size of the current container.
- size is always less than or equal to capacity
- When the size in the container == capacity, if you insert content into it at this time, the vector will apply for more space.
- When applying for space, you do not directly open up the original space continuously, but find another larger space. After completing the copy operation, then point the current vector pointer to the new larger space.
5. Insertion and deletion
(1) Function: insert and delete elements into the vector container
(2)Method:
1. v.push_back(ele);//Insert element at the end 2. v.pop_back();//Delete the last element 3. v.insert(const_iterator pos, ele);//Insert element ele at the position pos pointed by the iterator 4. v.insert(const_iterator pos, count, ele);//Insert count elements at the specified position pos 5. v.erase(const_iterator pos);//Delete the element pointed to by the iterator 6. v.erase(const_iterator start, const_iterator end);//Delete the elements between the iterator from start to end 7. v.clear();//Delete all elements in the container
Example:
#include<iostream> #include<vector> using namespace std; //Print vector void printVector(vector<int> & amp; v) {<!-- --> for (vector<int>::iterator it = v.begin(); it != v.end(); it + + ) {<!-- --> cout << *it << " "; } cout << endl; } //Insert and delete void test04() {<!-- --> vector<int> v1; //Tail insert v1.push_back(11); v1.push_back(4); v1.push_back(5); v1.push_back(14); printVector(v1); //Delete tail v1.pop_back(); printVector(v1); //Insert at specified position v1.insert(v1.begin(), 114); printVector(v1); //Insert the specified number at the specified position v1.insert(v1.begin(), 2, 514); printVector(v1); //delete v1.erase(v1.begin()); printVector(v1); vector<int> v2(v1); //Delete interval v1.erase(v1.begin(), v1.end()); printVector(v1); cout << "Before v2 is cleared:"; printVector(v2); //clear v2.clear(); cout << "After clearing v2: "; printVector(v1); } int main() {<!-- --> test04(); return 0; }
operation result:
6. Data access operations
(1) Function: Store and retrieve data in vector.
(2)Method:
1. operator[index];//Similar to [] in an array, returns the data pointed to by index index 2. at(int index);//Use the at function to return the data pointed to by index index 3. front();//Return the first data in the container 4. back();//Return the last element in the container
Example:
#include<iostream> #include<vector> using namespace std; //Print vector void printVector(vector<int> & amp; v) {<!-- --> for (vector<int>::iterator it = v.begin(); it != v.end(); it + + ) {<!-- --> cout << *it << " "; } cout << endl; } void test05() {<!-- --> vector<int> v1; for (int i = 0; i < 10; + + i) {<!-- --> v1.push_back(i); } //Use [] to access elements in the array for (int i = 0; i < v1.size(); + + i) {<!-- --> cout << v1[i] << " "; } cout << endl; //Access elements in the array using at for (int i = 0; i < v1.size(); + + i) {<!-- --> cout << v1.at(i) << " "; } cout << endl; //Get the first element cout << "The first element is:" << v1.front() << endl; //Get the last element cout << "The last element is: " << v1.back() << endl; } int main() {<!-- --> test05(); return 0; }
operation result:
7. Interchangeable containers
(1) Function: Exchange the elements of two containers
(2)Method:
v1.swap(v2);//Swap the elements of v2 with the elements of v1
Example:
#include<iostream> #include<vector> using namespace std; //Print vector void printVector(vector<int> & amp; v) {<!-- --> for (vector<int>::iterator it = v.begin(); it != v.end(); it + + ) {<!-- --> cout << *it << " "; } cout << endl; } void test06() {<!-- --> cout << "Before exchange:" << endl; vector<int> v1; for (int i = 0; i < 10; + + i) {<!-- --> v1.push_back(i); } printVector(v1); vector<int> v2; for (int i = 10; i > 0; i--) {<!-- --> v2.push_back(i); } printVector(v2); cout << "After exchange:" << endl; v1.swap(v2); printVector(v1); printVector(v2); } int main() {<!-- --> test06(); return 0; }
operation result:
Supplementary (important uses):
We can use swap to interchange two containers. Coupled with the nature of anonymous objects, it can be used to achieve the purpose of shrinking memory space. Here’s how:
void test07() {<!-- --> vector<int> v; for(int i = 0; i < 114514; i + + ) {<!-- --> v.push_back(i); } cout << "The capacity of v is:" << v.capacity() << endl; cout << "The size of v is:" << v.size() << endl; //If you simply re-specify the size, the capacity will not change, resulting in unnecessary waste of space. v.resize(25); cout << "Use resize(): " << endl; cout << "The capacity of v is:" << v.capacity() << endl; cout << "The size of v is:" << v.size() << endl; //And we can cleverly use swap() to shrink the memory vector<int>(v).swap(v);//vector<int>(v) creates an anonymous object and will initialize the size of the anonymous object container according to the size of v. //Use swap() to exchange it with the anonymous function. The pointer of the original container points to the container of the anonymous object, and the pointer of the original container of the anonymous object points to the original container. //After the system creates the anonymous function, it will recycle the pointer (address, memory) of the anonymous object cout << "Use swap + anonymous function: " << endl; cout << "The capacity of v is:" << v.capacity() << endl; cout << "The size of v is:" << v.size() << endl; } int main() {<!-- --> test07(); return 0; }
operation result:
8. Reserve space
(1) Function: Open up space in advance to reduce the number of vector expansions when dynamically expanding capacity.
(2) Method:
reserve(int len);//The container reserves len elements in length, the reserved position is not initialized, and the elements are inaccessible
Example:
void test08() {<!-- --> vector<int> v1; int count = 0; int* p1 = NULL; for (int i = 0; i < 114514; i + + ){<!-- --> v1.push_back(i); //Every time the capacity is expanded, a new piece of memory will be opened, and the address pointed to by p is different from the original one, so as to count the number of dynamic allocations. if (p1 != & amp;v1[0]) {<!-- --> p1 = &v1[0]; count + + ; } } cout << "count when no space is reserved: " << count << endl; count = 0; vector<int> v2; v2.reserve(114514); int* p2 = NULL; for(int i = 0; i < 114514; i + + ) {<!-- --> v2.push_back(i); if (p2 != & amp;v2[0]) {<!-- --> p2 = &v2[0]; count + + ; } } cout << "count when reserving space: " << count << endl; } int main() {<!-- --> test08(); return 0; }
operation result:
vector summary
- The vector container is one of the most commonly used containers, and most of the time it is needed to store data.
- Operations such as constructors, element access, two-dimensional containers, traversal acquisition, insertion and deletion are relatively common.
- Basically, [] is commonly used to obtain, access, and construct anonymous constructs and specified size constructs, and push_back() is also commonly used.
- Pay attention to the access of iterators, because it can point directly to memory and is more flexible.
- The memory principles in construction and assignment operations need to be mastered. When expanding, the mechanism is to reopen a new space and point the pointer again.
- The address and memory of anonymous objects will be automatically reclaimed by the system, so you can use swap and anonymous objects to shrink the space. Also note that reserved space can reduce the number of dynamic expansion and opening times.
The above is all about the common operations and principles of vector containers. If there are any errors in the article or you encounter any problems, please feel free to contact me at any time.