Introduction and use of vector

【 Write it at the front 】

Compared with string,vector Is easier to use , And its interface is better than string Much less , Plus we've learned something similar string, And the sequence table in the data structure chapter has already touched on .vector It is also very important in practice , In practice, we can be familiar with common interfaces .
stay vector From the beginning, we can try to have a look STL The source of the ,string Why didn't you see it , As I said before , about string Is in STL This specification was designed before . Our source code mainly refers to P.J Version and SGI edition .

What do you think

1. P.J

   Debug the following code after the break point , You can view it in a single step
   
   Visual Studio 2017 Refer to the following table of contents ：
   
   But for P.J Some parts of the version also cover C++11 The optimization of the , You may not understand , So we mainly refer to SGI edition .

2. SGI

   Here is a Book 《STL Source analysis 》, It uses STL3.0 Version of , Students in need can send a private e-mail version . Of course, we will learn the core content of this book .
   

stl3.0 List

1. After unpacking , find vector And open
   

2. find stl_vector.h And open ( The core code is 500 Multiple lines )

   

3. How to read

   as everyone knows , Looking at other people's code is a very painful thing , If his level is higher than yours , Then you can grow , But don't look at it line by line , This will cause you to see only the trees and not the forest . Remember here “ This principle ”, One 1000 Lines of code , Only 200 Line is the core , Just put this 200 OK, I understand , Then you will understand .

4. The core code is simply filtered as follows

   Documents to be consulted ：vector stl_vector.h stl_construct.h

vector

#include <stl_algobase.h>#include <stl_alloc.h>#include <stl_construct.h>#include <stl_uninitialized.h>#include <stl_vector.h>#include <stl_bvector.h>

stl_vector.h

// The template here gives default parameters , Which means that it's OK not to pass it on .Alloc It's the space configurator , Is a memory pool to apply for and free space , We just use new It's OK , It's just that the memory pool is a little more efficient template <class T, class Alloc = alloc>class vector {public:	typedef T value_type;	typedef value_type* iterator;protected:	// Why don't you see the pointer here 、size、capacity Things like that ? ————  We can have a look at iterator What is it ( stay public It has been indicated in the )	// So here are three T* The pointer to 	iterator start; 	iterator finish; 	iterator end_of_storage;public:	// Secondly, you can also look at its constructor , It's done right 3 Initialization of member variables 	vector() : start(0), finish(0), end_of_storage(0) {}	// Next, look at push_back The implementation of the 	// At this stage, we still have some difficulties in looking at the source code , We will dig deeply later  	void push_back(const T& x) { 	// It means that it is not full     if (finish != end_of_storage) {    // This is not a direct assignment , But the call construct, The reason here is to call the constructor initialization for an existing space display , We are stl_vector.h No implementation found in     // In fact, it is necessary to combine vector Come to see , We have a bunch of header files on it , Then its implementation must be in stl_vector.h In the header file above ————stl_construct.h      construct(finish, x);// How to achieve ?      ++finish;    }    // Full of , increase capacity     else      insert_aux(end(), x);// How to achieve ?  }}

stl_construct.h

//construct It's a function template 2template <class T1, class T2>inline void construct(T1* p, const T2& value) {  new (p) T1(value);// location new expression }

Add

For sequence tables , Although it was renamed vector 了 , But its implementation is much the same as the previous understanding .

One 、vector The introduction and use of

vector Introduction to

vector Documentation of

1. vector Is a variable size array sequence Containers
2. It's like an array ,vector It also uses continuous storage space to store elements . That means subscript pairs can be used vector Element to access , As efficient as arrays . But it's not like an array , Its size can be changed dynamically , And its size is automatically handled by the container
3. Essence ,vector Use a dynamic allocation array to store its elements . When a new element is inserted , This array needs to be resized to increase storage space . This is done by , Assign a new array , Then move all the elements to this array . In terms of time , This is a relatively expensive task , Because every time a new element is added to the container ,vector It doesn't re size every time
4. vector Space allocation strategy ：vector Some extra space will be allocated to accommodate possible growth , Because the storage space is larger than the actual need . Different libraries use different strategies to balance space use and reallocation . But anyway , Reallocation should be the interval size of the array growth , So that inserting an element at the end is done in constant time complexity
5. therefore ,vector It takes up more storage space , To get the ability to manage storage space , And grow dynamically in an effective way
6. Compared with other dynamic sequence containers (deques,lists and forward_lists), vector More efficient when accessing elements , Adding and removing elements at the end is relatively efficient . For other delete and insert operations not at the end , Less efficient . Compared with lists and forward_lists Uniform iterators and references are better

