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 中,
是能存在相同的元素的.
但是在实际中用的不太多, 了解即可