C++基础（15）——关联式容器的使用和介绍（set和map）
目录
一、相关概念
关联式容器
在c++stl库当中，我们会有序列式容器和关联式容器。
- 序列式容器：存储数据本身，底层使用线性结构，比如我们之前实现过的vector和list等。
- 关联式容器：存储的是一对键值对<key, value>，这种结构在我们检索的时候效率会大幅提高，比如：set、map、unordered_set、unordered_map等。
关联式容器的分类
我们根据使用的场景的不同，实现了两种不同的关联式容器：树形结构和哈希结构。
| 具体容器 | 结构 | 底层实现 |
|---|---|---|
| set, map, multiset, multimap | 树形结构，有序，唯一/允许重复键 | （平衡搜索二叉树）红黑树 |
| unordered_set, unordered_map, unordered_multiset, unordered_multimap | 树形结构，无序，唯一/允许重复键 | 哈希表 |
键值对
我们使用关联式容器的时候，最重要的就是使用键值对，这个结构一般含有两个成员：key(键)和value(值)，key唯一对应一个value。
这个就好比是我们的英汉字典，英文单词和中文释义一一对应。
在SGI-STL（标准模板库）中关于键值对的定义：
template <class T1, class T2>
struct pair {
T1 first; // 键
T2 second; // 值
// 构造函数
pair() : first(), second() {}
pair(const T1& a, const T2& b) : first(a), second(b) {}
};
二、set
💡相关概念
set常被用来作为数据去重的容器，也就是说set中存储的value都是唯一的。
set是有序的容器，也就是使用迭代器遍历得到的结果是有序的。
与map不同，set中的元素是不可被修改的，修改就破坏了二叉搜索树。
在底层set的使用使用的是二叉搜索树（红黑树），所以set的查找效率高（log(N)）。
💡set的定义
第一种：构造某个类型
set<int> s;第二种：拷贝构造
set<int> p(s);第三种：构造某一段内容
string str("hello world");
set<char> s_str(str.begin(), str.end());第四种：构造一个比较是大于的容器
set<int, greater<int>> sg;💡set的使用
| 函数/功能 | 描述 |
|---|---|
| insert(const T& value) | 插入一个元素，返回一个 pair，其中第二个元素是一个 bool，表示插入是否成功。 |
| erase(const T& value) | 删除指定元素。如果元素存在，删除并返回 1，否则返回 0。 |
| erase(iterator pos) | 删除指定位置的元素，返回删除元素后的下一个元素的迭代器。 |
| find(const T& value) | 查找指定元素，返回该元素的迭代器。如果元素不存在，返回 end()。 |
| count(const T& value) | 返回容器中指定元素的个数（对于 set，返回值为 0 或 1，因为 set 不允许重复元素）。 |
| lower_bound(const T& value) | 返回指向第一个大于或等于 value 的元素的迭代器。 |
| upper_bound(const T& value) | 返回指向第一个大于 value 的元素的迭代器。 |
| equal_range(const T& value) | 返回一个 pair，包含指向第一个大于或等于 value 的元素的迭代器和指向第一个大于 value 的元素的迭代器。 |
| size() | 返回 set 中元素的个数。 |
| empty() | 判断 set 是否为空，返回 true 或 false。 |
| clear() | 清空容器中所有元素。 |
迭代器相关函数：
| begin() | 返回指向容器中第一个元素的迭代器。 |
| end() | 返回指向容器中最后一个元素之后位置的迭代器。 |
| rbegin() | 返回指向容器中最后一个元素的逆向迭代器。 |
| rend() | 返回指向容器中第一个元素之前位置的逆向迭代器。 |
我们这里举个栗子：
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
s.insert(1);
s.insert(1);
s.insert(2);
s.insert(2);
s.insert(4);
s.insert(4);
s.insert(3);
for(auto e : s) {
cout << e << " ";
}
cout << endl;
// 删除方式一
s.erase(2);
// 删除方式二
set<int>::iterator pos = s.find(3);
if(pos != s.end()) {
s.erase(pos);
}
set<int>::iterator it = s.begin();
while(it != s.end()) {
cout << *it << " ";
it++;
}
cout << endl;
cout << s.count(1) << endl;
cout << s.size() << endl;
s.clear();
cout << s.empty() << endl;
set<int> temp{10, 8, 2, 6, 9, 1, 3, 5};
s.swap(temp);
set<int>::reverse_iterator rit = s.rbegin();
while(rit != s.rend()) {
cout << *rit << " ";
rit++;
}
cout << endl;
auto x = s.lower_bound(8);
auto y = s.upper_bound(8);
cout << *x << " " << *y << endl;
return 0;
}测试效果：
三、multiset
我们的multiset容器的底层实现和set容器的底层实现是一样的，都是使用的平衡搜索二叉树，我们这里唯一的一个区别就是multiset支持键值对的冗余，也就是说我们的存储元素可以重复了。
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> s;
s.insert(1);
s.insert(1);
s.insert(2);
s.insert(2);
s.insert(4);
s.insert(4);
s.insert(3);
for(auto& e : s) {
cout << e << " ";
}
cout << endl;
return 0;
}测试效果：
这里我们改变了原来的规则，那么find和count函数就会不太一样了：
| 函数 | 容器类型 | 功能说明 | 返回值 |
|---|---|---|---|
find |
set |
查找是否存在指定元素，返回迭代器 | 指向元素的迭代器或 end()（至多一个元素） |
multiset |
查找是否存在指定元素，返回第一个匹配的迭代器 | 指向第一个匹配元素的迭代器或 end()（可能有多个匹配元素） |
|
count |
set |
返回指定元素的个数（只能是 0 或 1，所以可以替换掉find） | 0 或 1 |
multiset |
返回指定元素的出现次数 | 元素出现次数（可能大于 1） |
四、map
💡相关概念
我们的map中是需要传入键值对的，而不是传入value。
我们的map也可以按章一定的次序来存储键值对key和value，使用迭代器遍历就可以得到有序的序列了（通过key比较）。
map中的key是不可被修改的，但是我们的value是可以被修改的，因为底层实现是使用key构建的。
map是支持下标访问的，也就是在[]中放入key就可以找到对应的value。
💡map的定义方式
第一种：指定key和value的类型构造一个容器。
map<int, double> m;第二种：拷贝构造
map<int, double> m_copy(m);第三种：使用迭代器拷贝构造
map<int, double> m_s(m.begin(), m.end());第四种：比较方式用大于
map<int, double, greater<int>> m_g(m);💡map的插入
map的插入函数的原型如下：
pair<iterator, bool> insert(const value_type& val);insert函数的参数是value_type类型的，实际上就是pair类型的别名。
typedef pair<const Key, T> value_type;所以我们插入的时候，是要用key和value构造出来一个pair对象，然后再将pair对象作为参数传入insert函数中。
第一种：构造匿名对象插入
#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;
int main() {
map<int, string> m;
m.insert(pair<int, string>(1, "hello"));
m.insert(pair<int, string>(2, " world"));
m.insert(pair<int, string>(3, "!"));
for(auto& e : m) {
cout << "<" << e.first << ":" << e.second << ">" << " ";
}
cout << endl;
return 0;
}测试效果如图：
第二种：调用make_pair函数模版插入
我们的库函数提供了make_pair的函数模板：
template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y) {
return pair<T1, T2>(x, y);
}所以我们可以使用make_pair函数传入key和value来构造对应的pair对象。
#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;
int main() {
map<int, string> m;
m.insert(make_pair(1, "hello"));
m.insert(make_pair(2, " world"));
m.insert(make_pair(3, "!"));
for(auto& e : m) {
cout << "<" << e.first << ":" << e.second << ">" << " ";
}
cout << endl;
return 0;
}我们这里来介绍一下我们的insert函数的返回值的含义：
我们的insert函数的返回值也是一个pair对象，该对象的第一个参数是map的迭代器类型，第二参数是bool类型，具体的返回情况如下：
如果要插入的元素在map中不存在，则我们插入成功，返回插入后元素的迭代器和true。
如果要插入的元素在map中存在了，则我们插入失败，返回map中键值为key的元素的迭代器和false。
💡map的查找
map的查找函数的原型如下：
iterator find(const key_type& k);map的查找函数是根据所给的key值在map中找的，找到了就返回该元素的迭代器，没找到就返回容器最后一个元素下个位置的迭代器。
我们这里也举个栗子：
#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;
int main() {
map<int, string> m;
m.insert(make_pair(1, "hello"));
m.insert(make_pair(2, " world"));
m.insert(make_pair(3, "!"));
map<int, string>::iterator pos = m.find(2);
if(pos != m.end()) {
cout << pos->second << endl;
}
return 0;
}测试效果如图：
💡map的删除
map的删除函数的原型如下：
// 第一种
size_type erase(const key_type& k);
// 第二种
void erase(iterator position)我们这里有两种删除的函数，一个是传入指定的key值删除指定的元素，返回值就是删除元素的个数，也可以根据迭代器删除。
我们这里举个栗子：
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<int, string> m;
m.insert(make_pair(1, "hello"));
m.insert(make_pair(2, " world"));
m.insert(make_pair(3, "!"));
m.erase(2);
map<int, string>::iterator pos = m.find(1);
if(pos != m.end()) {
m.erase(pos);
}
for(auto& e : m) {
cout << "<" << e.first << ":" << e.second << ">" << " ";
}
return 0;
}测试效果如图：
💡map的[ ]运算符重载
map的[ ]运算符重载函数的原型如下：
mapped_type& operator[] (const key_type& k);我们来分析一下这些参数，首先我们插入的参数就是key，返回值就是下面这个：
(*((this->insert(make_pair(k, mapped_type()))).first)).second我们这样直接看还是太过复杂了，我们其实可以分解整理一下就很好理解了，其实就是分了三个步骤：
1、调用insert插入键值对
2、根据insert函数的返回值拿到对应的迭代器
3、根据迭代器就可以拿到value了
对应的代码分析如下：
mapped_type& operator[](const key_type& k) {
// 调用insert函数插入键值对，然后存一下返回值
pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
// 拿出insert函数的迭代器
iterator it = ret.first;
// 根据迭代器位置的元素拿到value
return it->second;
}我们这里也来举个栗子：
#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;
int main() {
map<int, string> m;
m.insert(make_pair(1, "hello"));
m.insert(make_pair(2, " world"));
m.insert(make_pair(3, "!"));
m[2] = "xywl";
m[4] = "!!";
for(auto& e : m) {
cout << "<" << e.first << ":" << e.second << ">" << " ";
}
cout << endl;
return 0;
}我们这里来总结一下:
1、如果我们的key不在map中，那么我们进行插入。
2、如果我们的key在map中了，就会返回key对应的value对象的引用了。
💡map的迭代器遍历
map中的迭代器相关函数如下：
| 函数/功能 | 描述 |
|---|---|
| begin() | 返回指向容器中第一个元素的迭代器。 |
| end() | 返回指向容器中最后一个元素之后位置的迭代器。 |
| rbegin() | 返回指向容器中最后一个元素的逆向迭代器。 |
| rend() | 返回指向容器中第一个元素之前位置的逆向迭代器。 |
第一种遍历的方式：用正向迭代器进行遍历
代码如下：
#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;
int main() {
map<int, string> m;
m.insert(make_pair(1, "hello"));
m.insert(make_pair(2, " world"));
m.insert(make_pair(3, "!!!"));
map<int, string>::iterator it = m.begin();
while(it != m.end()) {
cout << "<" << it->first << ":" << it->second << ">" << " ";
it++;
}
cout << endl;
return 0;
}测试效果如图：
第二种遍历方式：使用反向迭代器遍历
代码如下：
#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;
int main() {
map<int, string> m;
m.insert(make_pair(1, "hello"));
m.insert(make_pair(2, " world"));
m.insert(make_pair(3, "!!!"));
map<int, string>::reverse_iterator rit = m.rbegin();
while(rit != m.rend()) {
cout << "<" << rit->first << ":" << rit->second << ">" << " ";
rit++;
}
cout << endl;
return 0;
}测试效果如图：
第三种遍历方式：使用范围for遍历
代码如下：
#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;
int main() {
map<int, string> m;
m.insert(make_pair(1, "hello"));
m.insert(make_pair(2, " world"));
m.insert(make_pair(3, "!!!"));
for(auto& e : m) {
cout << "<" << e.first << ":" << e.second << ">" << " ";
}
cout << endl;
return 0;
}测试效果如图：
💡map的其他成员函数
| 函数 | 描述 | 返回值类型 | 备注 |
|---|---|---|---|
| size() | 返回 map 中元素的个数（即键值对的数量）。 |
size_t |
返回容器中元素的数量。 |
| empty() | 判断 map 是否为空。 |
bool |
如果容器为空，返回 true，否则返回 false。 |
| clear() | 清空 map 中所有元素。 |
void |
清空容器后，容器中的元素数量为 0。 |
| swap(map& m) | 交换当前 map 与另一个 map 的内容。 |
void |
交换两个 map 容器的内容，执行后两个容器的内容被交换。 |
| count(const Key& key) | 返回容器中指定键的元素个数（对于 map，返回值为 0 或 1）。 |
size_t |
map 中的键是唯一的，因此返回值只能是 0 或 1。 |
我们这里也举一个栗子：
#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;
int main() {
map<int, string> m;
m.insert(make_pair(1, "hello"));
m.insert(make_pair(2, " world"));
m.insert(make_pair(3, "!!!"));
cout << m.size() << endl;
cout << m.count(2) << endl;
m.clear();
cout << m.empty() << endl;
map<int, string> temp;
m.swap(temp);
return 0;
}测试效果如下：
五、multimap
multimap的实现和map的底层实现是一样的，也就是我们提到的平衡搜索二叉树（红黑树）结构，接口也是一样的，我们这里重点还是说一说它们的区别之处，那就是multimap是允许键值的冗余的，也就是说我们存储的元素是可以有重复值的。
我们这里也是来举个栗子：
#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;
int main() {
multimap<int, string> m;
m.insert(make_pair(1, "hello"));
m.insert(make_pair(2, " world"));
m.insert(make_pair(3, "!!!"));
m.insert(make_pair(3, "..."));
for(auto& e : m) {
cout << "<" << e.first << ":" << e.second << ">" << " ";
}
cout << endl;
return 0;
}测试效果如图：
和我们上面说到的set容器一样，我们的map和multimap的find函数和count函数的意义也出现了不同之处：
| 函数 | 容器类型 | 功能描述 | 返回值 |
|---|---|---|---|
find |
map |
查找指定键的元素，返回该元素的迭代器，若元素不存在返回 end()。 |
指向元素的迭代器或 end()（至多一个元素） |
multiset |
查找指定元素，返回 第一个匹配元素 的迭代器，若元素不存在返回 end()。 |
指向第一个匹配元素的迭代器或 end()（可能有多个匹配元素） |
|
count |
map |
返回指定键的元素个数（对于 map，返回值为 0 或 1）。 |
0 或 1 |
multiset |
返回指定元素的出现次数（允许重复元素）。 | 元素出现次数（可能大于 1） |
敲黑板：
我们的multimap因为允许键值的冗余，所以我在使用[ ]的时候会产生歧义，所以我们的实现中没有实现这个运算符的重载。
更多推荐
36
0- 0
已为社区贡献6条内容
所有评论(0)