【STL】vector

1. vector

vector It means vector in Chinese , It is a dynamic order table that can change size .

2. vector Common interfaces

2.1 Constructors

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

vector Is a class template , It can not only store int、double Other types , It can also store string, Strictly speaking vector Can store any type .

void test_vector1()
{
    
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);

	vector<double> v2;
	v2.push_back(1.1);
	v2.push_back(2.2);
	v2.push_back(3.3);

	vector<string> v3;
	// One parameter constructors support implicit conversions 
	//string(const char* str)
	//string s = "hello world";
	// A constant string constructs a temporary object 
	// Then copy the structure to s
	// Optimized into direct construction s
	v3.push_back(" Li Bai ");
	v3.push_back(" Du Fu ");
	v3.push_back(" Su shi ");
	v3.push_back(" Bai Juyi ");
	
	//10 individual 5 initialization 
	vector<int> v4(10, 5);
	
	// Iterator interval initialization 
	vector<string> v5(++v3.begin(), --v3.end());
	string s = "hello world";
	vector<char> v6(s.begin(), s.end());
}

test ：

2.2 Traverse

void test_vector2()
{
    
	//  Traverse 
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	// 1、 Subscript +[]
	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)
	{
    
		cout << e << " ";
	}
	cout << endl;
}

test ：

2.3 increase capacity

void test_vector3()
{
    
	size_t sz;
	vector<int> foo;

	// Current capacity 
	sz = foo.capacity();
	// increase capacity , If the capacity changes, print it 
	cout << "making foo grow:\n";
	for (int i = 0; i < 100; ++i) 
	{
    
		foo.push_back(i);
		if (sz != foo.capacity()) 
		{
    
			sz = foo.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

vs2019 Next test ：vs(PJ edition STL) It's probably 1.5 Double capacity increase .

Linux Next ：g++(SGI edition STL) Is in accordance with the 2 Multiplied by .

g++ Running results ：
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128

Analysis of how much words can be added :
The more capacity is increased in a single time , Insert N It's worth , The less capacity increase times , The more efficient .
The more capacity is increased in a single time , Maybe the more waste .
The single increase is less , It will lead to frequent capacity increase , inefficiency ,
therefore VS、Linux Choose... Separately 1.5 Times and 2 Double capacity , This is also the result of balancing .

If we already know how much space to use , You can use it reserve Open the space well in advance (resize Will change size, The insertion will still expand )：

2.4 shrink_to_fit

string、vector All have one characteristic ： Delete data , Generally, they will not actively shrink the volume .vector Provide shrink_to_fit To request the container to reduce its capacity to accommodate its size .
shrink_to_fit The shortcomings of :
(1) If you want to insert data later , It will be expanded again , Then why shrink the volume ！
(2) The operating system does not allow part of the memory , Therefore, the actual operation of volume reduction is to apply for a volume reduction size first ( Assuming that n Bytes ) Space , Then put the front of the original space n Copy bytes , Then release the original space .

shrink_to_fit At the cost of performance , I suggest you use it with caution .

void test_vector4()
{
    
	size_t sz;
	vector<int> foo;
	foo.reserve(100);
	foo.resize(10);

	cout << foo.size() << endl;
	cout << foo.capacity() << endl;

	//  Use with caution 、 To use less 
	foo.shrink_to_fit();
	cout << foo.size() << endl;
	cout << foo.capacity() << endl;
}

test ：

2.5 insert and erase

vector Of insert Subscripts are not supported , Only iterators are supported .

void test_vector5()
{
    
	//  Traverse 
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	v.insert(v.begin(), -1);
	v.insert(v.begin(), -2);
	v.insert(v.begin(), -3);

	for (auto e : v)
	{
    
		cout << e << " ";
	}
	cout << endl;

	v.insert(v.begin()+7, 300);
	//v.insert(v.begin()+8, 300); Transboundary , Illegal iterator location 

	for (auto e : v)
	{
    
		cout << e << " ";
	}
	cout << endl;
	v.erase(v.begin());
	v.erase(v.begin());

	for (auto e : v)
	{
    
		cout << e << " ";
	}
	cout << endl;
}

2.6 find

vector No lookup function , But it can be reused algorithm In the database find.

void test_vector6()
{
    
	//  Traverse 
	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(), 3);
	auto pos = find(v.begin(), v.end(), 3);
	if (pos != v.end())
	{
    
		cout << " eureka " << endl;
		v.erase(pos);
	}
	else
	{
    
		cout << " Can't find " << endl;
	}

	for (auto e : v)
	{
    
		cout << e << " ";
	}
	cout << endl;
}

2.7 sort

void test_vector7()
{
    
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(0);
	v.push_back(9);
	v.push_back(3);
	v.push_back(1);

	//  The default is ascending 
	sort(v.begin(), v.end());
	for (auto e : v)
	{
    
		cout << e << " ";
	}
	cout << endl;

	//  In descending order , functor 
	//  About affine functions , Remember this usage first , Let's talk about the queue later, and then talk about it in detail 
	sort(v.begin(), v.end(), greater<int>());  // >
	for (auto e : v)
	{
    
		cout << e << " ";
	}
	cout << endl;
}

3. Exercises

3.1 Yang hui triangle

Yang hui triangle

About the topic vector(vector<int>):

The core idea ： Find out the law of Yang Hui triangle , I found that the beginning and end of each line are 1, In the middle [j] The number is equal to the previous line [j-1]+
[j]

class Solution {
    
public:
    vector<vector<int>> generate(int numRows) {
    
    vector<vector<int>> vv;
    //  First open up the space of Yang Hui triangle 
    vv.resize(numRows);
    // Initialize each row 
    for(size_t i = 0; i < numRows; ++i)
    {
    
        // The number of each line increases in turn 
        vv[i].resize(i+1, 0);
        //  The first and last of each line are 1
        vv[i][0] = 1;
        vv[i][vv[i].size()-1] = 1;
    }
    for(size_t i = 0; i < vv.size(); ++i)
    {
    
        for(size_t j = 0; j < vv[i].size(); ++j)
        {
    
            if(vv[i][j] == 0)
            {
    
                // The position between is equal to the previous line j-1 and j Add up 
                vv[i][j] = vv[i-1][j-1] + vv[i-1][j];
            }
        }
    }
    return vv;
    }
};

C Language reference code ：