vector Use

1、vector The definition of

(constructor) Constructor declaration	Interface specification
vector()	No arguments structure
vector(size_type n, const value_type& val = value_type())	Construct and initialize n individual val
vector(const vector& x)	Copy structure
vector(InputIterator first, InputIterator last)	Use iterators for initialization construction

explain

• default(1)
  Here is a default value , At this stage, we just need to see alloc You can just ignore it , It is STL Space configurator in six components .

• fill(2)
  value_type Is the first template parameter , It's a \0
  

• range(3)
  The iterator here is also a function template , The iterator is not necessarily here vector The iterator

#include<iostream>#include<vector>#include<string>using namespace std;void test_vector1(){	vector<int> v;   	// stay C In the implementation of data structure, our code style is hump method , and STL The overall style is lowercase and underline separated style 	v.push_back(1);	v.push_back(2);	v.push_back(3);	v.push_back(4);	v.push_back(5);	// Traverse vector	//1、operator[]	for(size_t i = 0; i < v.size(); ++i)	{		v[i] -= 1;		cout << v[i] << " ";		}	cout << endl;	//2、 iterator 	vector<int>::iterator it = v.begin();	while(it != v.end())	{		*it += 1;		cout << *it << " ";			++it;	}	cout << endl;	//3、 Range for	for(auto& e : v)	{		++e;		cout << e << " ";		}	cout << endl;		// Why vector, There will be more string Well 	//vector Li Gei char, Although they are stored in an array at the bottom char, But it's still different 	// comparison T yes char Of vector,s The space pointed to in the object ends with \0, This conforms to many specifications , For example, you need to play strstr、strcpy etc. , and vector Can't play += String, etc. 	// So T yes char Of vector Can't replace string 	string s("111111");	vector<char> vc(6, '1');	// You can use an iterator interval to construct , This section can also be controlled , And this is a deep copy ( All that have their own independent space should be copied deeply )	vector<int> v1(v.begin(), v.end());	vector<int> v2(++v.begin(), --v.end());	// Iterators of other containers can be used to construct , As long as the data type can match (*iterator The type of object is the same as vector The data types stored in are consistent )	string s1("hello world");	vector<char> v3(s1.begin(), s1.end());	//vector<char*> v3(s1.begin(), s1.end());//err, from char The switch to char*	// How to achieve 	/*template<class InputIterator> vector(InputIterator first, InputIterator last) { while(first != last) { push_back(*first); ++first; } }*/	// Copy structure 	vector<int> v4(v);}int main(){	test_vector1();	return 0;}

Add

1. List item
   
   Here we find a problem , When we use containers , Don't care about destructions , Because out of scope, it automatically calls , But you have to know the value of destructors .

2. List item

   vecor There is no design write time copy ,string It is possible that , And I said before STL On the container , Copy on write is also flawed , So it's not particularly mainstream ,g++ I have used , But it seems that I gave up ( This will be verified later )

2、vector iterator Use

Interface	explain
begin+end	Get the... Of the first position iterator/const_iterator, Get the next location of the last data iterator/const_iterator
rbegin+rend	Get the last data location of reverse_iterator, Get the previous location of the first data reverse_iterator

