再识关联容器

关联容器包括set，multiset，map，mulitmap，它们的实现通常是平衡二叉树。下面是记录关联容器的一些使用细节。

特有查找接口

根据所实现关联容器的数据结构平衡二叉树的特性。它们提供了查找接口。

名称	作用
find(elem)	返回“元素为elem“的一个元素，如果找不到就返回end()
lower_bound(elem)	返回elem的第一个可安插位置，也就是“元素值>=elem“的第一个元素位置
upper_bound(elem)	返回elem的最后一个可安插位置，也就是“元素值>elem“的第一个元素位置
equal_range(elem)	返回elem可安插第一个位置和最后一个位置，也就是“元素值==elem”的元素区间
insert(pos,elem)	安插一份elem副本，返回新元素位置（pos是个提示，指出安插操作的搜寻起点，如果提示恰当，可大大加快速度）

元素的相等判断

相等的判断是通过==，但是在关联容器中并不如此。关联容器是特点是对元素进行排序，其中容器set,map中的key是唯一，所以会有两种动作，判断大小，判断相等。比如接口insert就包括这两种操作，先判断容器中是否有该元素(相等)，再进行插入操作(排序)，下面是set的定义

template <class T,
        class Compare = less<T>,
        class Alllocator = allocator<T> >
class set;

Compare表示比较函数(排序准则)，默认的是std::less<T>，它是一个函数对象，重载函数调用操作符

bool operaotr()(const T &lhs,const T &rhs)const
{
    return lhs < rhs;
}

所以放入关联容器的自定义对象，如果使用默认的比较函数，则需要重载operaotr <操作符，或者使用自定义的函数对象来实现自定义的比较函数(排序准则)。比如从大到小排序的set

std::set<int,std::greater> greaterSet

set只有一个用于比较的类型参数，并没有==的类型参，所以不是通过==来判断相等的，是通过比较函数确定的，标准是：如果两个元素都不小于对方(或说op(x,y)和op(y,x)都为假),则两个元素相等,用代码表示元素相等，如下：

• 使用默认的比较函数的要求，重载了operator <

!(v1 < v2)&&!(v2 < v1) //为真

• 使用自定义比较函数(函数对象)的要求

!c.key_comp()(x,y)&&!c.key_comp()(y,x) //为真

STL中对关联容器的比较函数有更具体的要求

用于排序关联容器的比较函数必须在它们所比较的对象上定义一个严格的弱序化(strict weak ordering),其意义如下：

1. 必须是“反对称的“，对operator<而言，如果x<y为真，则y<x为假，对判断式op()而言，如果op(x,y)为真，则op(y,x)为假
2. 必须是“可传递的“，对operator<而言，如果x<y为真且y<z为真，则x<z为真，对判断式op()而言，如果op(x,y)为真且op(y,z)为真，则op(x,z)为真
3. 必须是“非自反的“，对operator<而言，x<x为假。对判断式op()而言，op(x,x)永远为假

试想如果还是使用==相等作为判断标准，那就需要再多出一个类型参数。所以用比较函数来定义相等也简化了实现

等价与相等

把关联容器的比较函数定义的相等称为等价，用以与===的相等作区别，泛型算法find和set的insert成员函数是很多必须判断两个值是否相等的函数代表。但它们以不同的方式完成。

• find对“相等” 的定义是相等，基于operator==
• set::insert对“相等”的定义是等价，通常基于operaotr<

下面通过一个实现了忽略大小写的set<string>，来看看两者的区别

#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <string>
class RuntimeStringCamp
{
  public:
    RuntimeStringCamp(){}
    bool operator()(const std::string& s1,const std::string& s2)
    {
      return std::lexicographical_compare(s1.begin(),s1.end(),s2.begin(),s2.end(),nocase_compare);
    }
  private:
    static bool nocase_compare(char c1,char c2)
    {
      return std::toupper(c1) < std::toupper(c2);
    }
};

typedef std::set<std::string,RuntimeStringCamp> StringSet;
int main()
{
  StringSet coll1;
  coll1.insert("Mo");
  coll1.insert("mo");

  for (auto it:coll1)
  {
    std::cout<<it<<" ";
  }

  std::cout<<std::endl;
  auto fit = coll1.find("mo");
  std::cout<<*fit<<std::endl;

  auto ffit = std::find(coll1.begin(),coll1.end(),"mo");
  if (ffit == coll1.end())
  {
    std::cout<<"can't find "<<std::endl;
  }
}

• 通过自定义的RuntimeStringCamp函数对象作为set的比较类型，来实现忽略大小写的set<string>
• 对coll1.insert("Mo")和coll1.insert("mo")，Mo和mo被判断为相同的值，所以coll1中只存在Mo
• std::find算法是基于==，显然Mo不等于mo,所以auto ffit = std::find(coll1.begin(),coll1.end(),"mo");是返回end

两个代码示例

自定义排序准则的代码示例

如上实现的忽略大小写的set<string>，示范了自定义的排序准则

重载<的代码示例

#include <set>
#include <iostream>
class SetTest
{
  public:
    SetTest()
    {}

    SetTest(int a,int b):_a(a),_b(b)
    {

    }


    void PrintValue()
    {
      std::cout<<"a "<<_a<<",b "<<_b<<std::endl;
    }

    friend bool operator<(const SetTest& v1,const SetTest& v2);
  private:
    int _a;
    int _b;
};

//重载操作符，一般都定义为类的友元
bool operator<(const SetTest& v1,const SetTest& v2)
{
  return v1._a < v2._a;
}