C++ [Use of vector in STL]

The use of vector in STL


This article has been included in the “C++ Language and Advanced Data Structures” column!
Author: ARMCSKGT



Use of vector in STL

  • foreword
  • text
    • default member function
      • common structure
      • copy construction
      • destructor
      • assignment overloading
    • iterator
      • forward iterator
      • reverse iterator
      • const iterator
    • capacity class
      • Space capacity query
      • Space Capacity Operations
        • Expansion operation
        • Number of Elements Operations
        • Shrink operation
    • data access
      • subscript access
      • Head and tail element access
      • get raw pointer
    • Element insertion and deletion operations
      • Tail plug and tail delete
      • Insert and delete at any position
      • insert anywhere
      • delete anywhere
    • Other operation functions
      • exchange function
      • clear function
  • at last

Foreword

vector is a variable-sized array sequence container, generally also called a vector; the underlying principle is a sequence table, but vector is a generic container that can support storage of int, double and even custom types, and is frequently and widely used in normal times , vector can improve our development efficiency in many scenarios, so it is necessary to learn how to use vector as a powerful tool!
vector

Text

This article will introduce the common interface of vector, according to the official document of C++ vector!
First, before using vector, you need to declare the header file < vector > and declare the namespace std!
Vector is a generic container through a template instance, which needs to be instantiated by specifying the type!

Default member function

There are three conventional constructions for vector, but in C++11, a useful construction method has been added!
vector default member function

Common structure

vector supports the following constructs:

  • Default construction (generates an empty container object without any data)
  • Construct n objects whose elements are val
  • iterator range construction
  • List initialization construction
#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v1; //Default construction

vector<int> v2(5, 10); //Construct 5 objects with 10 elements

int arr[] = {<!-- --> 1,2,3,4,5 };
vector<int> v3(arr, arr + (sizeof(arr) / sizeof(arr[0]))); //iterator interval construction

vector<int> v4 = {<!-- --> 6,7,8,9,10 }; //List initialization construction

return 0;
}

constructor

Copy construction

When we define an object, we can let the new object copy an existing object to complete the initialization!

#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v1(10, 1);

//Two copy construction methods
vector<int> v2(v1);
vector<int> v3 = v1;

return 0;
}

copy structure

Destructor

The destructor is automatically called at the end of the vector object’s life cycle, and we don’t need to care about the use phase!

Assignment overload

vector supports assignment to copy an object (provided that the object already exists and not constructed), and C++11 supports assignment through list initialization!

Assignment overload

#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v1 = {<!-- -->1,2,3};
vector<int> v2;
v2 = v1; //Assign empty object

vector<int> v3 = {<!-- --> 4,5,6 };
v3 = {<!-- -->10,11,12}; //Assign objects with existing data through the list

return 0;
}

Assignment overload
It can be found that when there is data in the object, the assignment to it will reflect the original data, and the vector object can also be initialized through the list!

Iterator

  • vector supports two kinds of iterators forward and reverse (C++ 11), both of which have const versions!
  • The iterator is to encapsulate the pointer and construct it into an iterator object, and control the operable behavior by yourself!
  • The iterator of vector is a random iterator, which can ± any integer to any element while supporting ++ and – -, so sort can be used!
    iterator

Forward iterator

Forward iterator traversal, the default is from begin() to end()!
begin points to the position of the first element in the vector, and end points to the next position of the last element!
begin and end

You cannot use > and < etc. when judging the end condition, because after the iterator is encapsulated, you don’t know whether it is a continuous space, just judge whether it is equal to end!

#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v = {<!-- --> 1,2,3,4,5 };
vector<int>::iterator it = v.begin(); //Define vector<int>iterator type
//auto it = v.begin(); //If you feel troublesome, you can also use auto
while (it != v. end())
{<!-- -->
cout << *it << " ";
+ + it;
}
cout << endl;
return 0;
}

Forward iterator

Reverse iterator

As the name suggests, the opposite of a forward iterator!
rend points to the previous position of the first element in the vector, and rbegin points to the position of the last element!
rbegin and rend

#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v = {<!-- --> 1,2,3,4,5 };
vector<int>::reverse_iterator rit = v.rbegin();
while (rit != v. rend())
{<!-- -->
cout << *rit << " ";
+ + rit;
}
cout << endl;
return 0;
}

Reverse iterator
The ++ of the reverse iterator is to go from the back to the front, which is the opposite of the behavior of the forward iterator!

const iterator

In some scenarios such as:

//vector object const reference parameter, the iterator declared in the function is a const iterator
void Print(const vector<int> & v) {<!-- -->}

// When the range for uses const to modify the element, the bottom layer calls the const iterator
for (const auto & x : v) {<!-- -->}

Usually we rarely use const iterators, but we can also actively define them!

vector<int>::const_iterator //const forward iterator
vector<int>::const_reverse_iterator ///const reverse iterator

A const iterator cannot modify the element pointed to by the iterator, but it can change the point of the iterator!

Capacity class

Operations on capacity query and modification:
capacity class

Space capacity query

