关联式容器的特征: 所用元素都会根据元素的键值自动被排序.
set
STL 中的关联式容器低层数据结构为红黑树, 其功能都是调用低层数据结构中提供的相应接口.
set 元的元素不会像 map 那样同时拥有键 (key) 和值 (value).
set 元素的键就是值, 值就是键, 并不允许两个元素有相同的键.
multiset 允许相同键值存在.
因为 set 元素的键和值相等, 所以不允许对 set 元素的值进行修改.(数据结构会根据 key 对元素进行排序, 对 value 的更改会改变树中元素的排列顺序).
set 容器提供的迭代器为 const iterator;
set 类的声明:
- template <class _Key, class _Compare, class _Alloc>
- class set;
set 类含三个模板参数, 键类型_Key, 键比较方法_Compare, 分配器类型_Alloc; 平时经常用到的是第一个模板参数: 键类型_Key, 如:
set<int> iset={1,2,3,4,5};
另外两个模板参数在特殊的应用场景上会发挥作用._Compare 模板参数可以指定容器中元素的比较方法, 根据容器存放元素的大小, 可修改内存分配策略_Alloc. 这两个参数都可已通过设置 set 的构造函数参数来进行指定:
- explicit set(const _Compare& __comp,
- const allocator_type& __a = allocator_type())
- : _M_t(__comp, __a) {}
如果 set 未指定后两个模板参数, 则会调用默认版本:
- template <class _Key, class _Compare __STL_DEPENDENT_DEFAULT_TMPL(Less<_Key>),
- class _Alloc = __STL_DEFAULT_ALLOCATOR(_Key)>
- class set;
- map
map 的每个元素都是一个 pair<_key,_value>, 同时拥有键值对.
map 不允许两个元素的键相同.
map 可以通过迭代器修改元素的值, 但不能修改键 (会改变元素排列).map iterator 是一种介于 const iterator 和 mutable iterator 之间的迭代器.
- template <class _Key, class _Tp, class _Compare, class _Alloc>
- class map ;
map 类有四个类模板参数, 分别是: 键类型_Key, 值类型_Tp, 键比较方法_Compare, 分配器类型_Alloc; 平时经常用到的是前两个模板参数: 键类型_Key 和值类型_Tp, 如:
- #include
- #include
- using namespace std;
- int main(){
- map<int,string> ismap={{1,"Hello"},{2,"World"}};
- cout<<ismap[1]<<endl; //Hello
- cout<<ismap[2]<<endl; //World
- return 0;
- }
若不指定后两个参数, 则会使用默认模板参数:
- template <class _Key, class _Tp,
- class _Compare __STL_DEPENDENT_DEFAULT_TMPL(Less<_Key>),
- class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp)>
- class map;
map 的按照键映射值是通过 [] 运算符来进行的:
- _Tp& operator[](const key_type& __k) {
- iterator __i = lower_bound(__k);
- // __i->first is greater than or equivalent to __k.
- // insert 那句, 根据键值和实值取出一个元素, 由于实值未知, 所以产生一个与实值
- // 类型相同的暂时对象替代 ->value_type(__k,_Tp()), 然后将这个元素插入到 map 里面
- // 此时,__i 指向插入之后的新位置的迭代器, 然后在返回实值.
- if (__i == end() || key_comp()(__k, (*__i).first))
- __i = insert(__i, value_type(__k, _Tp()));
- return (*__i).second;
- }
该函数首先对键__k 进行搜索, 若没有找到, 则在搜索结束位置插入新的节点. 函数返回的是键所对应值的引用, 因此, 可以对其进行赋值.
multiset 和 multimap
multiset 和 multimap 的用法和 set,map 的用法相同, 不过它们允许重复的键. 对应到源代码上就是, multi 版本的插入操作调用红黑树的 insert_equal 接口, 而普通版本则调用 insert_unique 接口. 以 multiset 为例:
set 版本
- pair<iterator,bool> insert(const value_type& __x) {
- pair<typename _Rep_type::iterator, bool> __p = _M_t.insert_unique(__x);
- return pair<iterator, bool>(__p.first, __p.second);
- }
multiset 版本
- iterator insert(const value_type& __x) {
- return _M_t.insert_equal(__x);
- }
小结
map 和 set 是常用的关系型容器, 两者内部都使用红黑树作为低层数据结构. 类提供的接口都调用红黑树提供的相应接口. 是对红黑树类的封装 (适配).
set 和 map 中的元素都是自动排序的.
set 的元素是键 (等于值).map 的元素是键值对 (key-value pair), 可以提供键到值的映射功能.
set 中的值 (键) 不能被修改, map 中元素的值可以被修改, 而键不能被修改.
来源: http://www.bubuko.com/infodetail-3302798.html