include // std::complex
#include // std::cout/endl
#include // std::unordered_map
#include // std::unordered_set
#include “output_container.h”

using namespace std;

//下面这样特化hash函数更常规
//请注意我们在 std 名空间中添加了特化，这是少数用户可以向 std 名空间添加内容的情//况之一。正常情况下，向 std 名空间添加声明或定义是禁止的，属于未定义行为。

函数对象及其特化
先讲两个重要的函数对象，less和hash
先看less，小于关系在标准库中less通常这样定义

template <class T>
struct less: binary_function<T, T, bool> {//binary_function函数模板 参数为T,T类型 返回值为布尔类型
  bool operator()(const T& x,
                  const T& y) const
  {
    return x < y;
  }
};

less()(1,2);//先less()构造less临时对象，再调用opreator()双参数重载版
less 是一个函数对象，并且是个二元函数，执行对任意类型的值的比较，返回布尔类型。作为函数对象，它定义了函数调用运算符（operator()），并且缺省(defualt 默认)行为是对指定类型的对象进行 < 的比较操作。 —- 还有greater

若干容器和排序算法sort会用这个默认less

计算哈希值的函数对象hash，目的是把某个类型(传入的实例化类型)的值转换成一个无符号整数哈希值(类型为size_t)，编译器没有像less一样给一个默认缺省的hash实现

系统提供了对于系统常用的类型hash特化 如

namespace std{
    //声明一个模板 hash，其有一个类型参数。编译器知道了 
    //hash 是一个类模板之后，下面才能进行特化。
    template <class T>
    struct hash;//声明函数hash类
    template <>//模板T特化
    struct hash<int>//int特化版本
      : public unary_function<int, size_t> {
      size_t operator()(int v) const
        noexcept
      {
        return static_cast<size_t>(v);
      }
    }
};

更复杂的类型，如指针或者 string 的特化，都会更复杂。要点是，对于每个类，类的作者都可以提供 hash 的特化，使得对于不同的对象，hash函数调用运算符都能得到尽可能均匀分布的不同数值

下面再举一个系统对hash特化的例子


#include <algorithm>   // std::sort
#include <functional>  // std::less/greater/hash
#include <iostream>    // std::cout/endl
#include <string>      // std::string
#include <vector>      // std::vector
#include "output_container.h"
using namespace std;
int main()
{
  // 初始数组
  vector<int> v{13, 6, 4, 11, 29};
  cout << v << endl;
  // 从小到大排序
  sort(v.begin(), v.end());
  cout << v << endl;
  // 从大到小排序
  sort(v.begin(), v.end(),
       greater<int>());
  cout << v << endl;
  cout << hex;
  auto hp = hash<int*>();//特化对int*类型 的hash计算函数对象
  cout << "hash(nullptr)  = "
       << hp(nullptr) << endl;
  cout << "hash(v.data()) = "
       << hp(v.data()) << endl;//v.data()返回的是vector裸指针
  cout << "v.data()       = "
       << static_cast<void*>(v.data())
       << endl;
  auto hs = hash<string>();//特化对string类型 的hash计算函数对象
  cout << "hash(\"hello\")  = "
       << hs(string("hello")) << endl;
  cout << "hash(\"hellp\")  = "
       << hs(string("hellp")) << endl;
}

在 MSVC 下的某次运行结果如下所示：
{ 13, 6, 4, 11, 29 }
{ 4, 6, 11, 13, 29 }
{ 29, 13, 11, 6, 4 }
hash(nullptr) = a8c7f832281a39c5
hash(v.data()) = 7a0bdfd7df0923d2
v.data() = 000001EFFB10EAE0
hash(“hello”) = a430d84680aabd0b
hash(“hellp”) = a430e54680aad322

在这个实现里，空指针的哈希值是一个非零的数值，指针的哈希值也和指针的数值不一样。要注意不同的实现处理的方式会不一样。GCC、Clang 和 MSVC 对常见类型的哈希方式都各有不同。

函数对象hash,less的类型int,int,string确定了容器的行为。
比如vector v{13, 6, 4, 11, 29}; sort(v.begin(), v.end(),greater());第三个参数的类型确定了其排序行为。