Vector supports the following capacity query operations:

  • Query the number of elements size
  • Query the current capacity capacity
  • Query whether the current object is empty (no element exists) empty
  • The query object can hold the maximum number of elements (estimated, not exact) max_size
#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v = {<!-- --> 1,2,3 };
cout << "size:" << v. size() << endl;
cout << "capacity:" << v. capacity() << endl;
cout << "empty:" << (bool)v.empty() << endl;
cout << "max_size:" << v.max_size() << endl;
return 0;
}

Capacity query
The max_size will change due to factors such as different instance types and different platforms!
max_size

Space capacity operation

Expansion operation

Vector supports manual capacity expansion using the reserve function. In some scenarios where the number of elements is known, space can be opened up in advance to improve performance and reduce memory fragmentation!

First, let’s take a look at vector’s own expansion mechanism:

VS platform (PJ version)
VS platform
g++ platform (SGI version)
g++ platform
Through observation, we found that the expansion under VS is 1.5 times, and the expansion under g++ is 2 times; these two expansion strategies have their own advantages and disadvantages. When the amount of data is relatively large, frequent expansion of VS will lead to performance degradation; when the amount of data At medium, g++ expands redundancy too much and wastes space!

In response to this situation, we can use reserve to expand capacity in advance to avoid these two situations!

vector<int> v;
v.reverse(n); //Expand the capacity to n in advance

Example:

#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v;
v. reserve(100);
cout << "capacity:" << v. capacity() << endl;
v.reserve(50); //reserve does not support shrinkage
cout << "capacity:" << v. capacity() << endl;
return 0;
}

reserve

Number of elements operation

Vector supports the use of the resize function to customize the number of elements. If the number we set is greater than the current capacity, it will trigger expansion!

#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v = {<!-- -->1,2,3};
cout << "size:" << v. size() << endl;
cout << "capacity:" << v. capacity() << endl;
\t
v. resize(50);
cout << "size:" << v. size() << endl;
cout << "capacity:" << v. capacity() << endl;

v. resize(10);
cout << "size:" << v. size() << endl;
cout << "capacity:" << v. capacity() << endl;

return 0;
}


Obviously, resize changes the size of the size, no matter what, it will not shrink!
If in resize(n), n is greater than the current size, the newly increased space will be initialized with the default construction of the instantiated type!
resize
resize
In order to be compatible with custom types, built-in types also support initialization and construction like defining objects, which is to construct through int(), just like anonymous objects, except that int() is equivalent to 0!

int main()
{<!-- -->
int a(1); //object initialization method
int b = int(2); //Anonymous object copy construction method
cout << a << endl;
cout << b << endl;
return 0;
}

Built-in type initialization

Of course resize also supports the specified value to initialize the growth space

#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v = {<!-- -->1,2,3};
v.resize(10,668); //Specify to initialize the new element space as 668
return 0;
}

resize(668)
Equivalent to reserve, resize can not only expand capacity, but also complete initialization. Both have their own application scenarios!

Scale down operation

C++11 provides shrinking operations for containers. The shrink_to_fit function is rarely used in normal times, because it consumes a lot of performance!

vector<int> v(100,1);
v.shrink_to_fit(10); //Reduce the capacity to 10

The underlying principle is probably to re-open up a space of appropriate size and transfer data according to the free space!
shrink_to_fit

Data Access

Vector is a sequential table, and there are many ways to range it. In addition to the general iterator range, there are the following ways to access data:
Access

Subscript access

The bottom layer of vector is a sequential table, so it must support subscript random access!
There are two ways to access subscripts. On the basis of native access through [], there is also an at() in the library that can also be accessed through subscripts. The difference between the two is:

  • Access through [ ], if the subscript is out of bounds, error will be reported
  • Access through at() will throw an exception if the subscript is out of bounds
#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v = {<!-- -->1,2,3};
for (int i = 0; i < v. size(); + + i)
{<!-- -->
printf("v[%d]=%d，v.at(%d)=%d\\
",i, v[i], i, v.at(i));
}
return 0;
}

Subscript access

Head and tail element access

Vector supports the reference or const reference of the head and tail elements, and it is rarely used at ordinary times, just understand it!
front and back

#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v = {<!-- --> 1,2,3 };
cout << v. front() << endl;
cout << v.back() << endl;
return 0;
}

front and back

Get native pointer

Vector supports obtaining the direct native space of storage elements through the data function!
Through this pointer, like accessing an array, use subscript access or * dereference to access and modify the elements of each space!
This is rarely used, and it is very dangerous, so it is not recommended to use it! 

#include <iostream>
#include <vector>
using namespace std;

int main()
{<!-- -->
vector<int> v = {<!-- --> 1,2,3 };
int* p = v. data();
p[1] = 4;
for (const auto & x : v)
{<!-- -->
cout << x << endl;
}
return 0;
}

data

Element insertion and deletion operations

Vector has many operation functions for modifying elements, but we only need to understand the most commonly used ones!
Common insertion and deletion

Tail insertion and deletion

  • The push_back(val) function can insert val into the end of the current vector container
  • The pop_back() function can delete an element from the end of the current container
