STL六大组件关系

Containe通过Allocator取得数据存储空间，Algorithm通过Iterator存取Container，Functor内容可以协助Algorithm完成不同的策略变化，Adaptor可以修饰或者套接Functor。

关联容器特性

1. 关联容器定义

顺序容器支持高效的关键字查找和访问，map中的元素是一些关键字-值（key-value）对：关键字其索引作用，值则表示与缩影相关联的数据。set中每个元素只包含一个关键字：set支持高效的关键字查询操作。——检查一个关键字是否在set中。（例如在文本处理中可以保存想要忽略的单词，字典则是mapde 经典应用）。

• 例子1：单词计算程序

  string strs[] = { "苹果", "香蕉", "草莓", "苹果", "香蕉", "香蕉", "香蕉", "苹果", "香蕉", "草莓" };map<string, int> countmap;//pair<iterator,bool> insert (const value_type& val);//此类型的insert返回值是一个pair,第一个元素first是一个迭代器，指向新插入元素的map，第二个元素second是一个bool值，插入成功返回true,否则返回falsefor (const auto& e : strs){std::pair<std::map<std::string, int>::iterator, bool> ret = countmap.insert(make_pair(e, 1));if (ret.second == false){ret.first->second++;}}map<string, int>::iterator cit = countmap.begin();while (cit != countmap.end()){cout << cit->first << ":" << cit->second << endl;cit++;}//方式2string strs[] = { "苹果", "香蕉", "草莓", "苹果", "香蕉", "香蕉", "香蕉", "苹果", "香蕉", "草莓" };map<string, int> countmap;//利用find统计每一个元素出现的次数for (const auto& e : strs){map<string, int>::iterator it = countmap.find(e);//countmap.end()是map中最后一个元素的下一个if (it != countmap.end()){//如果找到，value++；it->second++;}else{//若是没有再去插入，又要遍历一遍，有些许冗余countmap.insert(make_pair(e, 1));}}//遍历每一个元素map<string, int>::iterator cit = countmap.begin();while (cit != countmap.end()){cout << cit->first << ":" << cit->second << endl;cit++;}方式3string strs[] = { "苹果", "香蕉", "草莓", "苹果", "香蕉", "香蕉", "香蕉", "苹果", "香蕉", "草莓" };map<string, int> countmap;for (const auto& e : strs){//先调用operator[];再对返回值value进行++。countmap[e]++;}for (auto& e : countmap){cout << e.first << ":" << e.second << endl;}
  

• 例子2经典的单词计数程序—利用关联数组map和互斥集合set

• 我们详细讲述了map这个关联数组， 并介绍了经典的单词计数程序，看看这个场景： 单词计数的时候， 不考虑一系列的单词， 如不考虑"abc", "de"等等。 set是个互斥集合， 所以在此可以排上用场了， 且看：

#pragma warning(disable : 4786)
#include <map>
#include <set>
#include <string>
#include <fstream>
#include <iostream>
using namespace std;int main()
{ifstream cin("test.txt"); // 这个cin会屏蔽掉std::cinif(!cin){return 1;}map<string, int> m;string word;set<string> s; // 互斥集合s.insert("abc");s.insert("de");while(cin >> word){if(s.find(word) == s.end()) // 在s中找不到word, 也就是说，word不在s中{m[word]++; // 非常非常经典啊， 我被map折服得五体头地}}map<string, int>::iterator it;for(it = m.begin(); it != m.end(); it++){cout << (*it).first << " " << (*it).second << endl;}return 0;
}

markdown 图片旋转格式

<img src="C:\Users\Administrator\Desktop\pic\set-multiset.jpg" style= "transform: rotate(90deg); zoom: 200%;" />

set-multiset

map-multimap

pair 类型

• 1. Write a program to read a sequence of strings and ints , storing each into a pair. Store the pairs in a vector. P381，11.12