#include<iostream>#include<vector>using namespace std;void test_vector1(){	vector<int> v;   	v.push_back(1);	v.push_back(2);	v.push_back(3);	v.push_back(4);	v.push_back(5);	//begin+end, Here and string Very similar , It can be said that an iterator is a pointer 	vector<int>::iterator it = v.begin();	while(it != v.end())	{		cout << *it << " ";			++it;	}	cout << endl;	//rbegin+rend,rbegin(rit) Point to 5,rend Point to 1,++rit How could you walk backwards 	// here rit It is no longer a native pointer , It is an encapsulated class object , heavy load operator++, Can achieve ++rit It's going the other way , The details will be explained later 	// So that's why iterators don't have to be ( Native ) The reason for the pointer 	vector<int>::reverse_iterator rit = v.rbegin();	while(rit != v.rend())	{		cout << *rit << " ";		++rit; 	}	cout << endl;}int main(){	test_vector1();	return 0;}

Add

3、vector Spatial growth problem

Capacity space	Interface specification
size	Get the number of data
capacity	Get capacity size
empty	Determine whether it is null
resize	change vector Of size
reserve	change vector Put in capacity

#include<iostream>#include<vector>using namespace std;void test_vector1(){	vector<int> v;   	// Open space , Change capacity , If you're sure you know how much space you need ,reserve Can ease vector The cost of capacity expansion 	v.reserve(10);	/* err, Wrong access , Before string It is explained in operator[] Will check whether the subscript is less than size,[] Only go to the right size Use of data within  for(size_t i = 0; i < 10; ++i) { v[i] = i; } */	//ok, Visit... Correctly 	for(size_t i = 0; i < 10; ++i)	{		v.push_back(i);		}		// Open space + Default initialization ,resize It will affect size	v.resize(20);		// Open space + Specified initialization 	v.resize(20, 1);}int main(){	test_vector1();	return 0;}

Add

1. List item

   operator[] and at The difference between

   Their functions are similar , The difference is ：operator[] It's rough to cross the boundary , If the subscript is greater than or equal to size, It directly asserts an error , And stop the program ; and at If an error is reported, an exception will be thrown , After the capture , It doesn't just abort the program .

2. List item

   stay string It is also explained in . here vector Of capacity Code in vs and g++ Running separately will find that ：vs Next capacity Is in accordance with the 1.5 Multiplied by , And the initial capacity here is 0;g++ Is in accordance with the 2 Multiplied by , And the initial capacity here is also 0. This problem is often examined , Don't take it for granted that , The capacity increase of the sequence table is 2 times , How much growth is defined by specific needs .vs yes PJ Version of STL,g++ yes SGI Version of STL.

4、vector Add or delete check change

vector Add or delete check change	Interface specification
push_back	Tail insertion
pop_back	Deletion at the end
find	lookup ( Note that this is the implementation of the algorithm module , No vector Member interface of )
insert	stay position Insert before val
erase	Delete position Location data
swap	Two exchanges vector Data space of
operator[]	Access like an array

#include<iostream>#include<vector>#include<algorithm>#include<functional>using namespace std;void test_vector1(){	std::vector<int> first;	std::vector<int> second;	std::vector<int> third;	//assign New content can be assigned , Replace its current content , And modify it accordingly size	//n individual val	first.assign(7, 100);	// Iterator interval 	std::vector<int>::iterator it;	it = first.begin() + 1;	second.assign(it, first.end() - 1);		// Pointer interval , here myints Point to 1,myints+3 Point to 4, Why only output 1 2 3	// Two parameters here myints,myints+3 Pass to the iterator interval respectively first,last. The iterator must be a left closed and right open interval [first, last), Because the loop condition of the iterator is first!=last	int myints[] = { 1, 2, 3, 4, 5 };	third.assign(myints, myints + 3);	for(auto e : third)	{		std::cout << e << " ";		}	std::cout << "Size of first:" << int(first.size()) << '\n';	std::cout << "Size of second:" << int(second.size()) << '\n';	std::cout << "Size of third:" << int (third.size()) << '\n';}void test_vector2(){	int a[] = { 1, 2, 3, 4, 5 };	vector<int> v(a, a + 5);		// Head insertion 	v.insert(v.begin(), 0);		// stay 2 Insert in front of , You can start with find 2, however vector Not provided find, But the algorithm provides the function template find	// The reason why the algorithm provides find The reason is that vector want find,list want find, So here find Providing a template solves the problem , You can be vector The iterator , It can also be list The iterator ,string The iterator for is not necessary , Of course string I have provided , Why? string You should provide it yourself 	// because string Not only to support find A character , It also supports finding a string , Use find Want a bag algorithm	vector<int>::iterator pos = find(v.begin(), v.end(), 2);	if(pos != v.end())// No return found last	{		v.insert(pos, 20);		}}void test_vector3(){	// We talked about the algorithm find after , By the way, let's talk about the commonly used sort	int a[] = { 1, 20, 2, 3, 4, 5 };	vector<int> v(a, a + 6);	// Ascending 	sort(v.begin(), v.end());	// Descending , Here you need to pass a comparator object , Here we will deal with the imitative function , The priority of the queue will be described in detail later , Using it requires a package functional	/*greater<int> gt; sort(v.begin(), v.end(), gt);*/	sort(v.begin(), v.end(), greater<int>());// ditto , Anonymous objects are more recommended 	//sort Not only can you sort containers , You can also sort arrays , Because pointers to array space are natural iterators 	// In other words, from now on C Linguistic qsort To give up  	int b[] = { 30, 4, 50, 6, 7 };	sort(b, b + 5);}void test_vector4(){	int a[] = { 1, 20, 2, 3, 4, 5 };	vector(int> v(a, a + 6);		// Head deletion 	v.erase(v.begin());		// Delete 2	vector<int>::iterator pos = find(v.begin, v.end(), 2);	if(pos != v.end))	{		v.erase(pos);	}	}int main(){	test_vector1();	test_vector2();	test_vector3();	test_vector4();	return 0;}

