1. string container

Please click to jump to this chapter

2. vector container

2.1 basic concept of vector

Function:

• vector data structure is very similar to array, also known as single ended array

The difference between vector and ordinary array:

• Array is static space (the capacity is fixed and cannot be changed after definition)
• vector can be extended dynamically

Dynamic expansion:

• Instead of adding a new space after the original space, find a larger memory space, and then copy the metadata to the new space to release the original space
• The iterator of the vector container is an iterator that supports random access

2.2 vector constructor

Function Description:

• Create vector container

Function prototype:

• vector<T> v;// Using template implementation class implementation, default constructor
• vector(v.begin(), v.end());// Copy the elements in the [v.begin(), v.end()) interval to itself
• vector(n, elem);// The constructor copies n elems to itself
• vector(const vector& vec);// copy constructor

#include<vector>

void printVector(vector<int>& v)
{
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	vector<int>v1;//Default construction, parameterless construction
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	//It is constructed by interval
	vector<int>v2(v1.begin(), v1.end());
	printVector(v2);

	//n elem ent mode construction
	vector<int>v3(10, 100);//10 100
	printVector(v3);

	//Copy structure √
	vector<int>v4(v3);
	printVector(v4);
}

2.3 vector assignment

Function Description:

• Create vector container

Function prototype:

• vector& operator= (const vector & vec);// Overloaded equal sign operator
• assign(beg, end);// Assign the data copy in the [beg, end) interval to itself
• assign(n, elem);// Assign n elem copies to itself

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

void printVector(vector<int>& v)
{
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	//assignment
	//Method 1 operator=
	vector<int>v2;
	v2 = v1;
	printVector(v2);

	//Method 2 assign
	vector<int>v3;
	v3.assign(v1.begin(), v1.end());//Front closing and rear opening
	printVector(v3);

	//Method 3 assign
	vector<int>v4;
	v4.assign(10, 100);//10 100
	printVector(v4);
}

2.4 vector capacity and size

Function Description:

• Operation on the capacity and size of the vector container

Function prototype:

• empty();// Determine whether the container is empty
• capacity();// Capacity of container
• size();// Returns the number of elements in the container (capacity ≥ size)
• resize(int num);// Reassign the length of the container to num. If the container becomes longer, fill the new position with the default value; If it becomes shorter, the element whose end exceeds the length of the container is deleted
• resize(int num, elem);// Reassign the length of the container to num. If the container becomes longer, fill the new position with elem value; If it becomes shorter, the element whose end exceeds the length of the container is deleted

void printVector(vector<int>& v)
{
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	//Determine whether the container is empty
	if (v1.empty())//True: indicates that the container is empty
	{
		cout << "v1 Empty" << endl;
	}
	else
	{
		cout << "v1 Not empty" << endl; 
		cout << "v1 The capacity of the is:"  << v1.capacity() << endl;//13
		cout << "v1 The size of the is:" << v1.size() << endl;//10
	}

	//Reassign size
	v1.resize(15);
	printVector(v1);// 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 
	v1.resize(16, 100);
	printVector(v1);// 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 100
	v1.resize(5);
	printVector(v1);// 0 1 2 3 4 
}

2.5 vector insertion and deletion

Function Description:

• Insert and delete the vector container

Function prototype:

• push_back(ele);// Tail insert element ele
• pop_back();// Delete last element
• insert(const_iterator pos, ele);// The iterator points to the position POS and inserts the element ele
• insert(const_iterator pos, int count, ele);// The iterator points to the position POS and inserts count elements ele
• erase(const_iterator pos);// Delete the element pointed to by the iterator
• erase(const_iterator start, const_iterator end);// Delete the elements of the iterator from start to end
• clear();// Delete all elements in the container