priority_queue
priority_queue优先队列(大小堆) 也是一个容器适配器(底层要用什么容器实现可以由模板参数指定默认vector 堆本来就是完全二叉树，可以用数组实现)。上一讲没有和其他容器适配器一起讲的原因就在于它用到了比较函数对象（默认是 less）。
它和 stack 相似，支持 push、pop、top 等有限的操作，但容器内的顺序既不是后进先出，也不是先进先出，而是（部分）排序的结果。
在使用缺省的 less 作为其 Compare 模板参数时(默认大顶堆)，最大的数值会出现在容器的“顶部”。如果需要最小的数值出现在容器顶部，则可以传递 greater 作为其 Compare 模板参数。其增push,删pop平均为O(logn)
priority_queue< pair, vector>, greater>> q;
容器元素类型底层由什么容器实现比较的特化函数对象

*关联容器(有序)
关联容器有 set（集合）、map（映射）、multiset（多重集）和 multimap（多重映射）。跳出 C++ 的语境，map（映射）的更常见的名字是关联数组和字典，而在 JSON 里直接被称为对象（object）。在 C++ 外这些容器常常是无序的；在 C++ 里关联容器则被认为是有序的。

set<int> s{1, 1, 1, 2, 3, 4};
//s  -- >  { 1, 2, 3, 4 }
multiset<int, greater<int>> ms{1, 1, 1, 2, 3, 4};
// ms -- > { 4, 3, 2, 1, 1, 1 }
map<string, int> mp{ {"one", 1},{"two", 2},{"three", 3},{"four", 4} };
//mp  { {"four", 4} , {"one",1} , {"three",3} , {"two",2} }

mp中的排序默认按键的类型(这个例子是字符串类型),缺省less排序
less默认按string中字符ascii码排列，字符串的从前到后字符ascii码越小则认为越小，一样等则看下个字符

mp.insert({"four", 3}); //这种直接用{}插入键值对的写法在c++17里才正确
//mp  { {"four", 4} , {"one",1} , {"three",3} , {"two",2} }

自带对键去重—-检测到插入的键值对的键在 map中出现过则不会再插入

mp["five"] = 5;
//mp  {{"five", 5}, {"four", 4} , {"one",1} , {"three",3} , {"two",2} }
可通过下标索引添加元素
multimap<string, int> mmp{{"one", 1},{"two", 2},{"three", 3},{"four", 4}};
//mmp  { {"four", 4} , {"one",1} , {"three",3} , {"two",2} }
mmp.insert({"four", -4});
//mmp  { {"four", 4},{"four", -4} , {"one",1} , {"three",3} , {"two",2} }

multi允许键的重复，将键值对按先来后到顺序插入

关联容器是一种有序的容器。名字带“multi”的允许键重复，不带的不允许键重复。set 和 multiset 只能用来存放键，而 map 和 multimap 则存放一个个键值对。

与前面的序列容器相比，关联容器没有前后的概念(-无front,back 以及顺序的概念，无next,prev,数字索引[])
但是提供insert,emplace等成员函数。关联容器都有find、lower_bound、upper_bound等查找函数(O(logn) 没有uordered容器O(1)快),这些查找函数返回的是迭代器
find(k) 可以找到任何一个键值等于k的元素并返回其迭代器(没找到返回end) !(xk)
lower_bound(k) 找到第一个键值不小于k的元素 !(x<k)
upper_bound(k) 找到第一个键值大于k的元素 (x>k)

//mp  { {"four", 4} , {"one",1} , {"three",3} , {"two",2} }
mp.find("four")->second;  // 4
//mp.find("four")返回的是迭代器it, 对it取内容 *it是个键值对，
//取键值对的second即值内容为4
(--mp.upper_bound("four"))->second;  //4
//mp.upper_bound("four")返回的是迭代器it, 对it取内容 *it是个键值对{"one",1}，
//因为查找的是第一个键大于four的键值对，
//--mp.upper_bound("four")为{"one",1}的上个键值对为{"four", 4} 输出其值内容为4
//mmp  { {"four", 4},{"four", -4} , {"one",1} , {"three",3} , {"two",2} }
(--mmp.upper_bound("four"))->second;  //-4
//mmp.upper_bound("four")返回的是迭代器it, 对it取内容 *it是个键值对{"one",1}，
//因为查找的是第一个键大于four的键值对，
//--mp.upper_bound("four")为{"four", -4}的上个键值对为{"four", -4} 
//输出其值内容为-4