#include <iostream>
#include <vector>
using namespace std;

void Print(const vector<int> & v)
{<!-- -->
for (const auto & x : v)
{<!-- -->
cout << x << " ";
}
cout << endl;
}

int main()
{<!-- -->
vector<int> v = {<!-- --> 4,5,6 };
v. pop_back();
Print(v);
v. push_back(668);
Print(v);
return 0;
}

End at the end and delete at the end

Insert and delete at any position

Add or delete at any location

Insert anywhere

The insert function has three forms and supports:

  • Insert a val element at the current iterator position (equivalent to inserting an element before an element) and return the iterator of the newly inserted element
    – This return value is crucial! When we insert an element, expansion may be triggered, then the original iterator will become invalid (the iterator becomes invalid), and insert will return a new iterator pointing to the inserted element to facilitate subsequent operations!
  • Insert n elements val elements at the current iterator position, no return value
  • Insert the iterator interval of any container at the current iterator position, no return value
    – For these two functions, the iterator must be manually updated after insertion, otherwise the compiler will report an error! 
#include <iostream>
#include <vector>
using namespace std;

void Print(const vector<int> & v)
{<!-- -->
for (const auto & x : v)
{<!-- -->
cout << x << " ";
}
cout << endl;
}

int main()
{<!-- -->
vector<int> v = {<!-- --> 4,5,6 };
v.insert(v.begin(), 1); //head insert 1
Print(v);

v.insert(v.begin(), 2); //head insert 1
Print(v);

v.insert(v.begin() + 2, 2, 668); //Insert two 668 before element 2
Print(v);

int arr[] = {<!-- --> 9,6,3 };
v.insert(v.begin() + 1, arr, arr + (sizeof(arr) / sizeof(arr[0]))); // Insert an array before element 1
Print(v);

return 0;
}

insert

Delete anywhere

There are two forms for erasing any position:

  • Delete the element pointed by the current iterator, and return the element iterator after this element
  • Delete an iterator range of the container, and return an iterator of the next element in the range
    –The deletion operation will inevitably cause the iterator to become invalid, so each deletion operation will update the iterator! 
#include <iostream>
#include <vector>
using namespace std;

void Print(const vector<int> & v)
{<!-- -->
for (const auto & x : v)
{<!-- -->
cout << x << " ";
}
cout << endl;
}

int main()
{<!-- -->
vector<int> v = {<!-- -->1,2,3,4,5,6,7,8,9,10};
Print(v);
v.erase(v.begin()); //head delete
Print(v);
v.erase(v.begin() + 2, v.begin() + 7); //Delete elements 2-7
Print(v);
return 0;
}

erase
Deletion consumes a lot of performance, because it involves moving data, and it is not used much at ordinary times!

Other operation functions

Exchange function

Vector has its own exchange function, and its bottom layer is the space managed by both sides of the exchange!

#include <iostream>
#include <vector>
using namespace std;

void Print(const vector<int> & v)
{<!-- -->
for (const auto & x : v)
{<!-- -->
cout << x << " ";
}
cout << endl;
}

int main()
{<!-- -->
vector<int> v1 = {<!-- --> 1,2,3,4,5 };
vector<int> v2 = {<!-- --> 6,7,8,9,10 };
v1. swap(v2);
Print(v1);
Print(v2);
return 0;
}

swap
Of course, vector also supports the unified swap function in the library, but it needs to declare the algorithm header file algorithm to use it!

#include <iostream>
#include <vector>
#include <algorithm> //algorithm header file
using namespace std;
int main()
{<!-- -->
vector<int> v1 = {<!-- --> 1,2,3,4,5 };
vector<int> v2 = {<!-- --> 6,7,8,9,10 };
swap(v1,v2);
return 0;
}

Empty function

The clear function can clear all the elements of the current vector object, but it will not shrink or destroy the object! 

#include <iostream>
#include <vector>
using namespace std;

void Print(const vector<int> & v)
{<!-- -->
for (const auto & x : v)
{<!-- -->
cout << x << " ";
}
cout << endl;
}

int main()
{<!-- -->
vector<int> v = {<!-- --> 1,2,3,4,5 };
cout << "size:" << v. size() << endl;
cout << "capacity:" << v. capacity() << endl;
v. clear();
cout << "size:" << v. size() << endl;
cout << "capacity:" << v. capacity() << endl;
return 0;
}

clear

Last

This is the end of the introduction to the use of vector. Vector is a powerful generic sequence table, which makes up for the shortcomings of arrays that cannot be dynamically expanded, and the generic idea allows vector to be instantiated into any type of sequence table, but In fact, there is only one code; later I will reveal the secrets of the bottom layer of vector for you, and introduce the bottom layer implementation of vector!

This time will be introduced here first, I hope it can help everyone as much as possible.

If there are flaws in the article, please comment and leave a message carefully, and I will fix the mistakes immediately, thank you!

end


Other articles reading recommendation
C ++ -CSDN Blog
C ++ -CSDN Blog
C++ -CSDN blog
C++