explain

1. List item
   

2. List item
   
   

3. List item

   operator[] and at The difference between

   Their functions are similar , The difference is ：operator[] It's rough to cross the boundary , If the subscript is greater than or equal to size, It directly asserts an error ; and at If an error is reported, an exception will be thrown , After the capture , It doesn't just abort the program .

5、vector The problem of iterator failure ( Recommendations and vector The simulation implementation of )

The main function of iterators is to make the algorithm don't care about the underlying data structure , The bottom layer is actually a pointer , Or encapsulate the pointer , such as ：vector The iterator of 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 ( The iterator failure problem is similar to the wild pointer problem ), And use a space that has been released , The result is a program crash ( That is, if you continue to use an iterator that has expired , The program could crash )

#include<iostream>#include<vector>#include<algorithm>using namespace std;void test_vector1(){	vector<int> v;	v.push_back(1);	v.push_back(2);	v.push_back(3);	v.push_back(4):		vector<int>::iterator pos = find(v.begin(), v.end(), 2);	if(pos != v.end())	{		v.insert(pos, 20);		}	// stay insert in the future ,pos It may fail , If it fails, the program may crash , The iterator failure problem is similar to the wild pointer problem 	// Access and modify as follows: , Note that different compilers may have different results , stay VS I can't even pass the interview (insert It is caused by capacity increase )	cout << *pos << endl;	*pos = 100;}void test_vector2(){	vector<int> v;	// If the capacity is increased in advance, there will be no capacity increase below , So it won't fail ?	v.reserve(6);		v.push_back(1);	v.push_back(2);	v.push_back(3);	v.push_back(4):		vector<int>::iterator pos = find(v.begin(), v.end(), 2);	if(pos != v.end))	{		v.insert(pos, 20);	}	// stay VS No error is reported after running the program , Here we can conclude that as long as there is capacity increase , Then it must fail 	// Although there is no capacity increase here , But strictly speaking, it still fails , Failure here refers to pos The meaning of has changed , It no longer points to the original value 2, It's pointing to 20, So iterator failure is not necessarily a wild pointer , And the meaning has changed 	cout << *pos << endl;	*pos = 100;}void test_vector3(){	vector<int> v;	v.push_back(1);	v.push_back(2);	v.push_back(3);	v.push_back(4);	vector<int>::iterator pos = find(v.begin(), v.end(), 2);	if(pos != v.end()）	{		v.erase(pos);		}	// here erase after , Lead to pos It doesn't work , The reason for the failure is pos The meaning of is changed , And though pos No wild pointer , But the meaning has changed ,vs(p.j) Mandatory check under version , So here *pos You're going to report a mistake 	cout << *pos << endl;	*pos = 100; }int main(){	//insert	test_vector1();	test_vector2();	//erase	test_vector3();	return 0;}

