1. The basic components of STL
The Standard Template Library (STL for short) is simply a collection of templates for some commonly used data structures and algorithms.
Broadly speaking, STL is divided into three categories: Algorithm (algorithm), Container (container) and Iterator (iterator). Containers and algorithms can be seamlessly connected through iterators.
In detail, STL consists of 6 parts: Container, Algorithm, Iterator, Function object, Adapter, and Allocator.
2. Common containers in STL
Containers can be used to store data structures of various types of data (variables of basic types, objects, etc.). They are all template classes and are divided into three types: sequential containers, associative containers, and container adapters. The characteristics of the three types of containers are as follows :
2.1 Sequential Containers
The container is not sorted, and the insertion position of the element has nothing to do with the value of the element. Including vector, deque, list, the specific implementation principle is as follows:
(1) vector header file <vector>
dynamic array. Elements are stored contiguously in memory. Random access to any element can be done in constant time. Adding and deleting elements at the end has better performance.
(2) deque header file <deque>
two-way queue. Elements are stored contiguously in memory. Random access to any element can be done in constant time (second only to vector). Adding and deleting elements at both ends has better performance (constant time in most cases).
(3) list header file <list>
Doubly linked list. Elements are not stored contiguously in memory. Adding and deleting elements at any position can be done in constant time. Random access is not supported.
2.2 Associative Containers
The elements are sorted; any element is inserted, its position is determined according to the corresponding sorting rules; it has very good performance when searching; it is usually implemented in a balanced binary tree. Including set, multiset, map, and multimap, the specific implementation principles are as follows:
(1) set/multiset header file <set>
set means collection. The same elements are not allowed in a set, and the same elements are allowed in a multiset.
(2) map/multimap header file <map>
The difference between map and set is that the elements stored in the map have only two member variables, one named first and the other named second. The map sorts the elements from small to large according to the first value, and can be quickly retrieved according to first element.
Note: The difference between map and multimap is whether elements with the same first value are allowed.
2.3 Container Adapter
Some basic containers are encapsulated, so that they have new functions, such as encapsulating deque into a data structure with stack function. This newly obtained data structure is called an adapter. Including stack,queue,priority_queue, the specific implementation principle is as follows:
(1) stack header file <stack>
A stack is a finite sequence of items, and the items that are deleted, retrieved, and modified in the sequence can only be the items of the most advanced insertion sequence (the item at the top of the stack). last in first out.
(2) queue header file <queue>
queue. Insertion is only possible at the tail, and deletion, retrieval, and modification are only allowed at the head. First in first out.
(3) priority_queue header file <queue>
priority queue. Maintain some kind of order internally, and then make sure the highest priority element is always at the head. The highest priority element is always dequeued first.
Three, map container
Maps are associative containers, and their underlying containers are red-black trees. All elements of map are pair s, which have both real value and key value. The first element of a pair is considered a key value, and the second element is considered a real value. All elements will be automatically sorted according to the key value of the element. Duplicate key values are not allowed.
3.1 The characteristics of map are as follows
(1) map uses RBTree as the underlying container;
(2) All elements are key + value;
(3) Key duplication is not allowed;
(4) All elements are automatically sorted by key;
(5) The key of the map cannot be modified, but the value corresponding to the key can be modified.
3.2 Using map s
The map object is a template class that requires two template parameters, keyword and storage object:
std:map<int, string> personnel;
#include <iostream>
using namespace std;
#include <map> // automatically sort by key from small to large key is unique
// ID number Name
map<string, string> userMap;
//Added data:
pair<string, string> p1("142327199209091111","Zhang San");3.3 Insert elements
// Define a map object map<int, string> mapStudent; // The first one uses the insert function to insert a pair mapStudent.insert(pair<int, string>(000, "student_zero")); // The second is to use the insert function to insert value_type data mapStudent.insert(map<int, string>::value_type(001, "student_one")); // The third is to use the "array" method to insert mapStudent[123] = "student_first"; mapStudent[456] = "student_second";
3.4 Finding elements
//Access 3: find
cout << "look up" << endl;
it=userMap.find("142327200009091111");
// count counts the number of elements according to the key
//int res =userMap.count("142327200009091111");
if (it == userMap.end())
{
cout << "There is no such information" << endl;
}
else
{
cout << it->first << ":" << it->second << endl;
}3.5 Delete and clear elements
//iterator delete
iter = mapStudent.find("123");
mapStudent.erase(iter);
//delete with keyword
int n = mapStudent.erase("123"); //Returns 1 if deleted, otherwise returns 0
//Delete with iterator range: clear the entire map
mapStudent.erase(mapStudent.begin(), mapStudent.end());
//Equivalent to mapStudent.clear()3.6 Accessing elements
//Access 1: [key] gets the value
//Visit 2: Iterator
map<string, string>::iterator it = userMap.begin();
for (;it != userMap.end(); it++)
{
// it->first is the key it->second is the value
cout << it->first << ":" << it->second <<endl;
}Four, vector container
The underlying implementation principle of vector is a one-dimensional array (elements are stored continuously in space).
Vector stores elements in a continuous array. If the collection is full, when new data is added, a larger piece of memory is allocated, the original data is copied, the previous memory is released, and new elements are inserted.
dynamic array. Elements are stored contiguously in memory.
4.1 Inserting elements
#include <iostream>
using namespace std;
#include <vector>//vector --- "array
vector<int> v1;
v1.push_back(100);//tail plug
v1.push_back(200);4.2 Accessing elements
for loop through
for(int i=0;i<v1.size(); i++)
{
cout << v1[i] << endl;
}4.2 Iterator iteraotr
The iterator iterator is an important part of STL. Iterators can be used to store the elements in the collection very conveniently. STL writes an iterator for each collection. The iterator is actually a wrapper for a pointer to implement some common methods , such as ++, --, !=, ==, *, ->, etc.
//vector<int>::iterator it; is the iterator-pointer of vector<int>
vector<int>::iterator it;// vector<int>::iterator is equivalent to int* p; int*
for (it = v1.begin(); it!= v1.end(); it++)
{
cout << *it << endl;
}
5. List sequence container
Elements are stored in the heap, and each element is stored in a piece of memory. Its memory space can be discontinuous, and data is accessed through pointers.
#include <iostream>
using namespace std;
#include <list>
#if 0
#include <string>
int main()
{
list<string> strList;// new
//Added data: tail plug
strList.push_back("hello");
strList.push_back("world");
cout << strList.size() << endl;
//New data added: header inserted
strList.push_front("everyOne");
//New data: insert by position
list<string>::iterator it = strList.begin();
it++;
strList.insert(it, "teacher");
//access: iterator
for (it = strList.begin(); it!= strList.end(); it++)
{
cout << *it << endl;
}
//delete:
strList.pop_front();
it = strList.begin();
++it;
strList.erase(it);
// empty:
strList.clear();
return 0;
}
#endif