详解"/>
【C++知识树】STL详解
目录
STL六大组件
1.vector
vector容器基本概念
vector常用API 操作
array vs vector
capacity vs size
2.string容器
string容器基本概念
string容器常用操作
3.deque容器
deque容器基本概念
deque常用API
4.stack容器
stack容器基本概念
stack常用API
5.queue容器
queue容器基本概念
queue常用API
6.list容器
list容器基本概念
list容器的迭代器
list容器的数据结构
list常用API
7.set/multiset容器
set容器基本概念
multiset容器基本概念
set常用API
对组(pair)
8.map/multimap容器
map/multimap基本概念
map/multimap常用API
multimap案例
map实用案例
STL六大组件
STL提供了六大组件，彼此之间可以组合套用，这六大组件分别是:容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器。
1.vector
vector容器基本概念
vector的数据安排以及操作方式，与array非常相似，两者的唯一差别在于空间的运用的灵活性。
Array是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，可以，一切琐碎得由自己来，首先配置一块新的空间，然后将旧空间的数据搬往新空间，再释放原来的空间。
Vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就要求一个大块头的array了。
Vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦vector旧空间满了，如果客户每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓的扩充空间(不论多大)，一如刚所说，是”配置新空间-数据移动-释放旧空间”的大工程,时间成本很高，应该加入某种未雨绸缪的考虑，稍后我们便可以看到vector的空间配置策略。
vector常用API 操作
vector构造函数
vector<T> v; //采用模板实现类实现，默认构造函数
vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身。
vector(n, elem);//构造函数将n个elem拷贝给本身。
vector(const vector &vec);//拷贝构造函数。
Vector< vector< int> >v;// 二维向量
//例子 使用第二个构造函数 我们可以...
int arr[] = {2,3,4,1,9};
vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));
vector常用赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
vector& operator=(const vector &vec);//重载等号操作符
swap(vec);// 将vec与本身的元素互换。
vector大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。
capacity();//容器的容量
reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。
vector数据存取操作
at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
operator[];//返回索引idx所指的数据，越界时，运行直接报错
front();//返回容器中第一个数据元素
back();//返回容器中最后一个数据元素
vector插入和删除操作
insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
push_back(ele); //尾部插入元素ele
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
erase(const_iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素
vector例子
#include <iostream>
#include <vector>
using namespace std;int main()
{// 创建一个向量存储 intvector<int> vec; int i;// 显示 vec 的原始大小cout << "vector size = " << vec.size() << endl;// 推入 5 个值到向量中for(i = 0; i < 5; i++){vec.push_back(i);}// 显示 vec 扩展后的大小cout << "extended vector size = " << vec.size() << endl;// 访问向量中的 5 个值for(i = 0; i < 5; i++){cout << "value of vec [" << i << "] = " << vec[i] << endl;}// 使用迭代器 iterator 访问值vector<int>::iterator v = vec.begin();while( v != vec.end()) {cout << "value of v = " << *v << endl;v++;}return 0;
}output:
vector size = 0
extended vector size = 5
value of vec [0] = 0
value of vec [1] = 1
value of vec [2] = 2
value of vec [3] = 3
value of vec [4] = 4
value of v = 0
value of v = 1
value of v = 2
value of v = 3
value of v = 4巧用swap，收缩内存空间
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;int main(){vector<int> v;for (int i = 0; i < 100000;i ++){v.push_back(i);}cout << "capacity:" << v.capacity() << endl;cout << "size:" << v.size() << endl;//此时 通过resize改变容器大小v.resize(10);cout << "capacity:" << v.capacity() << endl;cout << "size:" << v.size() << endl;//容量没有改变vector<int>(v).swap(v);cout << "capacity:" << v.capacity() << endl;cout << "size:" << v.size() << endl;system("pause");return EXIT_SUCCESS;
}
reserve预留空间
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;int main(){vector<int> v;//预先开辟空间v.reserve(100000);int* pStart = NULL;int count = 0;for (int i = 0; i < 100000;i ++){v.push_back(i);if (pStart != &v[0]){pStart = &v[0];count++;}}cout << "count:" << count << endl;system("pause");return EXIT_SUCCESS;
}
array vs vector
Array是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，可以，一切琐碎得由自己来，首先配置一块新的空间，然后将旧空间的数据搬往新空间，再释放原来的空间。
Vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就要求一个大块头的array了。
capacity vs size
size 是当前 vector 容器真实占用的大小，也就是容器当前拥有多少个容器。
capacity 是指在发生 realloc 前能允许的最大元素数，即预分配的内存空间。
当然，这两个属性分别对应两个方法：resize() 和 reserve()
使用 resize() 容器内的对象内存空间是真正存在的
使用 reserve() 仅仅只是修改了 capacity 的值，容器内的对象并没有真实的内存空间(空间是"野"的)。
此时切记使用 [ ] 操作符访问容器内的对象，很可能出现数组越界的问题。
#include <iostream>
#include <vector>using std::vector;
int main(void)
{vector<int> v;std::cout<<"v.size() == " << v.size() << " v.capacity() = " << v.capacity() << std::endl;v.reserve(10);std::cout<<"v.size() == " << v.size() << " v.capacity() = " << v.capacity() << std::endl;v.resize(10);v.push_back(0);std::cout<<"v.size() == " << v.size() << " v.capacity() = " << v.capacity() << std::endl;return 0;
}output:
//初始化容器没有对象,也没有预留内存空间
v.size() == 0 v.capacity() = 0//reserve（10）预留10个对象的空间，但是容器内并没有对象，直接[]访问会报越界错误
v.size() == 0 v.capacity() = 10//size = capacity 后再push一个对象要重新分配一部分内存空间,
//至于重新分配多少，不同库有不同的实现
//（这里是增加原先大小的一半）
v.size() == 11 v.capacity() = 15 2.string容器
string容器基本概念
C风格字符串(以空字符结尾的字符数组)太过复杂难于掌握，不适合大程序的开发，所以C++标准库定义了一种string类，定义在头文件<string>。
string和c风格字符串对比：
char*是一个指针，string是一个类
string封装了char*，管理这个字符串，是一个char*型的容器。
string封装了很多实用的成员方法
查找find，拷贝copy，删除delete 替换replace，插入insert
不用考虑内存释放和越界
string管理char*所分配的内存。每一次string的复制，取值都由string类负责维护，不用担心复制越界和取值越界等。
string容器常用操作
string 构造函数
string();//创建一个空的字符串 例如: string str;
string(const string& str);//使用一个string对象初始化另一个string对象
string(const char* s);//使用字符串s初始化
string(int n, char c);//使用n个字符c初始化
string基本赋值操作
string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string& operator=(const string &s);//把字符串s赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
string& assign(const char *s);//把字符串s赋给当前的字符串
string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串
string& assign(const string &s);//把字符串s赋给当前字符串
string& assign(int n, char c);//用n个字符c赋给当前字符串
string& assign(const string &s, int start, int n);//将s从start开始n个字符赋值给字符串
string存取字符操作
char& operator[](int n);//通过[]方式取字符
char& at(int n);//通过at方法获取字符
string拼接操作
string& operator+=(const string& str);//重载+=操作符
string& operator+=(const char* str);//重载+=操作符
string& operator+=(const char c);//重载+=操作符
string& append(const char *s);//把字符串s连接到当前字符串结尾
string& append(const char *s, int n);//把字符串s的前n个字符连接到当前字符串结尾
string& append(const string &s);//同operator+=()
string& append(const string &s, int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾
string& append(int n, char c);//在当前字符串结尾添加n个字符c
string查找和替换
int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找
int find(const char* s, int pos = 0) const; //查找s第一次出现位置,从pos开始查找
int find(const char* s, int pos, int n) const; //从pos位置查找s的前n个字符第一次位置
int find(const char c, int pos = 0) const; //查找字符c第一次出现位置
int rfind(const string& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找
int rfind(const char* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找
int rfind(const char* s, int pos, int n) const;//从pos查找s的前n个字符最后一次位置
int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置
string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s
string比较操作
/*
compare函数在>时返回 1，<时返回 -1，==时返回 0。
比较区分大小写，比较时参考字典顺序，排越前面的越小。
大写的A比小写的a小。
*/
int compare(const string &s) const;//与字符串s比较
int compare(const char *s) const;//与字符串s比较
string子串
string substr(int pos = 0, int n = npos) const;//返回由pos开始的n个字符组成的字符串
string插入和删除操作
string& insert(int pos, const char* s); //插入字符串
string& insert(int pos, const string& str); //插入字符串
string& insert(int pos, int n, char c);//在指定位置插入n个字符c
string& erase(int pos, int n = npos);//删除从Pos开始的n个字符
string和c-style字符串转换
//string 转 char*
string str = "it";
const char* cstr = str.c_str();
//char* 转 string
char* s = "it";
string str(s);
在c++中存在一个从const char*到string的隐式类型转换，却不存在从一个string对象到C_string的自动类型转换。对于string类型的字符串，可以通过c_str()函数返回string对象对应的C_string.
通常，程序员在整个程序中应坚持使用string类对象，直到必须将内容转化为char*时才将其转换为C_string.
3.deque容器
deque容器基本概念
vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。
所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。
Deque容器和vector容器最大的差异，一在于deque允许使用常数项时间对头端进行元素的插入和删除操作。二在于deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像vector那样，”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque身上是不会发生的。也因此，deque没有必须要提供所谓的空间保留(reserve)功能.
虽然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针，其复杂度和vector不是一个量级，这当然影响各个运算的层面。因此，除非有必要，我们应该尽可能的使用vector，而不是deque。对deque进行的排序操作，为了最高效率，可将deque先完整的复制到一个vector中，对vector容器进行排序，再复制回deque.
deque常用API
deque构造函数
deque<T> deqT;//默认构造形式
deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n, elem);//构造函数将n个elem拷贝给本身。
deque(const deque &deq);//拷贝构造函数。deque赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符
swap(deq);// 将deq与本身的元素互换deque大小操作
deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，
//则以elem值填充新位置,如果容器变短，则末尾超出容器长度的元素被删除。deque双端插入和删除操作
push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据deque数据存取
at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
front();//返回第一个数据。
back();//返回最后一个数据deque插入操作
insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。deque删除操作
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。4.stack容器
stack容器基本概念
stack是一种先进后出(First In Last Out,FILO)的数据结构，它只有一个出口，形式如图所示。stack容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。
有元素推入栈的操作称为:push,将元素推出stack的操作称为pop.
stack没有迭代器
stack所有元素的进出都必须符合”先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。stack不提供遍历功能，也不提供迭代器。
stack常用API
stack构造函数
stack<T> stkT;//stack采用模板类实现， stack对象的默认构造形式：
stack(const stack &stk);//拷贝构造函数stack赋值操作
stack& operator=(const stack &stk);//重载等号操作符stack数据存取操作
push(elem);//向栈顶添加元素
pop();//从栈顶移除第一个元素
top();//返回栈顶元素stack大小操作
empty();//判断堆栈是否为空
size();//返回堆栈的大小5.queue容器
queue容器基本概念
queue是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口，queue容器允许从一端新增元素，从另一端移除元素。
queue没有迭代器
queue所有元素的进出都必须符合”先进先出”的条件，只有queue的顶端元素，才有机会被外界取用。queue不提供遍历功能，也不提供迭代器。
queue常用API
queue构造函数
queue<T> queT;//queue采用模板类实现，queue对象的默认构造形式：
queue(const queue &que);//拷贝构造函数queue存取、插入和删除操作
push(elem);//往队尾添加元素
pop();//从队头移除第一个元素
back();//返回最后一个元素
front();//返回第一个元素queue赋值操作
queue& operator=(const queue &que);//重载等号操作符queue大小操作
empty();//判断队列是否为空
size();//返回队列的大小6.list容器
list容器基本概念
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。
list和vector是两个最常被使用的容器。
list容器是一个双向链表。
- 采用动态存储分配，不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
- 链表灵活，但是空间和时间额外耗费较大
list容器的迭代器
list容器不能像vector一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。
list迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增，递减、取值、成员取用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。
由于list是一个双向链表，迭代器必须能够具备前移、后移的能力，所以list容器提供的是Bidirectional Iterators.
list有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效，甚至List元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。
list容器的数据结构
list容器不仅是一个双向链表，而且还是一个循环的双向链表。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
using namespace std;int main(){list<int> myList;for (int i = 0; i < 10; i ++){myList.push_back(i);}list<int>::_Nodeptr node = myList._Myhead->_Next;for (int i = 0; i < myList._Mysize * 2;i++){cout << "Node:" << node->_Myval << endl;node = node->_Next;if (node == myList._Myhead){node = node->_Next;}}system("pause");return EXIT_SUCCESS;
}list常用API
list构造函数
list<T> lstT;//list采用采用模板类实现,对象的默认构造形式：
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);//构造函数将n个elem拷贝给本身。
list(const list &lst);//拷贝构造函数。list数据元素插入和删除操作
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。list大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num，
若容器变长，则以默认值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num，
若容器变长，则以elem值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。list赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
list& operator=(const list &lst);//重载等号操作符
swap(lst);//将lst与本身的元素互换。list数据的存取
front();//返回第一个元素。
back();//返回最后一个元素。list反转排序
reverse();//反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。
sort(); //list排序7.set/multiset容器
set容器基本概念
set的特性是。所有元素都会根据元素的键值自动被排序。set的元素不像map那样可以同时拥有实值和键值，set的元素即是键值又是实值。set不允许两个元素有相同的键值。
我们不可以通过set的迭代器改变set元素的值，因为set元素值就是其键值，关系到set元素的排序规则。如果任意改变set元素值，会严重破坏set组织。换句话说，set的iterator是一种const_iterator.
set拥有和list某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。
multiset容器基本概念
multiset特性及用法和set完全相同，唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树
set常用API
set构造函数
set<T> st;//set默认构造函数：
mulitset<T> mst; //multiset默认构造函数:
set(const set &st);//拷贝构造函数set赋值操作
set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器set大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空set插入和删除操作
insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。set查找操作
find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count(key);//查找键key的元素个数
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。set的返回值 指定set排序规则举例
//插入操作返回值
void test01(){set<int> s;pair<set<int>::iterator,bool> ret = s.insert(10);if (ret.second){cout << "插入成功:" << *ret.first << endl;}else{cout << "插入失败:" << *ret.first << endl;}ret = s.insert(10);if(ret.second){cout << "插入成功:" << *ret.first << endl;}else{cout << "插入失败:" << *ret.first << endl;}}struct MyCompare02{bool operator()(int v1,int v2){return v1 > v2;}
};//set从大到小
void test02(){srand((unsigned int)time(NULL));//我们发现set容器的第二个模板参数可以设置排序规则，默认规则是less<_Kty>set<int, MyCompare02> s;for (int i = 0; i < 10;i++){s.insert(rand() % 100);}for (set<int, MyCompare02>::iterator it = s.begin(); it != s.end(); it ++){cout << *it << " ";}cout << endl;
}//set容器中存放对象
class Person{
public:Person(string name,int age){this->mName = name;this->mAge = age;}
public:string mName;int mAge;
};struct MyCompare03{bool operator()(const Person& p1,const Person& p2){return p1.mAge > p2.mAge;}
};void test03(){set<Person, MyCompare03> s;Person p1("aaa", 20);Person p2("bbb", 30);Person p3("ccc", 40);Person p4("ddd", 50);s.insert(p1);s.insert(p2);s.insert(p3);s.insert(p4);for (set<Person, MyCompare03>::iterator it = s.begin(); it != s.end(); it++){cout << "Name:" << it->mName << " Age:" << it->mAge << endl;}}对组(pair)
对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有属性first和second访问。
类模板：template <class T1, class T2> struct pair.
创建对组:
//第一种方法创建一个对组
pair<string, int> pair1(string("name"), 20);
cout << pair1.first << endl; //访问pair第一个值
cout << pair1.second << endl;//访问pair第二个值
//第二种
pair<string, int> pair2 = make_pair("name", 30);
cout << pair2.first << endl;
cout << pair2.second << endl;
//pair=赋值
pair<string, int> pair3 = pair2;
cout << pair3.first << endl;
cout << pair3.second << endl;8.map/multimap容器
map/multimap基本概念
map的特性是，所有元素都会根据元素的键值自动排序。
map所有的元素都是pair,同时拥有实值和键值，pair的第一元素被视为键值，第二元素被视为实值，map不允许两个元素有相同的键值。
我们不可以通过map的迭代器改变map的键值, 因为map的键值关系到map元素的排列规则，任意改变map键值将会严重破坏map组织。如果想要修改元素的实值，那么是可以的。
map和list拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。
multimap和map的操作类似，唯一区别multimap键值可重复。
map和multimap都是以红黑树为底层实现机制。
map/multimap常用API
map构造函数
map<T1, T2> mapTT;//map默认构造函数:
map(const map &mp);//拷贝构造函数map赋值操作
map& operator=(const map &mp);//重载等号操作符
swap(mp);//交换两个集合容器map大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空map插入数据元素操作
map.insert(...); //往容器插入元素，返回pair<iterator,bool>
map<int, string> mapStu;
// 第一种 通过pair的方式插入对象
mapStu.insert(pair<int, string>(3, "小张"));
// 第二种 通过pair的方式插入对象
mapStu.insert(make_pair(-1, "校长"));
// 第三种 通过value_type的方式插入对象
mapStu.insert(map<int, string>::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";map删除操作
clear();//删除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(keyElem);//删除容器中key为keyElem的对组。map查找操作
find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；/若不存在，返回map.end();
count(keyElem);//返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。multimap案例
//公司今天招聘了5个员工，5名员工进入公司之后，需要指派员工在那个部门工作
//人员信息有: 姓名 年龄 电话 工资等组成
//通过Multimap进行信息的插入 保存 显示
//分部门显示员工信息 显示全部员工信息#define _CRT_SECURE_NO_WARNINGS#include<iostream>
#include<map>
#include<string>
#include<vector>
using namespace std;//multimap 案例
//公司今天招聘了 5 个员工，5 名员工进入公司之后，需要指派员工在那个部门工作
//人员信息有: 姓名 年龄 电话 工资等组成
//通过 Multimap 进行信息的插入 保存 显示
//分部门显示员工信息 显示全部员工信息#define SALE_DEPATMENT 1 //销售部门
#define DEVELOP_DEPATMENT 2 //研发部门
#define FINACIAL_DEPATMENT 3 //财务部门
#define ALL_DEPATMENT 4 //所有部门//员工类
class person{
public:string name; //员工姓名int age; //员工年龄double salary; //员工工资string tele; //员工电话
};//创建5个员工
void CreatePerson(vector<person>& vlist){string seed = "ABCDE";for (int i = 0; i < 5; i++){person p;p.name = "员工";p.name += seed[i];p.age = rand() % 30 + 20;p.salary = rand() % 20000 + 10000;p.tele = "010-8888888";vlist.push_back(p);}}//5名员工分配到不同的部门
void PersonByGroup(vector<person>& vlist, multimap<int, person>& plist){int operate = -1; //用户的操作for (vector<person>::iterator it = vlist.begin(); it != vlist.end(); it++){cout << "当前员工信息:" << endl;cout << "姓名：" << it->name << " 年龄:" << it->age << " 工资:" << it->salary << " 电话：" << it->tele << endl;cout << "请对该员工进行部门分配(1 销售部门, 2 研发部门, 3 财务部门):" << endl;scanf("%d", &operate);while (true){if (operate == SALE_DEPATMENT){ //将该员工加入到销售部门plist.insert(make_pair(SALE_DEPATMENT, *it));break;}else if (operate == DEVELOP_DEPATMENT){plist.insert(make_pair(DEVELOP_DEPATMENT, *it));break;}else if (operate == FINACIAL_DEPATMENT){plist.insert(make_pair(FINACIAL_DEPATMENT, *it));break;}else{cout << "您的输入有误，请重新输入(1 销售部门, 2 研发部门, 3 财务部门):" << endl;scanf("%d", &operate);}}}cout << "员工部门分配完毕!" << endl;cout << "***********************************************************" << endl;}//打印员工信息
void printList(multimap<int, person>& plist, int myoperate){if (myoperate == ALL_DEPATMENT){for (multimap<int, person>::iterator it = plist.begin(); it != plist.end(); it++){cout << "姓名：" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话：" << it->second.tele << endl;}return;}multimap<int, person>::iterator it = plist.find(myoperate);int depatCount = plist.count(myoperate);int num = 0;if (it != plist.end()){while (it != plist.end() && num < depatCount){cout << "姓名：" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话：" << it->second.tele << endl;it++;num++;}}
}//根据用户操作显示不同部门的人员列表
void ShowPersonList(multimap<int, person>& plist, int myoperate){switch (myoperate){case SALE_DEPATMENT:printList(plist, SALE_DEPATMENT);break;case DEVELOP_DEPATMENT:printList(plist, DEVELOP_DEPATMENT);break;case FINACIAL_DEPATMENT:printList(plist, FINACIAL_DEPATMENT);break;case ALL_DEPATMENT:printList(plist, ALL_DEPATMENT);break;}
}//用户操作菜单
void PersonMenue(multimap<int, person>& plist){int flag = -1;int isexit = 0;while (true){cout << "请输入您的操作((1 销售部门, 2 研发部门, 3 财务部门, 4 所有部门, 0退出)：" << endl;scanf("%d", &flag);switch (flag){case SALE_DEPATMENT:ShowPersonList(plist, SALE_DEPATMENT);break;case DEVELOP_DEPATMENT:ShowPersonList(plist, DEVELOP_DEPATMENT);break;case FINACIAL_DEPATMENT:ShowPersonList(plist, FINACIAL_DEPATMENT);break;case ALL_DEPATMENT:ShowPersonList(plist, ALL_DEPATMENT);break;case 0:isexit = 1;break;default:cout << "您的输入有误，请重新输入!" << endl;break;}if (isexit == 1){break;}}}int main(){vector<person> vlist; //创建的5个员工 未分组multimap<int, person> plist; //保存分组后员工信息//创建5个员工CreatePerson(vlist);//5名员工分配到不同的部门PersonByGroup(vlist, plist);//根据用户输入显示不同部门员工信息列表 或者 显示全部员工的信息列表PersonMenue(plist);system("pause");return EXIT_SUCCESS;
}map实用案例
#include <iostream>
#include <map>
#include <string>using namespace std;struct myCompare
{bool operator()(const uint16_t a, const uint16_t b) const{return (a > b);}myCompare() {}
};template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
void print_Map(const string &name, const map<_Key, _Tp, _Compare, _Alloc> &tmap)
{cout << name << ": \n";for (const std::pair<const _Key, _Tp> it : tmap){cout << "key: " << it.first << ", value: " << it.second << endl;}
}void constructorTest()
{cout << "constructorTest() begin" << endl;// 构造空容器map<uint16_t, string> map1;cout << "map1.size() : " << map1.size() << endl;// 列表初始化，构造, 排序递增map<uint16_t, string, std::less<uint16_t>> map2{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};print_Map("initializer_list, ASC", map2);// 列表初始化，构造, 排序递减map<uint16_t, string, std::greater<uint16_t>> map6{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};print_Map("initializer_list, DESC", map6);// 列表初始化，构造, 排序自定义map<uint16_t, string, myCompare> map7{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};print_Map("initializer_list, DESC", map7);// 范围构造,排序递增map<uint16_t, string, std::less<uint16_t>> map3(map2.begin(), map2.end());print_Map("range, ASC", map3);// 范围构造,排序递减map<uint16_t, string, std::greater<uint16_t>> map8(map2.begin(), map2.end());print_Map("range, DESC", map8);// 拷贝构造，类型必须一致，包括排序，排序递增map<uint16_t, string, std::less<uint16_t>> map4(map3);print_Map("copy, ASC", map4);// 拷贝构造,排序递增map<uint16_t, string, std::greater<uint16_t>> map9(map8);print_Map("copy, DESC", map9);// 赋值构造,类型必须一致，包括排序，排序递增map<uint16_t, string, std::less<uint16_t>> map10 = map4;print_Map("assignment , ASC", map10);// 赋值构造,类型必须一致，包括排序，排序递减map<uint16_t, string, std::greater<uint16_t>> map11 = map9;print_Map("assignment , DESC", map11);cout << "constructorTest() end" << endl;
}void elementAccessTest()
{cout << "elementAccessTest() begin" << endl;map<uint16_t, string, std::less<uint16_t>> map1{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};cout << "at(key) : " << map1.at(1) << endl;cout << "[key] : " << map1[2] << endl;// map容器产生<6,"">节点cout << "[key] : " << map1[6] << endl;print_Map("[key] , ASC", map1);// map容器产生<7,"H">节点map1[7] = "H";print_Map("[key] , ASC", map1);// map容器key为1的节点value被替换为"K"map1[1] = "K";print_Map("[key] , ASC", map1);cout << "elementAccessTest() end" << endl;
}void capacityTest()
{cout << "capacityTest begin" << endl;map<uint16_t, string> map1;cout << "map1: " << (map1.empty() ? "empty" : "not empty");cout << "map1 size() " << map1.size() << endl;;map1[1] = "A";map1[2] = "B";cout << "map1: " << (map1.empty() ? "empty" : "not empty");cout << "map1 size() " << map1.size() << endl;;cout << "map<uint16_t, string> max_size: " << map1.max_size() << std::endl;map<uint16_t, uint16_t> map2;cout << "map<uint16_t, uint16_t> max_size: " << map2.max_size() << std::endl;map<string, uint16_t> map3;cout << "map<string, uint16_t> max_size: " << map3.max_size() << std::endl;map<string, string> map4;cout << "map<string, string> max_size: " << map4.max_size() << std::endl;cout << "capacityTest end" << endl;
}void iteratorTest()
{cout << "iteratorTest begin" << endl;map<uint16_t, string> map1{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};// 遍历容器， const_iteratorstd::cout << "const_iterator:\n";for (map<uint16_t, string>::const_iterator it = map1.cbegin(); it != map1.cend(); it++){cout << "key: " << it->first << ", value: " << it->second << endl;}std::cout << "const_iterator:\n";for (map<uint16_t, string>::const_reverse_iterator it = map1.crbegin(); it != map1.crend(); it++){cout << "key: " << it->first << ", value: " << it->second << endl;}std::cout << "begin(): " << std::hex << (int)&*map1.begin() << std::endl;std::cout << "cbegin(): " << std::hex << (int)&*map1.cbegin() << std::endl;std::cout << "end(): " << std::hex << (int)&*map1.end() << std::endl;std::cout << "cend(): " << std::hex << (int)&*map1.cend() << std::endl;std::cout << "rbegin(): " << std::hex << (int)&*map1.rbegin() << std::endl;std::cout << "crbegin(): " << std::hex << (int)&*map1.crbegin() << std::endl;std::cout << "rend(): " << std::hex << (int)&*map1.rend() << std::endl;std::cout << "crend(): " << std::hex << (int)&*map1.crend() << std::endl;cout << "iteratorTest end" << endl;
}void clearTest()
{cout << "clearTest() begin" << endl;map<uint16_t, string> map1{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};print_Map("clear before", map1);map1.clear();cout << "map1: " << (map1.empty() ? "empty" : "not empty");cout << "clearTest() end" << endl;
}void insertTest()
{cout << "insertTest() begin" << endl;map<uint16_t, string> map1{{1, "A"}, {2, "B"}, {3, "C"}};print_Map("insert before", map1);std::pair<std::map<uint16_t, string>::iterator, bool> itI = map1.insert({4, "D"});cout << "insert " << (itI.second ? "success" : "fail") ;cout << " key: " << itI.first->first << " value: " << itI.first->second << endl;print_Map("insert after", map1);map<uint16_t, string>::const_iterator pIt = map1.find(2);cout << "find key: " << pIt->first << " value: " << pIt->second << endl;map<uint16_t, string>::const_iterator nIt = map1.insert(pIt, {5, "E"});cout << "insert key: " << nIt->first << " value: " << nIt->second << endl;print_Map("insert after", map1);map<uint16_t, string> map2{{6, "F"}, {7, "H"}};map2.insert(map1.begin(), map1.end());print_Map("map2 insert after", map2);cout << "insertTest() end" << endl;
}void emplaceTest()
{cout << "emplaceTest() begin" << endl;map<uint16_t, string> map1{{1, "A"}, {2, "B"}, {3, "C"}};print_Map("emplace before", map1);std::pair<std::map<uint16_t, string>::iterator, bool> itI = map1.emplace(make_pair(4, "D"));cout << "emplace " << (itI.second ? "success" : "fail") ;cout << " key: " << itI.first->first << " value: " << itI.first->second << endl;print_Map("emplace after", map1);map<uint16_t, string>::const_iterator pIt = map1.find(2);map<uint16_t, string>::const_iterator nIt = map1.emplace_hint(pIt, make_pair(5, "E"));cout << "emplace_hint key: " << nIt->first << " value: " << nIt->second << endl;print_Map("emplace_hint after", map1);cout << "emplaceTest() end" << endl;
}void eraseTest()
{cout << "eraseTest() begin" << endl;map<uint16_t, string> map1{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};print_Map("erase before", map1);size_t ct = map1.erase(3);cout << "erase size: " << ct << std::endl;ct = map1.erase(3);cout << "erase size: " << ct << std::endl;print_Map("map1 erase after", map1);map<uint16_t, string>::const_iterator pIt = map1.find(2);map<uint16_t, string>::const_iterator eIt = map1.erase(pIt);cout << "erase key: " << eIt->first << " value: " << eIt->second << endl;print_Map("map1 erase after", map1);map<uint16_t, string> map2{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};print_Map("map2 erase before", map2);map2.erase(map2.begin(), map2.end());print_Map("map2 erase after", map2);cout << "eraseTest() end" << endl;
}void swapTest()
{cout << "swapTest() begin" << endl;map<uint16_t, string> map1{{1, "A"}, {2, "B"}, {3, "C"}};map<uint16_t, string> map2{{4, "D"}, {5, "E"}};print_Map("map1 swap before", map1);print_Map("map2 swap before", map2);map1.swap(map2);print_Map("map1 swap after", map1);print_Map("map2 swap after", map2);cout << "swapTest() endl" << endl;}int main()
{
// constructorTest();
// elementAccessTest();
// capacityTest();
// iteratorTest();
// clearTest();
// insertTest();
// emplaceTest();
// eraseTest();swapTest();return 0;
}更多推荐
【C++知识树】STL详解
发布评论