void test01()
{
	vector<int>v1;

	//Tail insertion
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);
	//ergodic
	printVector(v1);//10 20 30 40 50

	//Tail deletion
	v1.pop_back();
	printVector(v1);//10 20 30 40

	//insert
	v1.insert(v1.begin(), 100);//The first parameter is the iterator
	printVector(v1);//100 10 20 30 40

	v1.insert(v1.begin(), 2, 1000);
	printVector(v1);//1000 1000 100 10 20 30 40

	//delete
	v1.erase(v1.begin());//Parameters are also iterators
	printVector(v1);//1000 100 10 20 30 40

	v1.erase(v1.begin()+1, v1.end());
	printVector(v1);//1000

	//empty
	v1.clear();
}

2.6 vector data access

Function Description:

• Access to data in the vector container

Function prototype:

• at(int idx);// Returns the data indicated by the index idx
• operator[];// Returns the data indicated by the index idx
• front();// Returns the first data element in the container
• back();// Returns the last data element in the container

void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}

	//Access the elements in the array in [] mode
	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";
	}
	cout << endl;// 0 1 2 3 4 5 6 7 8 9

	//Accessing elements in at mode
	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1.at(i) << " ";
	}
	cout << endl;

	//Get the first element
	cout << v1.front() << endl;//0

	//Get the last element
	cout << v1.back() << endl;//9
}

2.7 vector interchange container

Function Description:

• Realize the exchange of elements in two containers

Function prototype:

• swap(vec); Swap VEC with its own elements

Basic usage:

void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);// 0 1 2 3 4 5 6 7 8 9

	vector<int>v2;
	for (int i = 10; i > 0; i--)
	{
		v2.push_back(i);
	}
	printVector(v2);//10 9 8 7 6 5 4 3 2 1

	//The elements of the two containers are interchanged
	v1.swap(v2);
	printVector(v1);//10 9 8 7 6 5 4 3 2 1
	printVector(v2);//0 1 2 3 4 5 6 7 8 9
}

Practical use: (smart use of swap can shrink memory space)

vector<int>v;
for (int i = 0; i < 100000; i++)
{
	v.push_back(i);
}
cout << "v The capacity of the is:" << v.capacity() << endl;//138255
cout << "v The size of the is:" << v.size() << endl;//100000


v.resize(3);//Reassign size
cout << "v The capacity of the is:" << v.capacity() << endl;//138255
cout << "v The size of the is:" << v.size() << endl;//3
//Waste of memory!

//Shrink memory with swap
vector<int>(v).swap(v);
cout << "v The capacity of the is:" << v.capacity() << endl;//3
cout << "v The size of the is:" << v.size() << endl;//3

vector<int>(v). swap(v); Can greatly reduce memory waste. The principle is: vector < int > (V) for an anonymous object, create a new object without a name, and initialize it with V, so the capacity and size of the new anonymous object are the same as that of V, and then Swap (V) is an element of the exchange container, so the size and capacity of V change at this time. At this time, the anonymous object points to the large memory space, but the compiler will automatically release the anonymous object.

2.8 reserved space for vector

Function Description:

• Reduce the expansion times of vector when dynamically expanding capacity

Function prototype:

• reserve(int len);// The container reserves len element lengths. The reserved positions are not initialized and the elements are inaccessible

vector<int>v;

int num = 0;//Count the number of newly opened memory (dynamic expansion)
int* p = NULL;
for (int i = 0; i < 10000; i++)
{
	v.push_back(i);
	if (p != &v[0])
	{
		p = &v[0];
		num++;
	}
	//When you reopen more memory,
	//The pointer points to the first address of the original memory instead of the current memory,
	//So num + + shows that a new piece of memory has been opened up
}
cout << num << endl;//24

When the amount of data is large, it is troublesome to constantly open up new memory, that is, repeat dynamic expansion. Therefore, reserve can be used to reserve space at the beginning, as follows:

vector<int>v;

//Reserve space with reserve
v.reserve(10000);

int num = 0;//Count the number of newly opened memory (dynamic expansion)
int* p = NULL;
for (int i = 0; i < 10000; i++)
{
	v.push_back(i);
	if (p != &v[0])
	{
		p = &v[0];
		num++;
	}
}
cout << num << endl;//1

[to be continued]