C++ Of STL in , What kind of containers do you have ?
<> container
On data storage , There is one object type , It can hold other objects or pointers to other objects , This object type is called a container .
<> Sequence container (7 individual )
<>vector
vector Is a continuous memory address , Implementation based on array , It provides automatic memory management function （ Adopted STL Universal memory manager allocator）, The length of the object can be changed dynamically , Provide random access . The time to add and remove elements at the tail is constant , But in the head or in the middle is linear time .
stay vector There are several functions about size in the container ：
* size()： Returns the size of the container
* max_size()： Returns the maximum number of stored elements for the container extension limit
* empty()： Determine whether the container is empty
* capacity()： Returns the number of elements that the container can hold
vector Memory expansion mode ：
* Looking for more space ;
* Copy the original data ;
* Release the original space .
General attention vector The problem of memory allocation , as a result of ：
*
Once the size of the container exceeds capacity The size of ,vector The internal storage is reconfigured , Lead to and vector All related elements reference,pointers,iterator It's going to fail .
* Memory reconfiguration can be time consuming , Frequent realloc Operation will greatly reduce the efficiency of the program .
*
vector Of capacity Refers to the maximum capacity in the current state . If this value is not specified , At first 0, When the first value is added , because capacity Not enough , Applied to the operating system for a length of 1 Memory for . After that, every time capacity Insufficient time , Will re apply to the operating system for twice the length of the original memory .
Ways to avoid memory reconfiguration ：
* Reserve() Reserve appropriate capacity
After creating the container , Allocate enough space for the container at the first time , Avoid reallocation of memory . std :: vector<int> v; //create an empty
vector v.reverse(80); //reserve memory for 80 elements
* Use the constructor to create enough space
This method is used when creating a container , Use constructor initialization to get enough space , std::vector<int> v(80); //1. Define and initialize vector<int>
vec1; // Default initialization ,vec1 It is empty vector<int> vec2(vec1); // use vec1 initialization vec2 vector<int>
vec3(vec1.begin(),vec1.end()); // use vec1 initialization vec2 vector<int> vec4(10);
//10 The first value is 0 The elements of vector<int> vec5(10,4); //10 The first value is 4 The elements of //2. Common operation methods vec1.push_back(100);
// Add element to tail int size = vec1.size(); // Number of elements bool isEmpty = vec1.empty(); // Judge whether it is empty
cout<<vec1[0]<<endl; // Get the first element vec1.insert(vec1.end(), 5, 3);
// from vec1.back Position insertion 5 The first value is 3 The elements of vec1.pop_back(); // Delete end element vec1.erase(vec1.begin(),
vec1.begin() + 2); // delete vec1[0]-vec1[2] Elements between , barring vec1[2], Move other elements forward cout<<(vec1 ==
vec2) ? true : false; // Judge whether it is equal or not ==,!=,>=,<= vector<int> :: iterator iter =
vec1.begin(); // Get iterator first address vector<int> :: const_iterator c_iter = vec1.begin();
// obtain const type iterator vec1.clear(); // Empty element //3. ergodic // subscripts int length = vec1.size();
for(int i=0; i<length; i++) { cout<<vec1[i]; } cout<<endl<<endl; // Iterator method
vector<int> :: iterator iter = vec1.begin(); for( ; iter != vec1.end(); iter++)
{ cout<<*iter; }
<>list
list It's discontinuous memory , Realization based on linked list , It belongs to circular two-way linked list , The purpose is to achieve fast insertion and deletion , However, the visit is relatively slow .
//1. Define and initialize list<int> lst1; // Create empty list list<int> lst2(3); // Create a three element list
list<int> lst3(3,2); // Create a 2 Of list list<int> lst4(lst2); // use lst2 initialization lst4
list<int> lst5(lst2.begin(), lst2.end()); // with lst4 //2. Common operation methods
lst1.assign(lst2.begin(),lst2.end()); // distribution 3 The first value is 0 The elements of lst1.push_back(10); // Add value at the end
lst1.pop_back(); // Delete end value lst1.begin(); // Iterator that returns the initial value lst1.end(); // Iterator that returns the trailing value
lst1.clear(); // Clear value bool isEmpty1 = lst1.empty(); // The judgment is empty
lst1.erase(lst1.begin(),lst1.end()); // Delete element lst1.front(); // Returns the reference of the first element
lst1.back(); // Returns the reference of the last element lst1.insert(lst1.begin(), 3, 2); // Inserts from the specified location 3 The first value is 2 The elements of
lst1.rbegin(); // Returns the forward pointer to the first element lst1.remove(2); // Delete all the same elements lst1.reverse(); // reversal
lst1.size(); // Number of elements lst1.sort(); // sort lst1.unique(); // Remove adjacent duplicate elements //3. ergodic // Iterator method
for(list<int> :: const_iterator iter = lst1.begin(); iter != lst1.end();
iter++) { cout<<*iter; }
<>deque
Two terminal queue （double-ended
queue）, Support random access , And vector similar , The main difference is that , from deque At the beginning of the object, the time to insert and delete elements is also constant , So if most operations occur at the beginning and end of a sequence , It should be considered deque. To achieve in deque The time of inserting and deleting operations at both ends is constant ,deque Design ratio of object vector It's more complicated , therefore , Although both provide random access to elements and perform linear time insertion and deletion operations in the middle of the sequence , but vector Containers perform these operations faster .
#include <deque> #include <iostream> #include <algorithm> #include <stdexcept>
using namespace std; int main() { //1. initialization deque<int> v; deque<int> :: iterator
iv; deque<int> v1{ 1, 2, 3, 4, 5}; deque<int> v2(v1); deque<int> v3(v1.begin(),
v1.end()); //v.assign(10, 2); // take 10 The first value is 2 The elements of deque in v.assign(v1.begin(),
v1.end()); // Accept the scope of the sequence container cout << v.size() << endl; // return deque Number of elements actually contained //2. add to
v.push_front(666); for (int i = 0; i < 10; i++) v.push_back(i);
for_each(v.begin(), v.end(), print); // need #include <algorithm>, print For custom output functions
cout << v.size() << endl; //3. Insert and traverse , Inverse ergodicity v.insert(v.begin() + 3, 99);
v.insert(v.end() - 3, 99); for_each(v.begin(), v.end(), print);
for_each(v.rbegin(), v.rend(), print); // Do it on the reverse iterator ++ The operation points to the previous element in the container // General ergodic writing
for(iv = v.begin(); iv != v.end(); ++iv) cout << *iv << " "; //4. delete
v.erase(v.begin() + 3); for_each(v.begin(), v.end(), print); v.insert(v.begin()
+ 3, 99); // reduction v.erase(v.begin(), v.begin() + 3); // Note the deletion 3 It's an element instead of an element 4 individual
for_each(v.begin(), v.end(), print); v.pop_front(); v.pop_back();
for_each(v.begin(), v.end(), print); //5. query cout << v.front() << endl; cout <<
v.back() << endl; // Dangerous practices , But in general, we just operate as if we were accessing arrays for (int i = 15; i < 25; i++) cout
<< "Element " << i << " is " << v[i] << endl; // Safe practices try { for (int i = 15; i
< 25; i++) cout << "Element " << i << " is " << v.at(i) << endl; } catch
(out_of_range err) //#include <stdexcept> { cout << "out_of_range at " << i <<
endl; } //6. empty v.clear(); cout << v.size() << endl; //0 for_each(v.begin(),
v.end(), print); // already clear,v.begin()==v.end(), There will be no result . return 0; }
<>forward_list
The single linked list is realized , Irreversible . Compared to list,forward_list It's simpler , More compact , But it's also less functional .
<>queue
queue Is an adapter class .queue Templates let the underlying class （ The default is deque） Show a typical queue interface .queue Limit ratio of template deque more , Not only does it not allow random access to queue elements , Even traversing the queue is not allowed . Same as queue , Only elements can be added to the end of the team , Remove element from team leader , View the values at the head and tail of the team , Check the number of elements and whether the test queue is empty .
<>priority_queue
priority_queue Is another adapter class , Supported operations and queue identical . The main difference between the two is that , stay priority_queue in , The largest element is moved to the top of the team . The internal difference is that , The default underlying class is vector. You can modify the comparison method used to determine which element is placed at the top of the team , Method is to provide an optional constructor parameter ：
priority_queue<int> pq1; // default version priority_queue<int>
pg2(greater<int>); // use greater<int> to order, greater<> A function is a predefined function object .
<>stack
And queue be similar ,stack It is also an adapter class , It gives the underlying class （ By default, it is vector） A typical stack interface is provided .
<> Association container (4 individual )
The main types of containers are as follows map and set.map yes key-value Formal ,set It's single valued .map and set Can only store unique key value ,multimap and multiset Can store multiple identical key value . The bottom layer is based on tree structure .
<>map/multimap
map The container provides a key value pair (key-value) container ,map And multimap The only difference is that multimap One key is allowed to correspond to multiple values . For iterators , You can modify the real value , It cannot be modified key.map According to key Auto sort .
//map yes 6 Constructors , It's about memory allocation , ellipsis //1. Define and initialize map<int, string> map1; // empty map //2. Common operation methods
map1[3] = "Saniya"; // Add element map1.insert(pair<int, string>(1,"Siqinsini"));
//pair Insert element by map1.insert(map<int, string> :: value_type(2, "Diyabi"));
//value_type Method input element map1.insert(make_pair<int, string>(4, "V5") );
//make_pair Insert element string str = map1[3]; // Insert elements numerically , according to key obtain value,key It cannot be modified map<int,
string> :: iterator iter_map = map1.begin();// Gets the first address of the iterator int key =
iter_map->first; // obtain key string value = iter_map->second; // obtain value
map1.erase(iter_map); // Delete iterator data map1.erase(3); // according to key delete value map1.size();
// Number of elements map1.empty(); // Judgment null map1.clear(); // Empty all elements //3. ergodic // Normal traversal for(map<int,
string> :: iterator iter = map1.begin(); iter != map1.end(); iter++) { int k =
iter->first; string v = iter->second; cout<< k << " " << v <<endl; } // reverse traversal
for(map<int, string> :: iterator iter = mapStudent.rbegin(); iter !=
mapStudent.rend(); iter++) cout << iter->first << " "<< iter->second << endl;
// Array traversal , Note that this is not for(int nindex = 0; nindex < nSize; nindex++) for(int nindex =
1; nindex <= nSize; nindex++) cout<<mapStudent[nindex]<<endl;
<>set/multiset
set It means set , It's an orderly container , The elements inside are sorted and support insertion , delete , Search and other operations , It's like a collection , All operations are strictly in the logn Finish in less time , It's very efficient .set and multiset What's the difference ,set The inserted elements cannot be the same , however multiset It can be the same ,set The default is automatic sorting , The usage is similar list.
<> Comparison of several containers
1)vector
Internal data structure ： array .
The time required to add or remove elements at the end is independent of the number of elements , The time required to add or delete elements in the middle or at the beginning varies linearly with the number of elements .
2):deque
The internal data structure is ： array .
Random access to each element , The time required is constant . The time required to add elements at the beginning and end is independent of the number of elements , The time required to add or delete in the middle varies linearly with the number of elements .
3)list
Internal data structure ： Two way ring linked list .
You cannot access an element randomly , Bidirectional traversal , At the beginning , The time required to add or remove elements at the end and anywhere in the middle is constant .
4)set
Keys and values are equal and unique .
Elements are arranged in ascending order by default ,
5)map
Key uniqueness , Value corresponding key .
The ascending order of the element's default keys
<> Iterator failure
On the problem of iterator failure , Use with care STL In erase.
// This code will crash #include"stdafx.h" #include<iostream> #include<vector> using
namespace std; int main() { vector<int> vect; for(int i = 0; i < 10; i++ ) {
vect.push_back(i); } vector<int>::iterator iter = vect.begin(); for(; iter !=
vect.end(); iter++ ) { if( *iter % 2 == 0 ) { vect.erase(iter); } } return 0; }
The program is direct crash It's over .iter It's pointing vector An element in this container , If not in for,while In circulation ,erase There is no problem deleting elements , But if you are for,while Iteration of container in loop , Delete all elements that meet the criteria , There may be problems .vect.erase(iter) after ,iter And the iterators that follow have failed , These iterators should no longer be used , Reexecution iter++, Its behavior is undefined . Other containers also encounter iterator failures .
about vector The iterators of the deleted elements and those pointing to the following elements are all invalid . about deque Deleting an element at the head or tail only invalidates the iterator that points to the deleted element , Insert and delete operations at other locations will invalidate all iterators of the container .
about list Only iterators pointing to deleted elements fail . Why is the failure of iterators different for different containers ? This is mainly related to the data structure of each container . Here's an example ：
#include "stdafx.h" #include<iostream> #include<vector> #include<map>
#include<deque> #include<list> using namespace std; int main() { //vector
vector<int> vect; for(int i = 0; i < 10; i++ ) { vect.push_back(i); }
vector<int> :: iterator iter = vect.begin(); for(; iter != vect.end(); ) { if(
*iter % 2 == 0 ) { //vect.erase(iter++); // test , report errors iter = vect.erase(iter); }
else { iter++; } } //deque deque<int> myDeque; for( int i = 0; i < 10; i++ ) {
myDeque.push_back(i); } deque<int>::iterator deiter = myDeque.begin(); for(;
deiter != myDeque.end();) { if( *deiter % 2 == 0 ) { //myDeque.erase(deiter++);
// test , Same error deiter = myDeque.erase(deiter); } else { deiter++; } } //list
list<int> myList; for( int i = 0; i < 10; i++ ) { myList.push_back(i); }
list<int>::iterator listiter = myList.begin(); for(; listiter != myList.end();)
{ if( *listiter % 2 == 0 ) { //myList.erase(listiter++); listiter =
myList.erase(listiter);
// about list Either way is OK . Because for list For example, only iterators pointing to deleted elements fail , Does not cause all iterators to fail } else { listiter++;
} } //map map<int, int> myMap; myMap[0] = 1; myMap[1] = 2; myMap[2] = 3;
myMap[3] = 4; map<int,int> :: iterator it = myMap.begin(); for(; it !=
myMap.end(); ) { if( (it->second) % 2 == 0 ) { myMap.erase(it++); //it =
myMap.erase(it); // about map Either way is OK ,C++11 To support the return of the current iterator } else { it++; } }
//set With map equally system("pause"); return 0; }
Technology