关联式容器

序列式容器：vector，list，deque等。底层为线性序列的数据结构，其中存放元素本身。

关联式容器：存放的是 < key,value > 结构的键值对，根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)，作为其底层结果，容器中的元素是一个有序的序列。

键值对

用来表示索引（key，键）与值（value）一一对应的关系。

在STL中，对键值对进行了封装——pair

SGI-STL对键值对的定义

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
11
12
13
14
15

其中 first充当key，而second充当value。

我们一般创建键值对有两种方式

1. 使用构造函数：pair<T1,T2>来构造匿名对象

2. 函数模板：make_pair(x,y),模板可自动识别xy类型，返回pair的匿名对象

   template <class T1,class T2>
   pair<T1,T2> make_pair (T1 x, T2 y)
   {
       return ( pair<T1,T2>(x,y) );
   }
   1
   2
   3
   4
   5

set

模板参数列表：

1. T ：set 存放的元素类型，实际在底层存储 < value,value > 键值对
2. Compare ：仿函数，set存放元素的顺序。默认按照小于来比较（中序遍历输出为升序）
3. Alloc ：空间配置器。

翻译：

1. set的元素按照特定的顺序进行存放。
2. set的value也标识它自身（value就是key。类型为T），并且每个value必须是唯一的。set中的元素一次也不能修改（元素总是const），但是可以从容器中插入以及删除他们。
3. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
4. set在底层是用二叉搜索树(红黑树)实现的。

🚩注意：

set与map不同，map存放的是键值对 < key,value >,set中只放value，但在底层实际存放的是由 < value,value > 构成的键值对。

将数据放入set，它可以自动帮我们完成排序加去重的工作。

set的使用

1. set的构造

  1. set的默认构造函数，构造空的set
  2. 用 [ first , last ) 区间中的元素构造set
  3. set的拷贝构造
1
2
3

2. set的迭代器

• iterator begin(): 返回set中起始位置元素的迭代器
• iterator end(): 返回set中最后一个元素后面的迭代器
• const_iterator cbegin()const: 返回set中起始位置元素的const迭代器
• const_iterator cend()const: 返回set中最后一个元素后面的const迭代器
• reverse_iterator rbegin(): 返回set最后一个元素的反向迭代器。
• reverse_iterator rend(): 返回set第一个元素上一个位置的反向迭代器。
• const_reverse_iterator crbegin() const: 返回set最后一个元素的反向const迭代器。
• const_reverse_iterator crend() const: 返回set第一个元素上一个位置的反向const迭代器。

3. set的大小和容量

• bool empty ( ) const ：检测set是否为空，空返回true，否则返回true
• size_type size() const ：返回set中有效元素的个数

4. set的修改操作

• pair<iterator,bool> insert (const value_type& x)
  在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,如果插入失败，说明x在set中已经存在，返回<x在set中的位置，false>

• void erase ( iterator position )
  删除set中position位置上的元素。position必须是个有效的迭代器，如果position是通过find找到的，那么在删除前检查一下是否== set::end。如果position不是有效位置，删除会报错。

• size_type erase ( constkey_type& x)
  删除set中值为x的元素，返回删除的元素的个数。如果x不存在不会报错。

• void erase ( iterator first, iterator last )
  删除set中[first, last)区间中的元素

• void swap (set<Key, Compare, Allocator>&st )
  交换set中的元素

• void clear ( )
  将set中的元素清空

• size_type count ( constkey_type& x ) const
  返回set中值为x的元素的个数