使用equal_range 精确查找满足某个键的区间，结果上下界[lower,upper)半开半闭

#include <tuple>
multimap<string, int>::iterator lower, upper;
std::tie(lower, upper) = mmp.equal_range("four");
//mmp  { {"four", 4},{"four", -4} , {"one",1} , {"three",3} , {"two",2} }
//返回lower ==  {"four", 4}  upper == {"one",1}

对于关联容器而言，在创建的时候模板内没有提供实例化的比较函数类(multiset**>)，则缺省(默认)用less来排序(xxx为键的类别)。
如果键类对比较符<做了重载则ok不需要做额外工作(不需要指定less，而一样就用默认less 默认less会自动推动推导模板参数，并使用我们重载的<进行比较)，我们没有重载xxx类的<，
1 则需要对键类型xxx进行less的特化，

namespace std // or __gnu_cxx
{
    template <>//模板T特化
    struct less<X>
    {
    bool operator()(const X&x1,const X& x2)const
    {
        return  x1.i < x2.i;
    }
    };
}
std::sort(v.begin(), v.end(), less<X>() );
set<X,less<X>> s;

2 或者提供一个其他的函数对象类型

比如class compare_point_x
{
public:
    bool operator()(const point& pt1, const point& pt2)
    {
        return pt1.x < pt2.x;
    }
};
set<point,compare_point_x> s;//直接将自己定义的比较函数类传入
std::sort(points.begin(), points.end(), compare_point_x() );//将自定义的比较函数对象传入

3 也可以使用lamba正则表达式

std::sort(points.begin(), points.end(), [](point &pt1, point &pt2) ->bool{return pt1.x < pt2.x;});//使用正则表达式 直接返回对象

或者

auto point_comp_x =  [](point &pt1, point &pt2) ->bool {return pt1.x < pt2.x;}
set<point,decltype(point_comp_x)> s(point_comp_x);
std::sort(points.begin(), points.end(),point_comp_x);

hash对象函数同理也有上面三种实现方法

