首页 / C++ / C++标准模板库里面的容器
C++标准模板库里面的容器
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++标准模板库里面的容器，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含12595字，纯文字阅读大概需要18分钟。
内容图文
1. 顺序容器 sequential container
单一类型元素组成的有序集合
优：顺序访问元素快
不足：添加、删除元素性能相对低
非顺序访问元素性能相对低
vector、string、array都是连续的内存空间
容器选择：取决于执行访问的操作多还是插入删除的操作多
①一般用vector
②空间开销很重要时，不适用链表如list、forward_list
③需要随机访问：vector、deque
④要在中间进行插入、删除：链表类型如list、forwad_list
⑤只要在头尾插入、删除：deque
⑥读取输入时要在中间插入，之后要随机访问：
输入时用vector追加数据，在调用sort()函数，以避免在中间添加元素
若必须要在中间插入元素，输入时用list，输入完成后将list的内容保存到vector中
1.1 vector
https://zh.cppreference.com/w/cpp/container/vector
（1）vector的增长
vector<int> ivec;
cout<<"size:"<<ivec.size()<<endl;
cout<<"capacity:"<<ivec.capacity()<<endl;
for(int i=0;i<20;i++) {
ivec.push_back(i);
cout<<"size:"<<ivec.size()<<endl;
cout<<"capacity:"<<ivec.capacity()<<endl;
}
从输出结果看，这个vector一开始capacity即容量一开始为0，在插入第一个元素后变为1，在打算插入第二个元素时，vector需要新的空间，capacity变为2......
在capacity变为4，且准备放第5个元素时，vector申请空间（实际分配的空间多余需要的），capacity变成了8
当vector满了之后需要新空间时，会申请2倍于当前容量的空间。
（2）初始化
vector<int> vec1; //空的vector
vector<int> vec2 = vec1; //用已有的vector初始化，调用拷贝构造函数
vector<int> vec3(vec1); //同上
vector<int> vec3(10); //vec3的size和capacity都是10，里面的值为相应类型的默认值 string不适用
vector<int> vec3(10,99); //同上，但将值全设置为99
vector<int> vec4{1,2,3}; //列表初始化
vector<int> vec4 = {1,2,3};//同上
vector<int> vec5(be,en); //初始化为迭代器[be,en)间元素的拷贝 array不适用
用一个容器初始化另一个容器时，容器类型和元素类型必须相同（const char*可认为与string相同）
（3）其他操作
①迭代器
vec.begin(); //首元素的迭代器 vec.end(); //尾元素的下一个位置的迭代器
②添加元素
vec.push_back(12); //在尾端添加元素12 vec.insert(vec.begin(),10); //在首元素前插入元素10,10成了首元素 vec.insert(vec.end(),20); //20成了尾端元素
③遍历访问
数组形式：
for(int i=0;i<vec.size();i++) {
cout<<vec[i];
}
迭代器方式：
vector<int>::iterator i;
for(i=vec.begin();i!=vec.end();i++) {
cout<<*i;
}
vec.front(); //返回首元素的引用，要求vec不为空 vec.back(); //返回尾端元素的引用，要求vec不为空
④反向遍历
reverse_iterator rbegin() rever_iterator rend()
reverse_iterator ri;
for(ri=vec.rbegin();ri!=vec.rend();ri++) {
cout<<*ri;
}
⑤删除元素
iterator erase(iterator pos) 删除pos所指元素 iterator erase(iterator first,iterator last) 删除[first,last)区间里的元素
void clear(); //调用了 erase(vec.begin(),vec.end()) 删除vec对象里的所有元素
vec.pop_back(); //删除尾端元素
⑥整个vec的交换
利用swap算法
vector<int> vec1 = {1,2,3};
vector<int> vec2 = {4,5,6};
swap(vec1,vec2);
⑦属性
bool empty() 是否为空 size_type size() 容器中实际元素个数 size_type max_size() 系统容许的vector容器最大元素个数 size_type capacity() 当前可容纳的元素个数
1.2 deque
在尾部或头部插入、删除元素（O(1)复杂度）
deque元素数据用分块的线性结构存储，每个deque块一般512字节，因此每个deque块能容纳的元素个数取决于每个元素的大小
所有的deque用一个Map块管理，每个Map数据项记录各deque块首地址M_first、尾地址M_last、当前访问地址M_cur,还有M_node记录当前deque块在Map中的地址
（1）创建、初始化
deque<int> d; //没有元素的deque对象，实际有了一个deque块只是首尾迭代器重合 deque<int> d(10);//有10个元素的对象，元素有默认值 deque<int> d(10,1); //创建有10个初始值为1的deque对象 deque<int> d2(d); //通过已有的deque对象初始化 deque<int> d3(d.begin(),d.begin()+5); //将迭代器区间[first,last)里的元素复制到d3对象来初始化
（2）添加元素
void push_back(const T&); //向尾端添加一个元素 void push_front(const T&); //向头部添加一个元素 iterator insert(iterator pos,const T&x); //向pos位置之前插入元素x
（3）遍历访问
数组形式、迭代器形式，同vector
反向遍历，同vector
（4）删除元素
void pop_front(); //删除deque第一个元素 void pop_back(); //删除最后一个元素 iterator erase(iterator pos); //删除pos所指位置元素 iterator erase(iterator first,iterator last); //删除 [first,last) void clear(); //删除所有元素
（5）
没有capacity方法
1.3 list双向链表
向任意位置插入、删除，复杂度都是O(1)
list的初始化、添加元素、删除都类似vector、deque
遍历只能用迭代器
（1）
①list交换---swap
②list的归并
void splice(iterator pos,list& x) //将x的链表归并到当前链表的pos位置之前，x将被清空 void splice(iterator pos,list&,iterator i) //将一个list迭代器i所指元素归并到当前list链表中，并将被归并的元素从原链中删除 void merge(list &x) //将x的链表归并到当前链表中，并清空x的链表。只有当前链表和被归并的x链表元素事先都是升序排列的，这个函数才有意义，归并后也是升序
例程：
list<int> list1;
for(int j=1;j<=3;j++) {
list1.push_back(j);
}
list<int> list2;
list2.push_back(11);
list2.push_back(20);
list2.push_back(30);
list2.merge(list1);
//list1清空了,list2现在是按升序排列（1,2,3,11,20,30）
③list排序
list1.sort(); //升序排序
④连续重复元素删除，只保留一个
list1.unique();
1.4 forward_list 单向链表
在单向链表中添加、删除元素比双向链表要麻烦，需要两个迭代器：一个指向要处理的元素、一个指向其前驱
对一个元素删除时，应对其前面的迭代器调用 erase_after
flist.befor_begin(); //首元素之前不存在的元素迭代器(用来删除首元素)，对此迭代器不能解引用
flist.insert_after(iterp,x);//在迭代器iterp后插入元素x
flist.insert_after(iterp,n,x);//同上，插入n个
flist.insert_after(iterp,itera,iterb); //在iterp之后插入[itera,iterb) itera、iterb不能指向flist内
flist.insert_after(iterp,{1,2,3});//同上。 返回指向最后一个插入元素的迭代器 iterp不能是尾后迭代器end()
emplace_after(iterp,x); //用x在iterp指定位置后创建一个元素，返回指向新元素的迭代器
flist.erase_after(iterp); //删除iterp后面的一个元素
flist.erase_after(iterb,itere); //删除[iterp,itere) 返回被删元素之后的迭代器
两个例子：遍历删除list和forw_list中的元素
1 list<int> list1 = {1,2,3,4,5,6};
2 list<int>::iterator cur = list1.begin();
3 while(cur != list1.end()) {
4 if(*cur % 2) {
5 cur = list1.erase(cur); //erase返回被删除元素原来位置的下一个位置
6 }
7 else {
8 ++cur;
9 }
10 }
11
12 //forward_list需要两个迭代器操作
13 forward_list<int> flist = {1,2,3,4,5,6};
14 forward_list<int>::iterator flistpre = flist.before_begin();
15 forward_list<int>::iterator flistcur = flist.begin();
16 while(flistcur != flist.end()) {
17 if(*flistcur % 2) {
18 flistcur = flist.erase_after(flistpre);
19 }
20 else {
21 flistpre = flistcur;
22 ++flistcur;
23 }
24 }
1.5 array
1.6 string
（1）初始化
（2）添加
void push_back(char c); //添加字符c string & append(const char *s); //追加字符串s string & append(const string & s); //追加s对象的字符串 iterator insert(iterator pos,const char &c);//在指定位置之前插入字符c
（3）访问
有数组形式、前向迭代器、反向迭代器
（4）删除
（5）替换
string & replace(size_type pos,size_type n,const char *s);//从pos开始的n个字符替换为字符串s string & replace(size_type pos,size_type n,size_type n1,char c);//从pos开始的n个字符，替换为n1个字符c string & replace(iterator first,iterator last,const char *s);//将[first,last)间的字符替换为字符串s
（6）查找
size_type find(const char *s,size_type pos=0);//从pos位置开始查找子串s，返回位置索引或-1 size_type find(char c,size_type pos=0); //从pos位置开始找字符c的索引位置 无则返回-1 size_type rfind(const char *s,size_type pos=string::npos);//从pos位置开始反向查找 size_type rfind(char c,size_type pos=string::npos);//从pos位置开始反向查找 size_type find_first_of(const char *s,size_type pos=0);//从pos开始查找第一个位于子串s的字符 size_type find_first_not_of(const char *s,size_type pos=0);//查找第一个不在s里面的字符的位置 size_type find_last_of(const char *s,size_type pos=string::npos);//从pos开始查找最后一个位于子串s的字符 size_type find_last_not_of(const char *s,size_type pos=string::npos);//查找最后一个不在s里面的字符的位置
（7）比较
int compare(const stirng &s); //相等，0 大于s，1 小于s，-1 int compare(size_type pos,size_type n,const string &s); //当前字符串从pos开始的n个字符 与字符串s比较 int compare(const char *s);//当前字符串与字符串s比较
（8）字符串对象转C字符数组
const char* c_str()
1.7 注意事项
添加或删除元素后迭代器会失效，必须在进行改变容器的操作后都重新定位迭代器。
循环结束条件，需要每次判断迭代器不等于end() 而不能实现保存end()的值，因为添加、删除操作后end()变化了
2. 关联容器 associative container
set或者map
关键值是否能重复：能重复的带 multi
元素有序或无序：无序的带 unordered 无序容器用 哈希函数(散列) 组织元素，有序容器用 红黑树 组织
2.1 map
键值不重复、有序的关联容器，红黑树实现
有前向和反向迭代器 iterator、const_iterator、reverse_iterator、const_reverse_iterator
（1）创建、初始化
map<string,int> map1; //空的key对象为string，value为int，键值比较函数对象是默认的 less
map<string,int,greater<string>> map2; //空的map对象，键值比较函数对象是greater
map<string,int,my_func> map3; //创建空对象，并设置自定义的键值比较函数
map<string,int> map2(map2); //拷贝构造函数，利用已有对象创建另一个
pair<string,int> p1("a",1);
pair<string,int> p2("b",2);
pair<string,int> parray[] = {p1,p2};
map<string,int> map4(parray,parray+2); //利用迭代器[first,last)创建
设置自定义的键值比较函数对象的初始化：
struct strLess2 {
bool operator()(string s1,string s2) const {
int a = s1.compare(s2);
return (a<0); //string对象按字典升序排列
}
};
map<string,int,strLess2> mapa;
mapa.insert({"xy",1});
mapa.insert({"ab",2});
（2）添加元素
添加元素，可插入单个，也可以通过迭代器区间的方式插入。关键在于插入的数据元素是pair类型。map是键值无重复的，无法插入已有的键值
map1.insert({"abc",1});
map1.insert(make_pair("abc",1));
map1.insert(pair<string,int>("mn",1));
map1.insert(map<string,int>::value_type("mnb",1));
insert、emplace插入单个元素，返回一个pair，其first成员是迭代器，指向具有给定键值的元素，second成员是false表示插入失败(map中已有此键值)，是true表示插入成功。
比如对于string做键，int做值的map1，返回类型是 pair<map<string,int>::iterator,bool>
（3）删除元素
删除某迭代器位置上的元素、等于某键值的元素、迭代器区间上的元素、容器中所有元素
void erase(iterator pos); size_type erase(const key_type& key); //返回1 void erase(iterator first,iterator last); //[first,last) void clear();
（4）遍历访问
可通过数组形式和迭代器形式
①数组形式：以一个关键值作为下标进行访问或操作对应的值，如果此键值不在map中，则会创建此键值对
map1["ab"]; //返回键值为"ab"的对应的值，如果没有此键，则添加一个键并初始化值
map1.at("ab"); //若此键不在map中，则抛出out_of_range异常
用数组形式访问返回左值，可读可写。一般解引用迭代器返回的类型和下标运算符返回类型一致，但map不同：下标操作返回mapped_type对象，解引用迭代器返回value_type对象
下标和at操作只适用于非const的map和unordered_map
②反向遍历
（5）搜索 O(log n)
iterator find(const key_type& key) const; //返回第一个键为key的元素，若没有此键，则返回尾后迭代器 int count(const key_type& key) const; //键为key的元素的数量，对不允许键重复的容器，返回0或1 iterator lower_bound(key); //返回迭代器，指向第一个键不小于key的元素 iterator upper_bound(key); //返回迭代器，指向第一个键大于key的元素 iterator equal_range(key); //返回迭代器pair，表示关键字等于k的元素范围，若无此key，pair两个成员都是end()
2.2 multimap
红黑树实现，只是键值可重复
操作类似map，但不能用数组下标访问元素
2.3 set
与map类似，也是红黑树实现（根大于左孩子，小于右孩子），元素检索使用二叉搜索树的中序遍历，效率比vector、deque、list等顺序容器，由于中序遍历有序，因此set容器元素有序
set的初始化、添加元素、迭代器遍历都类似map，只是set只有键，而不是键值对
插入元素返回pair对象，提供所插入元素迭代器位置和成功标志
2.4 multiset
类似set
插入元素返回相应的迭代器位置，而不是含成功标志的pair对象
2.5 unordered_map
利用哈希函数实现，搜索平均性能比map好，占用内存可能比map高（C++ STL中还有一个hash_map，和unordered_map很像，只不过unordered_map是C++ 11标准）
无序容器在存储上组织成一组桶，每个桶保存0个或多个元素。无序容器使用哈希函数将元素映射到桶，若是multimap、multiset则有相同关键值的元素在同一个桶中。访问元素时，先计算哈希值找到桶。
无序容器有管理桶的成员函数：查询容器状态、强制容器重组
其他如创建、添加、遍历、删除等接口类似map
无序容器对键的要求：
无序容器重载 == 运算符来比较元素
可使用内置类型，还包括指针、string、智能指针作为键（都对其提供了对应的hash模板）。如想定义关键字为自定义类型，需要自己写hash模板
2.6 unordered_set、unordered_multimap、unordered_multiset
3. 容器适配器
stack、queue、priority_queue
通过现有的序列容器实现（stack使用deque），可看作适配器，将一种容器转换成另一种容器
3.3 priority_queue 优先队列容器
队列中最大的元素位与队首，每次出队时是最大元素先出队（底层是vector实现）
内容总结
以上是互联网集市为您收集整理的C++标准模板库里面的容器全部内容，希望文章能够帮你解决C++标准模板库里面的容器所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。