explain

1. List item

   VS Next insert There are two situations when ( Commissioning certificate )
   

2. List item

   Verified , stay Linux g++ Next ,test_vector1() and test_vector2() No crash , This may be due to different environments , Its compatibilization mechanism is different ( There may be enough space at the beginning ), But it should be noted that although in g++ There was no crash , however pos It still fails , as a result of pos The meaning of is changed .
   Then we went directly to push_back before reserve 4 Space , Let it achieve the effect of capacity expansion , Then access and modify , It still does not report an error , This overturns the different capacity increasing mechanism mentioned above .
   We guess g++ Next vector Will the capacity increase of be in place , There is no need to open up another space , But then it proved that the conjecture was wrong , Because if the capacity is increased in situ ,*pos The value of would not be 0 了 .
   So nine times out of ten g++ The access and modification operation of the wild pointer is not checked out ( We have explained this a long time ago , The out of bounds of memory is in the form of random inspection ), Verified ： Before and after capacity increase v.begin() Print out your address ( Note that it is not printing pos, Before printing pos The address of is the same twice , Let the pea mistake g++ The following is the in place capacity expansion mechanism , Also with the above *pos yes 0 For a long time )

   

3. List item

   about test_vector3() stay g++ No error is reported , And the printed value is 3. This shows that the inspection mechanisms of the two environments are different . But whether the compiler here reports an error or not , stay erase(pos) after , We all think pos It doesn't work , It should be noted that after failure , Don't visit , Here's why ：

   Because if I erase Is the last data , Visit again , Then the program itself has problems .

 There are also some cases of passing the ball , As shown in the following code . This code anyway , stay  vs  I will definitely report an error ( It said that ), But in  Linux  I'm in a different situation .

1、 A segment error occurred

2、 Again push_back 5, No error will be reported during operation

Why? push_back 5 Then you won't report an error

So the last one here is an even number, and there will be a segment error , The last one is odd, which allows you to avoid this mistake .

Therefore, the correct and standardized writing of this code should be as follows

 Summary ： The best way to disable iterators is not to make any access .

1. We are insert There are two cases ： One is that the original space is not enough , Need to expand ( In situ expansion 、 Remote expansion 【VS and g++ We are all expanding in different places 】), after pos Or a pointer to the original position in the original space , therefore pos Is failure , If you visit again after failure, you may crash (VS It's going to crash next week ,g++ It won't break down 【 Checking memory out of bounds is a form of random inspection , It can't be said that it hasn't been checked out , We can drink and drive 】); Second, the original space is enough , There's no need to expand , after pos Or point to the original space and location , however *pos The value of has been changed , So we also think it is invalid , Because its meaning has changed . So insert(pos, x) in the future , Both believe that pos It doesn't work , Do not use at this time pos 了 , Don't say the program didn't crash , Just use it , Otherwise, there may be various unpredictable results ,STL It's just a theory , It just tells us insert after ,pos It will fail , But it does not specify when it will expire , Which scenario fails .

2. about erase, We are erase It may also fail after , There are two reasons for failure ： firstly , Have you ever thought about such a problem ,insert It will expand , that erase It also shrinks ( Such as the 100 Space of capacity 、100 A valid number , Now after deleting , only 30 A valid number , Then I want to reduce the capacity to half 【 open 50 Space of capacity , Copy and release the contents of the old space ,pos It's the wild pointer 】); second , Never move this space , Directly overwrite the following data . These two ways are possible ,STL They are not regulated , But whether the volume is reduced or not , They are considered invalid , Because the meaning has changed . And in VS I made a very strict inspection (pos Only the meaning has changed , No wild pointer , Are not accessible ), and g++ No problem .
For failure , We also have a corresponding mechanism to deal with ： such as insert There is a return value , It returns an iterator pointing to the newly inserted element , That is, if you want to access the newly inserted element pointed to pos receive insert The return value of . Empathy erase It's the same , It returns the location of the next data of the deleted data .