4 对于自定义类型，推荐尽量使用标准的less实现，通过重载<(及其他比较运算符) 实现对该类对象进行排序。存储在关联容器中的键一般应满足严格弱序关系(strict weak ordering)
所有顺序容器的默认比较是,less—我们去重载小于<实现从小到大排列
即
对于任何该类型的对象x: !(x < x)永远为true 非自反
对于任何该类型的对象x,y: 如果(x < y)，则 !( y < x )永远为true 非对称
对于任何该类型的对象x,y,z: 如果(x < y)并且(y对于任何该类型的对象x,y,z: 如果x和y不可比(!(x

无序关联容器
从c++11开始每一个关联容器(有序)都有一个对于的无序关联容器
unordered_set
unordered_map
unordered_multiset
unordered_multimap
这些容器和关联容器非常相似，主要的区别就在于它们是“无序”的。这些容器不要求提供一个排序的函数对象，而要求一个可以计算哈希值的函数对象。你当然可以在声明容器对象时手动提供这样一个函数对象类型，但更常见的情况是，我们使用标准的 hash 函数对象及其特化。
先讲一个细节，用迭代器遍历无序容器得到的顺序和 unordered内部存在自动rehash过程。一旦rehash(插入新键值对)，节点的遍历顺序就会变化。无序容器的插入顺序!=迭代器遍历其的遍历顺序

include // std::complex
#include // std::cout/endl
#include // std::unordered_map
#include // std::unordered_set
#include “output_container.h”

using namespace std;

//下面这样特化hash函数更常规
//请注意我们在 std 名空间中添加了特化，这是少数用户可以向 std 名空间添加内容的情//况之一。正常情况下，向 std 名空间添加声明或定义是禁止的，属于未定义行为。

namespace std {
template <typename T>
struct hash<complex<T>> {
  size_t
  operator()(const complex<T>& v) const
    noexcept
  {
    hash<T> h; // 在complex的哈希计算中 又使用了实例化complex的类型T(一般是标准类型)的哈希计算
    return h(v.real()) + h(v.imag());
  }
};
}  // namespace std
int main()
{
  unordered_set<int> s{
    1, 1, 2, 3, 5, 8, 13, 21
  };
  cout << s << endl;
  unordered_map<complex<double>, double> umc{{{1.0, 1.0}, 1.4142}, {{3.0, 4.0}, 5.0}};
  //{1.0, 1.0} 可以用来构造一个复数（1 + i），{{1.0, 1.0}, 1.4142} 是 unordered_map 里的一项。
  cout << umc << endl;
}

请注意我们在 std 名空间中添加了特化，这是少数用户可以向 std 名空间添加内容的情况之一。正常情况下，向 std 名空间添加声明或定义是禁止的，属于未定义行为。

无序关联容器的优点在于因为其实现使用哈希表其增insert,删erease,查find平均可以达到O(1)。有序关联容器用红黑树实现，其增insert,删erease,查find平均为O(logn)
但是在哈希函数选择不当的情况下，无序关联插入、删除、查找性能可能成为最差情况的O(n)。

array
array是C数组的替代品，主要是为了保留数组以及C的向后兼容性
C数组本身和c++容器相差非常大
C数组没有 begin和end成员(虽然可以使用全局的begin和end函数)
C数组没有size成员函数 (需要用一些模板技巧来获得其长度)
C数组作为参数有退化行为，将数组传递给一个函数后，那个函数不再能获得C数组的长度和结束位置，所以在C风格编程中，传入一个数组常伴随传入这个数组的长度

在C年代，有时会定义这样一个宏来获得数组的长度
#define ARRAY_LEN(a) (sizeof(a)/sizeof((a)[0]))
如果在一个函数内部使用这个宏，结果肯定是错的
void test(int a[8])
{
cout << ARRAY_LEN(a) << endl;//警告 sizeof函数数组形参将会返回 size of ‘int *’ 而不是 sizeof ‘int [8]
}

//在C年代，有时会定义这样一个宏来获得数组的长度
#define ARRAY_LEN(a)  (sizeof(a)/sizeof((a)[0]))
//如果在一个函数内部使用这个宏，结果肯定是错的
void test(int a[8])
{
  cout << ARRAY_LEN(a) << endl;//警告 sizeof函数数组形参将会返回 size of ‘int *’ 而不是 sizeof ‘int [8]
}

c++17提供了一个size方法，可用于提供数组长度，在数组退化成指针(就是之前数组作为函数参数这种情况)的情况下会直接失败

#include <iostream>  // std::cout/endl
#include <iterator>  // std::size
void test(int arr[])
{
  // 不能编译 数组退化成指针 直接失败
  // std::cout << std::size(arr)
  //           << std::endl;
}
int main()
{
  int arr[] = {1, 2, 3, 4, 5};
  std::cout << "The array length is "
            << std::size(arr)//ok
            << std::endl;
  test(arr);
}

此外C数组没有良好的复制行为。无法用C数组作为map或unordered_map的键类型

#include <map>  // std::map
typedef char mykey_t[8];//mykey_t相当于 一维数组指针char[8]
//等同于 typedef char[8] mykey_t;
int main()
{
  std::map<mykey_t, int> mp;
  mykey_t mykey{"hello"};
  mp[mykey] = 5;
  // 轰，大段的编译错误
}

不用C数组，有三个可以考虑的替代容器
如果数组较大，应该考虑vector,vector有最大的灵活性和不错的性能
对于字符串数组，应该考虑string
如果数组大小固定(C的数组在c++里面本来就是大小固定的)并且较小的话，应该考虑array,
,array保留了C数组在栈上分配(其他所有容器都是堆上内存)的特点，同时提供了begin,end,size等通用成员函数
上面的代码用array改写
array可以作为map或unordered_map的键类型

#include <array>     // std::array
#include <iostream>  // std::cout/endl
#include <map>       // std::map
#include "output_container.h"
typedef std::array<char, 8> mykey_t;
int main()
{
  std::map<mykey_t, int> mp;
  mykey_t mykey{"hello"};
  mp[mykey] = 5;  // OK
  std::cout << mp << std::endl;
}

现代c

5 容器汇编2 需要函数对象的容器