【C++】set & map的使用

关联式容器

关联式容器也是用于存储数据的，其与序列式容器不同，内部存储的是键值对结构的数据，且在数据检索方面比序列式容器效率要更高。

键值对

键值对是用来表示具有一一对应关系的一种结构，这种结构一般只包含有两个成员变量：key 和 value。
key 代表键码，value 表示与 key 所对应的信息。
SGI-STL(stl_pair.h)中对pair(键值对)结构的定义如下：

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) {}
};
1
2
3
4
5
6
7
8
9
10

树形结构的关联式容器

STL中总共实现了两种不同结构的关联式容器：树型结构与哈希结构。
树型结构的关联式容器主要介绍四种：set，multiset，map，multimap
这四种容器的共同点是：在底层都是用红黑树实现的，都是默认按照小于的方式进行元素的比较。
而set和map具有排序+去重的作用。

set

向set中插入元素时，只需插入value即可，但在底层实际存储的是由构成的键值对。
set中的元素默认是按照小于来比较的，使用set的迭代器遍历set中的元素，可以得到一个有序序列。

set成员函数常用功能介绍

1. Constructor

2. Iterators

3. Capacity

4. Modifiers

5. Operations

map

key：键值对中key的类型。map中的key是唯一的，且不能修改。
T：键值对中value的类型。

map成员函数常用功能介绍

1. Constructor

2. Iterators

与set的迭代器功能类似。

3. Capacity

与set的容量操作功能类似。

4. Element access

mapped_type& operator[] (const key_type& k)
{
    return ( *( ( this->insert( make_pair( k,mapped_type() ) ) ).first ) ).second
}
1
2
3
4

5. Modifiers

6. Operations

multiset & multimap

multiset与set的区别是，multiset中的元素可以是重复的，而set中的元素是唯一的。
multimap与map的区别是：multimap中的key是可以重复的，而map中的key是唯一的。multimap没有重载operator[]操作。