• make_pair 或者pair的4种初始化方式。

   Exercise 11.12:#include <vector>
  #include <utility>
  #include <string>
  #include <iostream>int main()
  {std::vector<std::pair<std::string, int>> vec;std::string str;int i;while (std::cin >> str >> i)vec.push_back(std::pair<std::string, int>(str, i));//vec.push_back(std::make_pair(str, i));//vec.push_back({ str, i });//vec.emplace_back(str, i);                         //!! easiest way.for (const auto &p : vec)std::cout << p.first << ":" << p.second << std::endl;
  }
  

• 2. Define a map for which the key is the family’s last name （姓）and the value is a vector of the children’s names. Write code to add new families and to add new children to an existing family.

Exercise 11.7:#include <map>
#include <algorithm>using std::string; using std::vector; using std::map;
using std::cin; using std::cout;
using Families = map<string, vector<string>>;auto make_families()
{Families families;for (string ln; cout << "Last name:\n", cin >> ln && ln != "@q";)for (string cn; cout << "|-Children's names:\n", cin >> cn && cn != "@q";)families[ln].push_back(cn);return families;
}auto print(Families const& families)
{for (auto const& family : families){cout << family.first << ":\n";for (auto const& child : family.second)cout << child << " ";cout << "\n";}
}int main()
{print(make_families());return 0;
}

• 3. Could we define a map from vector::iterator to int? What about from list::iterator to int? In each case, if not, why not?

// Exercise 11.10://  vector<int>::iterator to int is ok , because < is defined
//  list<int>::iterator to int is not ok, as no < is defined.

• 4. Extend the map of children to their family name that you wrote for the exercises in § 11.2.1 (p. 424) by having the vector store a pair that holds a child’s name and birthday.

// Exercise 11.14:
// Exercise 11.7:#include <iostream>#include <map>#include <string>#include <vector>using std::ostream;using std::cout;using std::cin;using std::endl;using std::string;
using std::make_pair;using std::pair;using std::vector;using std::map;class Families
{
public:using Child     = pair<string, string>;using Children  = vector<Child>;using Data      = map<string, Children>;auto add(string const& last_name, string const& first_name, string birthday){auto child = make_pair(first_name, birthday);_data[last_name].push_back(child);}auto print() const{for (auto const& pair : _data){cout << pair.first << ":\n" ;for (auto const& child : pair.second)cout << child.first << " " << child.second << endl;cout << endl;}}private:Data _data;
};int main()
{Families families;auto msg = "Please enter last name, first name and birthday:\n";for (string l, f, b; cout << msg, cin >> l >> f >> b; families.add(l, f, b));families.print();return 0;
}

关联容器操作

1、关联容器和顺序容器的本质区别：关联容器是通过键存取和读取元素、顺序容器通过元素在容器中的位置顺序存储和访问元素。
因此，关联容器不提供front、push_front、pop_front、back、push_back以及pop_back，此外对于关联容器不能通过容器大小来定义，因为这样的话将无法知道键所对应的值什么。

2、两个主要的关联容器类型是map和set。map的元素以键-值对的形式组织：键用作元素在map的索引，而值则表示所存储和读取的数据。
set仅包含一个键，并有效地支持关于某个键是否存在的查询。
set和map类型的对象不允许为同一个键添加第二个元素。
如果一个键必须对应多个实例，则需使用multimap或mutiset类型，这两种类型允许多个元素拥有相同的键。

1.map

1-1. map的定义

1、定义一个map，必须指定关键字和值的类型；
2、从map中提取一个元素时，会得到一个pair类型的对象；
3、map中使用的pair用first成员保存关键字，用second成员保存对应的值；

1-2. map的插入

	map<int,int> mymap;//下标直接创建mymap[5] = 9;mymap[8] = 3;//或者以下4种方式创建mymap.insert(make_pair(2,4));mymap.insert(pair<int,int>(11,7));mymap.insert(map<int,int>::value_type(4,20) );mymap.insert({5,6});//无法覆盖前面的值，如果已经在map中，则什么都不做。  还是5，9//遍历auto iter_map = mymap.begin();cout << "mymap_size:" << mymap.size() << endl;while( iter_map != mymap.end() ){cout << iter_map->first << ' ' << iter_map->second << endl;;iter_map++;}