• iterator find ( const key_type& x ) const
  返回set中值为x的元素的位置（迭代器），找不到返回set::end(最后一个元素的后面位置)，注意类本身提供find比算法中的find要高。

  在这里我们可以将它和算法中的find进行对比：

  #include <iostream>
  #include <algorithm>
  #include <set>
  using namespace std;
  int main()
  {
      srand((size_t)time(nullptr));
      set<int> s;
      for (size_t i = 0; i < 10000; ++i)
      {
          s.insert(rand());
      }
      cout << "个数：" << s.size() << endl;
      int begin1 = clock();
      for (auto e : s)
      {
          s.find(e);
      }
      int end1 = clock();
  
      int begin2 = clock();
      for (auto e : s)
      {
          find(s.begin(), s.end(), e);
      }
      int end2 = clock();
  
      cout << "set的find用时1：" << end1 - begin1 << "ms" << endl;
      cout << "algorithm的find用时2：" << end2 - begin2 << "ms" << endl;
  
      return 0;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32

multiset

类 multiset 允许插入重复值，其余和set的使用相同。可用来排序。

• 对于重复值的处理

注意：查找一个重复出现的值，meltiset将提供重复值里中序排列的第一个值（即第一个插入进multiset的值）

验证：

int main()
{
    multiset<int> ms;
	ms.insert(1);
	ms.insert(4);
	ms.insert(4);
	ms.insert(8);
	ms.insert(1);

	auto pos = ms.find(4);
	while (pos != ms.end())
	{
		cout << *pos << endl;
		pos++;
	}

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 删除重复值

使用erase成员函数中“查值”的重载函数将删除所有的重复值

int main()
{
    multiset<int> ms;
	ms.insert(1);
	ms.insert(4);
	ms.insert(4);
	ms.insert(8);
	ms.insert(1);

	ms.erase(4);
	for (auto e : ms)
	{
		cout << e << ' ';
	}cout << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

set 应用举例

int main()
{
	// 用数组array中的元素构造set
	int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
	set<int> s(array, array + sizeof(array) / sizeof(int));
	cout << s.size() << endl;

	// 正向打印set中的元素，从打印结果中可以看出：set可去重
	for (auto& e : s)
		cout << e << " ";
	cout << endl;

	// 使用迭代器逆向打印set中的元素
	for (auto it = s.rbegin(); it != s.rend(); ++it)
		cout << *it << " ";
	cout << endl;

	// set中值为3的元素出现了几次
	cout << s.count(3) << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

map

翻译：

1. map使用关联式容器，每个元素为键值和映射值的组合，元素之间符合特定的次序。
2. map中key值用来排序以及唯一标识元素，value中存储与键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，实际上为pair的别名：typedef pair value_type。
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。key值在map里是唯一的。
6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树)。

map的使用

1. map的构造

  1. map的默认构造函数，构造空的map
  2. 用 [ first , last ) 区间中的元素构造map
  3. map的拷贝构造
1
2
3

2. map 的迭代器和容量的函数与set类似但需要注意：

map的元素类型为pair，其键值为pair的first成员，实值为pair的second成员，所以得到迭代器后，需要使用箭头来获取键值和实值。

3. map查找与计数

• iterator find (const key_type& k);

• const_iterator find (const key_type& k) const;

  输入key值即可查找。没找到返回map::end。

• size_type count (const key_type& k) const

4. map的插入与删除

因为 map 中的元素键是唯一的，所以插入操作会检查每个插入的元素是否具有与容器中已有元素的键相等的键，如果是，则不插入该元素，并返回一个指向该现有元素的迭代器 。

• pair<iterator,bool> insert (const value_type& val)

  插入单个元素，类型为value_type(pair)。特别要注意这个返回值（类型pair）。

  如果原有map对象中已经存在相同的key值，意味插入失败，那么返回值的pair::first的值为map中现存key值对应元素的迭代器。pair::second的布尔值为false。

  如果插入的key值在原有map对象总不存在，那么可以顺利插入，那么返回值的pair::first的值为map中新晋key值对应元素的迭代器。pair::second的布尔值为true。

  🚩总结插入返回值：<旧key元素迭代器，false>，<新key元素迭代器，true>

• iterator insert (iterator position, const value_type& val)

  在提示的指定位置插入新值。如果map对象存在key值，那么返回已有key对应元素迭代器，否则可成功插入并返回插入元素迭代器。

  请注意，position只是一个提示，并不强制将新元素插入到地图容器中的该位置（map中的元素始终遵循特定的顺序，具体取决于它们的键）。

• void insert (InputIterator first, InputIterator last)

  插入一段迭代器范围

  使用insert

• void erase (iterator position)

  删除position迭代器指向的元素，前提是确保迭代器有效。常与find连用。

• size_type erase (const key_type& k)

  删除键值为k的元素。返回值为删除的元素数目。

• void erase (iterator first, iterator last)

  删除一端迭代器区间的元素。

5. operator[]的使用（重点）

• mapped_type& operator[] (const key_type& k)

  如果 k 匹配容器中元素的键，则该函数返回对其映射值的引用。

  如果 k 不匹配容器中任何元素的键，则该函数使用该键插入一个新元素并返回对其映射值的引用。 请注意，如果不匹配将使容器大小增加一，即使没有为元素分配映射值（映射值使用其默认构造函数构造）。

  int main()
  {
      std::map<char, int> mymap;
  
      mymap.insert(std::pair<char, int>('a', 100));
      mymap.insert(std::make_pair('z', 200));
  
  
      cout << mymap['a'] << endl;
      mymap['a'] = 300;
      cout << mymap['a'] << endl;
  
      cout << mymap.size() << endl;
  
      mymap['b'];
      cout<< mymap['b'] << endl;
      cout << mymap.size() << endl;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

- opearator[]的实现

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

- []的功能

插入，查找，修改。

我们通过一个例子来理解operator[]的使用：

计算各个水果的数量

int main()
{
    string fruit[] = { "apple","apple","banana","pineapple","peach","banana","peach" };
	map<string, int> Countfruit;
	for (auto&s : fruit)
	{
        	//第一次出现：插入+修改
        	//不是第一次出现：查找+修改
		Countfruit[s]++;
	}
	for (const auto& e : Countfruit)
	{
		cout << e.first << ':' << e.second << endl;
	}

	cout << "-----------------" << endl;

	map<string, int> Countfruit2;
	for (auto& s : fruit)
	{
		pair<map<string, int>::iterator, bool> kv = Countfruit2.insert(make_pair(s,1));
		if (kv.second == false)
		{
			(kv.first)->second++;
		}
	}
	for (const auto& e : Countfruit2)
	{
		cout << e.first << ':' << e.second << endl;
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

由此看出了 [] 的便利性

注意：如果只是查找，就使用find或count，而不要使用[]，不然对于本身就没有的值，会执行插入。

multimap

map类的可重复版本，即相同的key值的pair（不管value是否相同），可以进行重复插入。

multimap的查找元素，如果存在重复的key值元素，那么找到的是中序遍历序列的第一个key值对应元素，即第一个插入到对象中的该key值对应元素。

multimap 没有 operator[]，因为出现重复key值的元素会造成歧义，编译器不知道提供哪一个给你。

multimap的erase也是三个版本：

其中第二个erase，会将key对应的元素全部删除，返回删除的元素个数。

map的应用举例

• 题

公司就让每个员工报告了自己最爱吃的水果，并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数，按降序打印出来。

题目函数接口：

void GetFavoriteFruit(const vector<string>& fruit)
{ 

}
1
2
3
4

fruit样本如下：

vector<string> fruit = { "apple","apple","banana","pineapple","peach","pineapple","banana","pineapple","peach","apple","apple" };

解法一：

使用map对水果计数。然后将pair传入到vector容器中方便排序（vector为随机迭代器），为了省去深拷贝可以在vector存入map的迭代器提高拷贝效率并节省空间。
所以我们自己写个仿函数Comp区分迭代器的大小来sort。

struct Comp//仿函数类
{
	bool operator()(const map<string,int>::iterator & p1,const map<string, int>::iterator& p2)
	{
		return  p1->second > p2->second;
	}
};

void GetFavoriteFruit1(const vector<string>& fruit，size_t k)
{ 
    cout << "----------vector----------" << endl;
    map<string, int> Countfruit;
    for (auto& s : fruit)
    {
      Countfruit[s]++;
    }

	vector<map<string, int>::iterator> favorite1;

	auto it = Countfruit.begin();
	while (it != Countfruit.end())
	{
		favorite1.push_back(it);
		++it;
	}

	sort(favorite1.begin(), favorite1.end(), Comp());
	for (auto& e : favorite1)
	{
		cout<< e->first << ':' << e->second << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

解法二 ：

使用STL中的priority_queue,可以在输入的时候根据仿函数类，自动帮我们排序（建立大堆）。（注意，提供给优先级队列的仿函数与sort的仿函数是反的）

struct Comp//仿函数类
{
	bool operator()(const map<string,int>::iterator & p1,const map<string, int>::iterator& p2)
	{
		return  p1->second < p2->second;
	}
};
void GetFavoriteFruit2(const vector<string>& fruit，size_t k)
{
    cout << "-------priority_queue----------" << endl;
	priority_queue<map<string, int>::iterator, vector<map<string, int>::iterator>,Comp_for_priority> favorite2;
	auto it = Countfruit.begin();
	while (it != Countfruit.end())
	{
		favorite2.push(it);
		++it;
	}
	while (!favorite2.empty())
	{
		cout << favorite2.top()->first << ':' << favorite2.top()->second << endl;
		favorite2.pop();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解法三 ：

使用multimap

void GetFavoriteFruit3(const vector<string>& fruit，size_t k)
{
  cout << "----------multimap----------" << endl;
	multimap<int, string, greater<int>> favorite;
	for (auto& s : Countfruit)
	{
		favorite.insert(make_pair(s.second, s.first));
	}
	for (const auto& e : favorite)
	{
		cout << e.first << ':' << e.second << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

输出结果：

---

—— end ——

青山不改 绿水长流