C++ - map,set
set和map介绍
map 和 set 是C++ STL 中提供的容器, map 和 set 的底层是基于红黑树来实现的.
set 是一个包含唯一元素 (key) 的集合，不允许有重复的元素.
map 是一个键值对 (key - value) 的集合, 每一个键 (key) 都是唯一的.
map 的key - value键值对是通过 pair 来实现的.
可以观察到, map 比 set 多一个模板参数.
set 只有 T, 而 map 有key 和 T.
set 和 map 底层既然是基于 红黑树 来实现的, 那么set 和 map 中的数据都是唯一且有序的, 并不允许存在重复的数据. set 和 map 也不持支改的操作, 只支持增删查.
pair结构
map 中存储的数据是键值对. 而 pair 实际上就是一个键值对的结构.
所以在 map 中实际存储的类型就是 pair.
pair是一个模板类，用于存储两个相关联的值.
可以看到 pair 有两个类型模板参数 T1 和 T2.
template<class T1, class T2>
struct pair
{
T1 first;
T2 second;
pair()
:first(T1()),
second(T2())
{}
pair(const T1& a, const T2& b)
:first(a),
second(b)
{}
};可以看到就是一个非常简单的数据结构, 里面存储两个变量, 没啥特别的.
两个变量的类型可以相同也可以不同, 使用灵活.
map 中就是使用这个 pair 结构来存储 key 和 value 的.
first 对应 key
second 对应 value.
map使用
map 的插入, 调用 insert 成员函数.
插入成功, 就会返回一个 pair 类型的数据.
pair<iterator, bool>可以看到返回的 pair 类型, first 是map的迭代器, 第二个则是 bool 类型, 代表本插入是否成功.
map<string, string> dict;
// 1. 直接创建一个对应类型的 pair
pair<string, string> kv1("树", "tree");
pari<string, string> kev2("栈", "stack");
dict.insert(kv1);
dict.insert(kv2);
// 2. 使用匿名对象插入
dict.insert(pair<string, string>("队列", "queue");
// 3. 使用 make_pair 插入, mak_pair 是一个函数模板
// 会用传入的两个值创建出一个 pair 类型返回
template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
return ( pair<T1,T2>(x,y) );
}
dict.insert(make_pair("链表", "list"));map 的删除, 使用 erase 函数
map<string, string> dict;
dict.insert(make_pair("链表", "list"));
dict.insert(make_pair("队列", "queue"));
dict.erase("链表"); // 通过 pair 中的 first 来查找, 并删除map 的查找, 使用 find 函数
会返回一个查找的数据的迭代器.
map<string, string> dict;
dict.insert(make_pair("链表", "list"));
dict.insert(make_pair("队列", "queue"));
std::map<string, string>::iterator = dict .find("链表");
cout << it->first << ": " << it->second;map 中用的最多的还是 operator[].
operator[] 有 insert 和 find 的功能.
operator[] 会先去查找 map 中是否存在这个 key,
如果存在则返回这个键值对中 value 的引用. 就是 pair 中的 second 的引用
如果不存在, 则会在 map 中先插入这个 key, value 调用 value 类型的默认构造创建一个默认值. 此时 key 就存在了, 然后和上面一样, 返回 value 的引用.
operator[] == (*((this->insert(make_pair(k,mapped_type()))).first)).second
int main ()
{
std::map<char,std::string> mymap;
mymap['a']="an element";
// 没有找到 'a' 这个键, 那么就会先插入 'a'.
// 然后返回 value 的引用, value 通过 = 被赋值为"an element"
mymap['b']="another element"; // 'b' 和 'a' 是一样的
mymap['c']=mymap['b']; // 将 'b' 的 value 赋值给 'c'
std::cout << "mymap['a'] is " << mymap['a'] << '\n';
std::cout << "mymap['b'] is " << mymap['b'] << '\n';
std::cout << "mymap['c'] is " << mymap['c'] << '\n';
std::cout << "mymap['d'] is " << mymap['d'] << '\n';
return 0;
}set使用
set 的插入, 调用成员函数 insert
和 map 的插入函数一样, 会返回一个 pair 类型数据
pair<iterator, bool>first 是 set 的迭代器, second 是 bool 类型, 表示本次插入是否成功
set<int> myset;
myset.insert(10);
myset.insert(20);set 的查找, find 函数
和 map 的 find 一样, 返回一个 set 的迭代器
set<int> myset;
myset.insert(10);
myset.insert(20);
std::set<int>::iterator it;
it = myset,find(10);
cout << *it << endl;set 的删除, erase 函数
set<int> myset;
myset.insert(10);
myset.insert(20);
myset.erase (10);multimap和multiset
在 map 和 set 中, 所有的元素都是唯一的, 不能重复.
但是在 STL 提供的 multimap 和 multiset 中,
是能存在相同的元素的.
但是在实际中用的不太多, 了解即可