[C++]vector

---

I. Introduction to vector

Introduction to vector documentation Most of the usage is similar to that of string A vector is similar to a sequential table, which is a dynamically growing array. Header file: #include < vector >

1. vector is a representation of thevariable-size arrayof the serial container.
2. Like arrays, vectors use contiguous storage to store elements. This means that the elements of a vector can be accessed using subscripts, which is just as efficient as an array. But unlike an array, its size can be changed dynamically, and its size is automatically handled by the container.
3. Essentially, a vector uses a dynamically allocated array to store its elements. When a new element is inserted, the array needs to be reallocated in order to increase storage space. This is done by allocating a new array and then moving all the elements into it. This is a relatively costly task in terms of time because the vector is not reallocated every time a new element is added to the container.
4. vector allocation space strategy: vectors allocate some extra space to accommodate possible growth because the storage space is larger than the actual storage space needed. Different libraries use different strategies to weigh space usage and reallocation. But in any case, reallocations should be logarithmically growing interval sizes such that inserting an element at the end is done in constant time complexity.
5. As a result, vectors take up more storage space, in order to gain the ability to manage storage space and grow dynamically in an efficient way.
6. Compared to other dynamic sequence containers (deque, list and forward_list), vectors are more efficient at accessing elements and relatively efficient at adding and removing elements at the end. It is less efficient for other delete and insert operations that are not at the end. Better than list and forward_list unified iterators and references

Second, vector’s common interface description

2.1 Use of vector

A vector can store any type of data Code Showcase:

vector<int> v1; // can be of type int or any type
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);

	vector<string> v2;//can be of type string
	v2.push_back("easy");
	v2.push_back("Junkai Wang");
	v2.push_back("wang yuan");

	vector<int> v3;
	v3 = v1;

	vector<double> v4(10, 1.2);// 10 1.2 for initialization
	// Can be initialized with iterator intervals
	vector<string> v5(++v2.begin(), v2.end());
	// initialize v5 from the second to the last of v2

	string s = "hello world";
	vector<char> v6(s.begin(), s.end());
	// can be an iterator of any type, not necessarily of its own type

Note: allocator is a space allocator, which is actually a memory pool. You can also write your own space allocator.

2.2 vector iterator Usage

Iteration of vectors

vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	//vector traversal
	//1.[]
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
	//2. Iterators
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	//3. Range for
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

2.3 The vector space growth problem

max_size()

• The code for capacity will be run under vs and g++ respectively, and you will find that capacity grows by a factor of 1.5 under vs, and by a factor of 2 under g++. This issue is often examined, do not solidify that the vector capacity increase are 2 times, the specific growth of how much is based on the specific needs of the definition. vs is the PJ version of STL, g + + is the SGI version of STL.
• reserve is only responsible for opening up space, and if you know for sure how much space you need to use, reserve can alleviate the problem of costly defects in vector augmentation.
• resize will also initialize while opening space, affecting size. (Open space + initialization can be done with resize()）
• When a string or vector is deleted, the data is not shrunk (capacity).

The more you add capacity in a single pass and the fewer times you add capacity, the more efficient it will be, but the more space you may waste. (If you know how much space to open you can use reverve()) shrink_to_fit shink_to_fit will make the capacity the same as size, but this function needs to be used with caution because instead of giving some of the space back to the operating system, all of the space is given back to the operating system and a new piece of space is opened up to put the data into.

2.4 vector Add, Delete, Check, and Change

insert vector does not support subscript insertion, only iterators; string supports subscript insertion. vector is no header insertion, can use insert for header insertion. insert also supports tail insertion. If you exceed the tail insertion, you can’t, it will be out of bounds access, and compilation error will occur.

vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.insert(v.begin(), -1);//equivalent to header insertion
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.insert(v.begin() + 5, 20);//equivalent to tail insertion
	//v.insert(v.begin() + 7, 30);//this line of code, will report an error
	// At this time there are a total of 6 data, if the eighth position inserted is not allowed, not to cross the line
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

erase Note: this is also an iterator [note: no crossing of boundaries] find vector and list do not have a find function, the reuse of the algorithm inside the find() function The find() function supports a segment of iterator intervals to find a value, and returns last if it doesn’t find one…[so, it’s a forward-closed-backward-open interval]; the header file is #include < algorithm > algorithm Delete 3->Find 3 this position first->Delete Code Showcase:

vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	// Find
	vector<int>::iterator pos = find(v.begin(), v.end(),3);
	//auto pos = find(v.begin(), v.end(), 3);//this one is more convenient
	if (pos != v.end())
	{
		cout << "found" << endl;
		v.erase(pos);
	}
	else
	{
		cout << "Not found" << endl;
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

sort

• sort works for vectors, it works for other containers, but some don’t (lists)
• sort is ascending by default, if you want descending, you need to imitate the function [header file #include < functional >]. Code Showcase：

vector<int> v;
	v.push_back(1);
	v.push_back(0);
	v.push_back(5);
	v.push_back(8);
	v.push_back(4);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	// Default ascending order
	sort(v.begin(), v.end());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	// imitation function, descending
	sort(v.begin(), v.end(), greater<int>());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

---

III. Summary

The above is the content of today’s talk, this article describes in detail the use of vector, the use of vector iterator, vector space growth issues, vector add, delete, check and change. I hope to bring help to friends!