1-3. map的遍历

	auto iter_map = mymap.begin();cout << "mymap_size:" << mymap.size() << endl;while( iter_map != mymap.end() ){cout << iter_map->first << ' ' << iter_map->second << endl;;iter_map++;}

1-4. map的查找

		if (map.find(3) != map.end()) {cout << "find key=" << map.find(3)->first << ", value=" << map.find(3)->second << endl;}if (map.count(5) > 0) {cout << "find 5: " << map.count(5) << endl;}

1-5. map与unordered_map的区别及优缺点

如果把1-2节中的map替换成unordered_map，则后insert的在前面打印出来。
在这里插入图片描述

区别：

map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。

unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。

优缺点以及适用处

map：
优点：
有序性**，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现**，因此效率非常的高
缺点：
空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间

适用处：对于那些有顺序要求的问题，用map会更高效一些

unordered_map：
优点： 因为内部实现了哈希表，因此其查找速度非常的快
缺点： 哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

总结：
内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder_map占用的内存要高。
但是unordered_map执行效率要比map高很多
对于unordered_map或unordered_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的

2.set

2-1.set的定义

set就是关键字的简单集合。当想知道一个值是否存在时，set是最有用的。
定义一个map时，必须即指明关键字类型又指明值类型；
而定义一个set时，只需指明关键字类型。

set中的key_type和value_type是一样的；
set中保存的值就是关键字

2-2.set的插入

set的插入insert两种方法：
1.接受一对迭代器
2.初始化列表

vector<int> ivec = { 2,4,6,8,2,4,6,8};
set<int> set2；
//1.接受一对迭代器
set2.insert(ivec.cbegin(),ivec.cend());
//2.初始化列表
set2.insert({1,3,5,7,1,3,5,7});

2-3.set的遍历

**set<int> set_v;
set_v.insert(  {1,7,8,5,6} );
set_v.insert(5);
set<int>::iterator s_iter = set_v.begin();
while( s_iter != set_v.end() )
{cout << *s_iter << endl;s_iter++;
}
**

2-4. unordered_set

unordered_set 是基于hash表的，因此并不是顺序存储。

迭代器

1. 插入器是一种适配器.

• 插入迭代器

  back_inserter 创建一个push_back的迭代器。

  fornt_inserter 创建一个push_front的迭代器

  inserter创建一个使用insert的迭代器。

  demo1

  list<int> lst = { 1,2,3,4 };
  list<int> lst2, lst3;
  copy(lst.begin(), lst.end(), front_inserter(lst2));
  copy(lst.begin(), lst.end(), inserter(lst3,lst3.begin()));
  

2. iostream 迭代器

istream_iterator<T> in(is); in从输入流is读取类型为T的值
istream_iterator<T> end;	读取类型为T的值istream_iterator迭代器，表示尾后位置in1 == in2 in1与in2必须读取相同的类型，如果他们都是尾后迭代器，或绑定到相同的输入，则两者相同
in1 != in2
*in 	返回从流中读取的值
in->mem 与 (*it).mem 的含义相同
++in ， in++ 前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值

istream_iterator调用 accumulate：

istream_iterator<int> in(cin), eof;
cout<< accumulate(in, eof, 0)<<endl;

3. ostream_iterator操作

• 方式1

ostream_iterator<int> out_iter(cout, " ");
for(auto e : vec)*out_iter++ = e;
cout<<endl;

• 方式2

当对out_iter赋值时，可以忽略解引用和递增运算。即循环可以写成如下的样子

for (auto x : vec)out_iter = e;
cout<<endl;

推荐第一种方式，推荐方式1，原因是这种写法 使得流迭代器和其他类型的迭代器保持一致。

反向迭代器

反向迭代器：++ 表示向前移动，–表示向后移动

	vector<int> vec = { 1,2,3,4,5,6 };for (auto riter = vec.crbegin(); riter != vec.crend(); ++riter) {cout << *riter << endl;} // 6 5 4 3 2 1

sort(vec.rbegin(), vec.rend());// 1,2,3,4,5,6 

泛型算法结构p365