1. 关联式容器
- vector、list、deque、forward_list 等容器统称为序列式容器,因为底层是线性序列的数据结构,里面存储的是元素本身。
- 关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是**<key, value>结构的键值对**,在数据检索比序列式容器效率更高,例如 set、map、unordered_set、unordered_map 等。
- 注意:C++ STL 当中的 stack、queue 和 priority_queue 属于容器适配器,它们默认使用的基础容器分别是 deque、vector。
2. 树形结构与哈希结构
根据应用场景的不同,C++ 的 STL 容器总共实现了两种不同结构的关联式容器:树型结构和哈希结构。
| 关联式容器 | 容器结构 | 底层实现 |
|---|
| set、map、multiset、multimap | 树型结构 | 平衡搜索树 (红黑树) |
| unordered_set、unordered_map、unordered_multiset、unordered_multimap | 哈希结构 | 哈希表 |
其中,树型结构容器中的元素是一个有序的序列,而哈希结构容器中的元素是一个无序的序列。
3. 键值对
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量 key 和 value,key 代表键值,value 表示与 key 对应的信息。
4. Set And MultiSet
4.1. set 的使用
- set 是按照一定次序存储元素的容器。
- 在 set 中,元素的 value 也标识它 (value 就是 key,类型为 T),并且每个 value 必须是唯一的。set 中的元素不能在容器中修改 (元素总是 const),但是可以从容器中插入或删除它们。
- 在内部,set 中的元素总是按照其内部比较对象 (类型比较) 所指示的特定严格弱排序准则进行排序。
- set 容器通过 key 访问单个 key 元素的速度通常比 unordered_set 容器慢,但它们允许根据顺序对子集进行直接迭代。
- set 在底层是用二叉搜索树 (红黑树) 实现的。
4.1.1. set 的模版参数列表
- T: set 中存放元素的类型,实际在底层存储<value,value>的键值对。
- Compare: set 中元素默认按照小于来比较。
- Alloc: set 元素空间的管理方式,使用 STL 提供的空间配置器进行管理。
4.1.1.1. set 的构造
#include <iostream>
using namespace std;
#include <set>
#include <vector>
void TestConstructor() {
set<int> s1;
vector<int> v1 = { 1,2,3,4,5,5,6,7,7 };
set<int> s2(v1.begin(), v1.end());
set<int> s3(s2);
for(auto & element : s2) cout << element << " ";
cout << endl;
for (auto& element : s3) cout << element << " ";
cout << endl;
}
int main() {
TestConstructor();
}
4.1.1.2. set 的迭代器
#include <iostream>
using namespace std;
#include <set>
#include <vector>
void TestIterator() {
vector<int> v1 = { 1,2,3,4,5,5,6,7,7 };
set<int> s1(v1.begin(), v1.end());
set<int>::iterator it = s1.begin();
while(it != s1.end()) {
cout << *it << " ";
it++;
}
cout << endl;
set<int>::reverse_iterator rit = s1.rbegin();
while (rit != s1.rend()) {
cout << *rit << " ";
rit++;
}
cout << endl;
}
int main() {
TestIterator();
}
4.1.1.3. set 的容量
#include <iostream>
using namespace std;
#include <set>
#include <vector>
void Test_Capacity() {
vector<int> v1 = { 1,8,9,7,5,6,4,3,2 };
set<int> s1(v1.begin(), v1.end());
cout << s1.size() << endl;
cout << s1.empty() << endl;
}
int main() {
Test_Capacity();
}
4.1.1.4. set 的修改
#include <iostream>
using namespace std;
#include <set>
#include <vector>
void Test_Modification() {
set<int> s1;
s1.insert(1);
s1.insert(2);
s1.insert(3);
s1.insert(5);
s1.insert(6);
s1.insert(7);
s1.insert(25);
for (auto& element : s1) cout << element << " ";
cout << endl;
set<int>::iterator Position = s1.find(2);
s1.erase(Position);
Position = s1.find(3);
size_t count = s1.erase(3);
cout <<"删除的元素个数:>" << count << endl;
for (auto& element : s1) cout << element << " ";
cout << endl;
cout << << s() << endl;
}
{
();
}
4.1.1.5. set 的其他操作
#include <iostream>
using namespace std;
#include <set>
#include <vector>
void Test_Operation() {
set<int> s1;
s1.insert(1);
s1.insert(2);
s1.insert(3);
s1.insert(5);
s1.insert(6);
s1.insert(7);
s1.insert(25);
set<int>::iterator it = s1.find(5);
for (auto& element : s1) cout << element << " ";
cout << endl;
if (s1.end() != it) {
cout << *it << endl;
s1.erase(it);
} else cout << "找不到" << endl;
for(auto & element : s1) cout << element << " ";
cout << endl;
for (size_t i = 1; i < ; i++) {
s(i * );
}
( element : s1) cout << element << ;
cout << endl;
set<>::iterator itlow = sower_bound();
set<>::iterator itup = s();
s(itlow, itup);
(& element : s1) cout << element << ;
cout << endl;
}
{
();
}
4.2. multiset
- multiset 是按照特定顺序存储元素的容器,其中元素是可以重复的。
- 在 multiset 中,元素的 value 也会识别它 (因为 multiset 本身存储的是<value,value>组成的键值对,因此 value 本身就是 key,key 就是 value,类型为 T)。multiset 的元素的值不能在容器中进行修改 (因为元素总是 const 的),但可以从容器中插入或者删除。
- 在内部,multiset 中的元素总是按照内部比较规则 (类型比较) 所指示的特定严格弱排序准则进行排序。
- multiset 容器通过 key 访问单个元素的速度通常比 unordered_multiset 容器慢,但当使用迭代器遍历时会得到一个有序序列。
- multiset 底层结构为红黑树。
PS:
- multiset 中在底层中存储的是<value,value>的键值对。
- multiset 的插入接口中只需要插入即可。
- 与 set 的区别是,multiset 的元素可以重复,set 中 value 是唯一的。
- multiset 中的元素不能被修改。
#include <iostream>
using namespace std;
#include <set>
#include <vector>
void Test_MultiSet() {
multiset<int> s1;
s1.insert(1);
s1.insert(1);
s1.insert(3);
s1.insert(2);
s1.insert(5);
s1.insert(7);
s1.insert(9);
s1.insert(15);
s1.insert(35);
for (auto& element : s1) cout << element << " ";
}
int main() {
Test_MultiSet();
}
4.3. Map And MultiMap
- map 是关联容器,它按照特定的次序 (按照 key 来比较) 存储由键值 key 和值 value 组合而成的元素。
- 在 map 中,键值 key 通常用于排序和唯一地标识元素,而值 value 中存储与此键值 key 关联的内容。键值 key 和值 value 的类型可能不同,并且在 map 的内部,key 与 value 通过成员类型 value_type 绑定在一起,为其取别名称为pair:typedef pair<const key,T>value_type;
- 在内部,map 中的元素总是按照键值 key 进行比较排序的。
- map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢,但 map 允许根据顺序对元素进行直接迭代 (即对 map 中的元素进行迭代时,可以得到一个有序的序列)。
- map 支持下标访问符,即在 [] 中放入 key,就可以找到与 key 对应的 value。
- map 通常被实现为二叉搜索树 (更准确的说:平衡二叉搜索树 (红黑树)).
4.3.1. map 的使用
key: 键值对中 key 的类型
T: 键值对中 value 的类型
Compare: 比较器的类型,map 中的元素是按照 key 来比较的,缺省情况下按照小于来比较,一般情况下 (内置类型元素) 该参数不需要传递,如果无法比较时 (自定义类型),需要用户自己显式传递比较规则 (一般情况下按照函数指针或者仿函数来传递).
Alloc: 通过空间配置器来申请底层空间,不需要用户传递,除非用户不想使用标准库提供的空间配置器.
注意:在使用 map 时,需要包含头文件。
4.3.1.1. map 的迭代器
#include <iostream>
using namespace std;
#include <map>
#include <vector>
void Test_MapIterator() {
map<string, string>m1;
pair<string, string>Kv1("Begin", "开始");
m1.insert(Kv1);
m1.insert(pair<string, string>("End", "结束"));
m1.insert(make_pair("Top", "顶部"));
m1.insert({ "Bottom","底部" });
map<string, string>::iterator it = m1.begin();
while (it != m1.end()) {
cout << (*it).first << ":" << it->second << endl;
++it;
}
}
int main() {
Test_MapIterator();
return 0;
}
4.3.1.2. map 的容量与元素访问
#include <iostream>
using namespace std;
#include <map>
#include <vector>
void The_Pricinple() {
map<string, string> dict;
dict.insert({ "string","字符串" });
dict["right"];
dict["left"] = "左边";
cout << dict["string"] << endl;
dict["right"] = "右边";
string str;
while (cin >> str) {
if (dict.count(str)) {
cout << "在字典里面" << endl;
} else {
cout << "不在字典里面" << endl;
}
}
}
int main() {
The_Pricinple();
return 0;
}
注意: 在元素访问时,有一个与 operator[] 类似的操作 at()(该函数不常用) 函数,都是通过 key 找到与 key 对应的 value 然后返回其引用,不同的是:当 key 不存在时,operator[] 用默认 value 与 key 构造键值对然后插入,返回该默认 value,at() 函数直接抛异常.
4.3.1.3. map 中元素的修改
#include <iostream>
using namespace std;
#include <map>
#include <vector>
void Test_Modify() {
map<string, string> Dictionary;
Dictionary.insert({ "apple","苹果" });
Dictionary.insert(pair<string, string>("banana", "香蕉"));
Dictionary.insert({"watermelon", "西瓜"});
Dictionary.insert({ "orange", "橙子" });
Dictionary.insert({ "lemon", "柠檬" });
for (auto& Kv : Dictionary) cout << Kv.first << ":>" << Kv.second << endl;
cout << "----------------------------" << endl;
Dictionary.erase("lemon");
Dictionary.erase("watermelon");
for (auto& Kv : Dictionary) cout << Kv.first << ":>" << Kv.second << endl;
}
int main() {
Test_Modify();
return 0;
}
4.3.2. Map 的总结
- map 中的元素总是键值对。
- map 中的 key 是唯一的,并且不能修改。
- 默认按照小于的方式对 Key 进行比较。
- map 中的元素如果用迭代器去进行遍历,可以得到一个有序的序列。
- map 的底层为红黑树,查找效率比较高。
- 支持 [] 操作符,operator[] 中实际进行插入查找。
4.3.3. Multimap
- Multimap 是关联式容器,它按特定的顺序,存储由 Key 和 value 映射成的键值对<key,value>,其中多个键值对之间的 key是可以重复的。
- 在 multimap 中,通过按照 key 排序和唯一地标识元素,而映射的 value 存储与 key 关联的内容,key 和 value 的类型可能不同,通过 multimap 内部的成员类型 value_type 组合在一起,value_type 是组合 key 和 value 的键值对:typedef pair<const Key, T> value_type;
- 在内部,multimap 的元素总是通过其内部比较对象,按照指定的特定严格弱排序对 key 进行排序
注意:multimap 和 map 的唯一不同就是:map 中的 key 是唯一的,而 multimap 中 key 是可以重复的。
4.3.3.1. Multimap 的使用
- multimap 中的key 是可以重复的。
- multimap 中的元素默认将 key 按照小于来比较。
- multimap 中没有重载 operator[] 操作.
- 使用时与 map 包含的头文件相同。
#include <iostream>
using namespace std;
#include <map>
#include <vector>
void Test_MultiMap() {
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
multimap<int, string> SortMap;
map<string, int> CountMap;
for (auto& element : arr) CountMap[element]++;
for (auto& kv : CountMap) SortMap.insert({ kv.second,kv.first });
for (auto& kv : SortMap) cout << kv.first << ":" << kv.second << endl;
cout << endl;
}
int main() {
Test_MultiMap();
return 0;
}