容器Container 0x02

函数对象与特化

常用函数对象less和hash。

less 是一个函数对象，是二元函数，返回布尔类型。作为函数对象，它定义了函数调用运算operator()，并且缺省行为是对指定类型的对象进行 < 的比较操作。

在需要大小比较的场合，C++ 通常默认会使用 less，需要产生相反的顺序的话，则可以使用 greater。

template <class T>
struct less: binary_function<T, T, bool> 
{
  bool operator()(const T& x, const T& y) const
  {
    return x < y;
  }
};

hash是把一个某种类型的值转换成一个无符号整数哈希值size_t，它没有一个可用的默认实现。

对于常用的类型，系统提供了需要的特化：

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

using namespace std;

template <typename T>
void m_print(T& t)
{
    for(auto& i : t){
        cout<< i << " ";
    }
    cout<< endl;
}

int main()
{
    // test less and greater
    vector<int> v{1,3,7,4,5,2};
    sort(v.begin(),v.end());
    m_print(v); //1 2 3 4 5 7
    sort(v.begin(),v.end(), greater<int>());
    m_print(v); //7 5 4 3 2 1

    // test hash
    auto H1 = hash<int*>();                         
    cout << H1(nullptr) << endl;                    //0
    cout << H1(v.data()) << endl;                   //7018240
    cout << static_cast<void*>(v.data()) << endl;   //0x6b1700
    auto H2 = hash<string>();
    cout << H2("morisa") << endl;                   //392600774329545265
    cout << H2(string("morisa")) << endl;           //392600774329545265
    return 0;
}

GCC、Clang 和 MSVC 对常见类型的哈希方式都各有不同。

函数对象的类型确定了容器的行为。

priority_queue

在使用缺省的 less 作为其 Compare 模板参数时，最大的数值会出现在容器的顶部。

要最小的数值出现在容器顶部，则可以传递 greater 作为其 Compare 模板参数。

#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>
#include <queue>

using namespace std;

int main()
{ 
    using tmp_type = pair<int, int>;
    priority_queue<tmp_type, vector<tmp_type>, greater<tmp_type>> p_q;
    p_q.push({1,2});
    p_q.push({4,3});
    p_q.push({2,0});
    while(!p_q.empty()){
        cout<<p_q.top().first<< " " << p_q.top().second << endl;
        p_q.pop();
    }
    /*
    1 2
    2 0
    4 3
    */
    return 0;
}

关联容器

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

在 C++ 外这些容器常常是无序的；在 C++ 里关联容器则被认为是有序的。

关联容器是一种有序的容器。名字带multi的允许键重复，不带的不允许键重复。

set 和 multiset 只能用来存放键，而 map 和 multimap 则存放一个个键值对。

与序列容器相比，关联容器没有前、后的概念及相关的成员函数，提供 insert、emplace 等成员函数。

关联容器都有 find、lower_bound、upper_bound 等查找函数，结果是一个迭代器：

  • find(k) 可以找到任何一个等价于查找键 k 的元素（!(x < k || k < x)）
  • lower_bound(k) 找到第一个不小于查找键 k 的元素（!(x < k)）
  • upper_bound(k) 找到第一个大于查找键 k 的元素（k < x）

需要在 multimap 里精确查找满足某个键的区间，建议用 equal_range，一次取得上下界（半开半闭）。

int main()
{ 
    multimap<string, string> m_map{
        {"A", "a"},
        {"B", "b"},
        {"A", "c"},
        {"A", "d"} };
    m_print_pair(m_map);
    
    multimap<string, string>::iterator m_map_begin, m_map_end;
    
    tie(m_map_begin, m_map_end) = m_map.equal_range("A");
    
    cout<< m_map_begin->second << (++m_map_begin)->second 
    << m_map_end->second << (--m_map_end)->second <<endl;
    /*
    (Aa) (Ac) (Ad) (Bb)
    acbd
    */
    return 0;
}

在声明关联容器时没有提供比较类型的参数，缺省使用 less 来进行排序。

键的类型提供了比较算符 < 的重载，不需要做任何额外的工作。否则需要对键类型进行 less 的特化，或者提供一个其他的函数对象类型。

无序关联容器

从 C++11 开始，每一个关联容器都有一个对应的无序关联容器。

  • unordered_set
  • unordered_map
  • unordered_multiset
  • unordered_multimap

这些容器不要求提供一个排序的函数对象，而要求一个可以计算哈希值的函数对象。

namespace std {
    template<typename T> 
    struct hash<complex<T>> 
    { 
        size_t operator()(const complex<T>& v) const noexcept 
        { 
            hash h; 
            return h(v.real()) + h(v.imag()); 
        }
    };     
}

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

从实际的工程角度，无序关联容器的主要优点在于其性能。关联容器和 priority_queue 的插入和删除操作，以及关联容器的查找操作，其复杂度都是 O(log(n))，而无序关联容器的实现使用哈希表，可以达到平均 O(1)！但这取决于我们是否使用了一个好的哈希函数：在哈希函数选择不当的情况下，无序关联容器的插入、删除、查找性能可能成为最差情况的 O(n)。