目录
一 基础概念
1 关联式容器
STL中的部分容器，比如：vector、list、deque等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的 键值对，在数据检索时比序列式容器效率更高。
2 键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代 表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然 有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应 该单词，在词典中就可以找到与其对应的中文含义。
SGI-STL中关于键值对的定义
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair() : first(T1()), second(T2())
{}
pair(const T1& a, const T2& b) : first(a), second(b)
{}
};
3 树形结构的关联式容器
根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结 构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列
二 map
1 概念
1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair : typedef pair<const key, T> value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
map的查询效率是O(log_2N)是正确的，但map的底层结构不是二叉搜索树，而是红黑树
2 基础操作
注意：在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过 key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]用默认 value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常。
3 使用实列
1 实例一
void test_map1()
{
map<string, string> dict;
dict.insert(pair<string, string>("sort", "排序"));
//pair<string, string> kv("string", "字符串");
pair<string, string> kv = { "string", "字符串" };
dict.insert(kv);
// C++11 多参数隐式类型转换(构造函数)
dict.insert({ "apple", "苹果" });
// C++98
dict.insert(make_pair("sort", "排序"));
//map<string, string>::iterator it = dict.begin();
auto it = dict.begin();
while (it != dict.end())
{
//cout << (*it).first << (*it).second << endl;
cout << it->first << it->second << endl;
++it;
}
cout << endl;
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
int main()
{
/*test_set1();*/
/*test_set2();*/
/*test_set3();*/
test_map1();
return 0;
}
2 实例二
void test_map2()
{
// key相同，value不同，不会插入也不会更新
map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字符串"));
dict["left"]; // 插入
cout << dict["sort"] << endl; // 查找
dict["sort"] = "xxx"; // 修改
dict["right"] = "右边"; // 插入+修改
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
int main()
{
/*test_set1();*/
/*test_set2();*/
/*test_set3();*/
/*test_map1();*/
test_map2();
return 0;
}
3 实例三
void test_map3()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "西瓜", "香蕉", "草莓" };
map<string, int> countMap;
//统计个数
//方法1
//for (auto& e : arr)
//{
// map<string, int>::iterator it = countMap.find(e);
// if (it != countMap.end())
// {
// it->second++;
// }
// else
// {
// countMap.insert(make_pair(e, 1));
// }
//}
//方法2
//for (auto& e : arr)
//{
// pair<map<string, int>::iterator, bool> ret;
// ret = countMap.insert(make_pair(e, 1));
// // 已经存在了
// if (ret.second == false)
// {
// ret.first->second++;
// }
//}
//方法3
for (auto& e : arr)
{
countMap[e]++;
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
int main()
{
/*test_set1();*/
/*test_set2();*/
/*test_set3();*/
/*test_map1();*/
test_map3();
return 0;
}
而[ ] 底层大概这样
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}4 实例四
降序
int main()
{
map<int, int, greater<int>> m;
m.insert(make_pair(1, 2));
m.insert(make_pair(2, 2));
m.insert(make_pair(3, 2));
m.insert(make_pair(4, 2));
m.insert(make_pair(5, 2));
for (auto& e : m)
{
cout << e.first << ' ' ;
}
return 0;
}
4 multimap
Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key,value>，其中多个键值对之间的key是可以重复的。
注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。
multimap中的接口可以参考map，功能都是类似的。
注意：
1. multimap中的key是可以重复的。
2. multimap中的元素默认将key按照小于来比较
3. multimap中没有重载operator[]操作。
4. 使用时与map包含的头文件相同
1 实例一
void test_map4()
{
multimap<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("sort", "xxx"));
dict.insert(make_pair("sort", "排序"));
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
int main()
{
/*test_set1();*/
/*test_set2();*/
/*test_set3();*/
/*test_map1();*/
/*test_map3();*/
test_map4();
return 0;
}
三 set
1 概念
1. set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
5. set在底层是用二叉搜索树(红黑树)实现的
注意：
1. 与map / multimap不同，map / multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列
5. set中的元素默认按照小于来比较
6. set中查找某个元素，时间复杂度为：$log_2 n$
7. set中的元素不允许修改
元素的哈希性要求： 在集合中，元素的存储和查找依赖于哈希值。为了保持高效的查找和插入操作，集合要求所有元素必须是可哈希的（即哈希值在其生命周期中保持不变）。如果允许修改集合中的元素，元素的哈希值可能会发生变化，这将破坏集合的结构，导致查找和操作失效。因此，集合要求其元素是不可变的对象
8. set中的底层使用二叉搜索树(红黑树)来实现。
2 基础操作
3 使用实例
1 实例一
void test_set1()
{
// 排序+去重
set<int> s;
s.insert(5);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(4);
s.insert(5);
s.insert(1);
set<int>::iterator it = s.begin();
//找不到返回s.end()
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
set<int>::iterator pos = s.find(5);
//找不到返回s.end()
if (pos != s.end())
{
cout << "找到了" << endl;
s.erase(pos);
}
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
// 在就删除，不在就不做任何处理
s.erase(3);
s.erase(30);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
// 这个值在，找到有效位置，再进行删除
//pos = s.find(5);
//s.erase(pos);
//count--> 返回该元素个数 有返回1 没有返回0
if (s.count(5))
{
cout << "在" << endl;
}
else
{
cout << "不在" << endl;
}
}
int main()
{
test_set1();
return 0;
}
2 实例二
void test_set2()
{
// 排序+去重
set<int> s;
s.insert(5);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(4);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
auto start = s.lower_bound(3); // 返回 >=val 的值
cout << *start << endl;
auto finish = s.upper_bound(5); // 返回 >val 的值
cout << *finish << endl;
//找 [3, 5]区间的数
while (start != finish)
{
cout << *start << " ";
++start;
}
cout << endl;
start = s.lower_bound(3);
//删除[3, 5]区间的数字
s.erase(start, finish);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
/*test_set1();*/
test_set2();
return 0;
}
3 实例三
#include<set>
int main()
{
set<int, greater<int>> s = { 1, 2, 3, 4, 5 };
for (auto e : s)
{
cout << e << ' ';
}
return 0;
}
4 multiset
multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
multiset底层结构为二叉搜索树(红黑树)。
操作可以参考set
1 实例一
void test_set3()
{
// 排序
multiset<int> s;
s.insert(5);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(4);
s.insert(5);
s.insert(1);
s.insert(1);
s.insert(5);
s.insert(1);
s.insert(1);
s.insert(2);
s.insert(7);
s.insert(10);
multiset<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//count 返回该value的个数
cout << s.count(5) << endl;
cout << s.count(1) << endl;
it = s.find(5);
while (it != s.end() && *it == 5)
{
cout << *it << " ";
++it;
}
cout << endl;
}
int main()
{
/*test_set1();*/
/*test_set2();*/
test_set3();
return 0;
}
本节是对后面的hash 的过度, 内容还是很简单的, 后续还会模拟实现它们, 继续加油!