Boost.MultiIndex 教程：键值提取

索引类型

Boost.MultiIndex 教程

容器创建

目录

• 简介
  • 读/写键值提取器
• 预定义的键值提取器
  • identity
  • member
  • const_mem_fun 和 mem_fun
    • 其他类型的成员函数的变体
  • global_fun
• 用户定义的键值提取器
• 复合键
  • 复合键和哈希索引
• C++17 简洁键值规范语法
• Boost.MultiIndex 键值提取器的高级特性

简介

STL 关联容器具有键的概念，尽管形式上还比较初期。因此，此类容器的键由嵌套类型 key_type 标识；对于 std::set 和 std::multiset，key_type 与 value_type 一致，即键是元素本身。std::map 和 std::multimap 管理 std::pair<const Key,T> 类型的元素，其中第一个成员是键。在任何一种情况下，从给定元素获取键的过程都是隐式固定的，用户无法自定义。

像 STL 关联容器执行的固定键值提取机制在 Boost.MultiIndex 的上下文中不能很好地扩展，在 Boost.MultiIndex 中，多个索引共享它们的 value_type 定义，但可能具有完全不同的查找语义。因此，Boost.MultiIndex 正式化了 键值提取器 的概念，以便在基于键的索引的定义中使其显式且可控。

直观地说，键值提取器是一个函数对象，它接受对元素的引用并返回其关联的键。形式概念也对过程的稳定性施加了一些合理的约束，即假定提取器在传递相同的元素时返回相同的键：这与键实际上是元素的某些“部分”并且不依赖于外部数据的非正式理解相符。

读/写键值提取器

键值提取器如果当传递一个非常量元素时返回对键的非常量引用，则称为读/写，否则称为只读。当使用基于键的索引的 modify_key 成员函数时，Boost.MultiIndex 要求键值提取器是读/写的。在所有其他情况下，只读提取器就足够了。关于 Boost.MultiIndex 键值提取器的高级特性 的章节展示了预定义的键值提取器是读/写的典型情况。

预定义的键值提取器

identity

identity 键值提取器返回整个基本对象作为关联的键

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>

multi_index_container<
  int,
  indexed_by<
    ordered_unique<
      identity<int> // the key is the entire element
    >
  >
> cont;

member

member 键值提取器返回对基本对象的指定数据字段的引用。例如，在我们熟悉的员工容器的以下版本中

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>

typedef multi_index_container<
  employee,
  indexed_by<
    ordered_unique<identity<employee> >,
    ordered_non_unique<member<employee,std::string,&employee::name> >,
    ordered_unique<member<employee,int,&employee::ssnumber> >
  >
> employee_set;

第二个和第三个索引分别在 employee::name 和 employee::ssnumber 上使用 member 提取器。member 实例化的规范很简单但有点人为

member<(base type),(key type),(pointer to member)>

似乎第一个和第二个参数是多余的，因为基本对象和关联数据字段的类型已经在指向成员的参数中隐式存在：不幸的是，使用当前的 C++ 机制无法提取此信息，这使得 member 的语法有点过于冗长。

const_mem_fun 和 mem_fun

有时，索引的键不是元素的具体数据成员，而是特定成员函数返回的值。这类似于某些关系数据库支持的计算索引的概念。Boost.MultiIndex 通过 const_mem_fun 支持这种键值提取。考虑以下容器，其中第三个索引的排序基于名称字段的长度

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/mem_fun.hpp>

struct employee
{
  int         id;
  std::string name;

  employee(int id,const std::string& name):id(id),name(name){}

  bool operator<(const employee& e)const{return id<e.id;}

  // returns the length of the name field
  std::size_t name_length()const{return name.size();}
};

typedef multi_index_container<
  employee,
  indexed_by<
    // sort by employee::operator<
    ordered_unique<identity<employee> >,
    
    // sort by less<string> on name
    ordered_non_unique<member<employee,std::string,&employee::name> >,
    
    // sort by less<int> on name_length()
    ordered_non_unique<
      const_mem_fun<employee,std::size_t,&employee::name_length>
    >
  >
> employee_set;

const_mem_fun 的使用语法类似于 member 的语法

const_mem_fun<(base type),(key type),(pointer to member function)>

引用的成员函数必须是 const，不接受任何参数并返回指定键类型的值。几乎总是您会想要使用 const 成员函数，因为 multi_index_container 中的元素被视为常量，就像 std::set 的元素一样。但是，为了与非常量成员函数一起使用，提供了 mem_fun 对等物，其适用性在关于 Boost.MultiIndex 键值提取器的高级特性 的段落中讨论。

示例 2 在示例部分中提供了一个完整的程序，展示了如何使用 const_mem_fun。

其他类型的成员函数的变体

考虑以下不编译的代码

struct employee
{
  ...
  std::size_t salary()const&; // note the &
};

typedef multi_index_container<
  employee,
  indexed_by<
    ...
    ordered_non_unique<
      // compiler error: can't convert &employee::salary to
      // std::size_t (employee::*)() const
      const_mem_fun<employee,std::size_t,&employee::salary>
    >
  >
> employee_set;

这里的问题是 &employee::salary 的类型，它是 ref-qualified，与 const_mem_fun 期望的类型不完全匹配。幸运的是，Boost.MultiIndex 提供了一个变体来适应

typedef multi_index_container<
  employee,
  indexed_by<
    ...
    ordered_non_unique<
      cref_mem_fun<employee,std::size_t,&employee::salary>
    >
  >
> employee_set;

这是 const_mem_fun 和 mem_fun 的所有可用变体的列表

global_fun

const_mem_fun 及其变体基于从中提取键的基本类型的给定成员函数，而 global_fun 接受一个全局函数（或静态成员函数），该函数接受基本类型作为其参数并返回键

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/global_fun.hpp>

struct rectangle
{
  int x0,y0;
  int x1,y1;
};

unsigned long area(const rectangle& r)
{
  return (unsigned long)(r.x1-r.x0)*(r.x1-r.x0)+
         (unsigned long)(r.y1-r.y0)*(r.y1-r.y0);
}

typedef multi_index_container<
  rectangle,
  indexed_by<
    // sort by increasing area
    ordered_non_unique<global_fun<const rectangle&,unsigned long,&area> >
  >
> rectangle_container;

global_fun 的规范遵循以下语法

global_fun<(argument type),(key type),(pointer to function)>

其中参数类型和键类型必须完全匹配所用函数的签名中的类型；例如，在上面的示例中，参数类型是 const rectangle&，没有省略 “const” 和 “&” 部分。因此，尽管大多数时候基本类型将通过常量引用接受，但 global_fun 也准备好接受通过值或非常量引用接受其参数的函数：后一种情况通常不能直接用于 multi_index_container 的规范中，因为它们的元素被视为常量，但是关于 Boost.MultiIndex 键值提取器的高级特性 的章节描述了基于具有非常量引用参数的此类函数的键值提取的有效用例。

示例 2 在示例部分中使用了 gobal_fun。

用户定义的键值提取器

尽管 Boost.MultiIndex 提供的 预定义键值提取器 旨在服务于大多数情况，但用户也可以在更特殊的情况下提供自己的键值提取器，只要这些提取器符合 键值提取器 概念即可。

// some record class
struct record
{
  boost::gregorian::date d;
  std::string            str;    
};

// extracts a record's year
struct record_year
{
  // result_type typedef required by Key Extractor concept
  typedef boost::gregorian::greg_year result_type; 
  
  result_type operator()(const record& r)const // operator() must be const
  {
    return r.d.year();
  }
};

// example of use of the previous key extractor
typedef multi_index_container<
  record,
  indexed_by<
    ordered_non_unique<record_year> // sorted by record's year
  >
> record_log;

示例 6 在示例部分中在一个复杂的场景中应用了一些用户定义的键值提取器，其中键是通过指针访问的。

复合键

在关系数据库中，复合键取决于给定表的两个或多个字段。Boost.MultiIndex 中类似的概念通过 composite_key 建模，如示例所示

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>

struct phonebook_entry
{
  std::string family_name;
  std::string given_name;
  std::string phone_number;

  phonebook_entry(
    std::string family_name,
    std::string given_name,
    std::string phone_number):
    family_name(family_name),given_name(given_name),phone_number(phone_number)
  {}
};

// define a multi_index_container with a composite key on
// (family_name,given_name)
typedef multi_index_container<
  phonebook_entry,
  indexed_by<
    // non-unique as some subscribers might have more than one number
    ordered_non_unique< 
      composite_key<
        phonebook_entry,
        member<phonebook_entry,std::string,&phonebook_entry::family_name>,
        member<phonebook_entry,std::string,&phonebook_entry::given_name>
      >
    >,
    ordered_unique< // unique as numbers belong to only one subscriber
      member<phonebook_entry,std::string,&phonebook_entry::phone_number>
    >
  >
> phonebook;

composite_key 接受同一值（此处为 phonebook_entry）上的两个或多个键值提取器。通过传递带有搜索值的元组来完成对复合键的查找操作

phonebook pb;
...
// search for Dorothea White's number
phonebook::iterator it=pb.find(std::make_tuple("White","Dorothea"));
std::string number=it->phone_number;

复合键按字典顺序排序，即，排序首先按第一个键执行，然后如果第一个键相等，则按第二个键执行，依此类推。此顺序允许仅指定第一个键的部分搜索

phonebook pb;
...
// look for all Whites
std::pair<phonebook::iterator,phonebook::iterator> p=
  pb.equal_range(std::make_tuple("White"));

作为一种符号约定，当仅指定第一个键时，可以直接传递参数，而无需将其包含在元组中

phonebook pb;
...
// look for all Whites
std::pair<phonebook::iterator,phonebook::iterator> p=pb.equal_range("White");

另一方面，不允许不指定第一个键的部分搜索。

默认情况下，相应的 std::less 谓词用于复合键的每个子键。可以使用 composite_key_compare 指定备用比较谓词

// phonebook with given names in reverse order

typedef multi_index_container<
  phonebook_entry,
  indexed_by<
    ordered_non_unique<
      composite_key<
        phonebook_entry,
        member<phonebook_entry,std::string,&phonebook_entry::family_name>,
        member<phonebook_entry,std::string,&phonebook_entry::given_name>
      >,
      composite_key_compare<
        std::less<std::string>,   // family names sorted as by default
        std::greater<std::string> // given names reversed
      >
    >,
    ordered_unique<
      member<phonebook_entry,std::string,&phonebook_entry::phone_number>
    >
  >
> phonebook;

有关 composite_key 的应用，请参见示例部分的 示例 7。

复合键和哈希索引

复合键也可以以直接的方式与哈希索引一起使用

struct street_entry
{
  // quadrant coordinates
  int x;
  int y;

  std::string name;

  street_entry(int x,int y,const std::string& name):x(x),y(y),name(name){}
};

typedef multi_index_container<
  street_entry,
  indexed_by<
    hashed_non_unique< // indexed by quadrant coordinates
      composite_key<
        street_entry,
        member<street_entry,int,&street_entry::x>,
        member<street_entry,int,&street_entry::y>
      >
    >,
    hashed_non_unique< // indexed by street name
      member<street_entry,std::string,&street_entry::name>
    >
  >
> street_locator;

street_locator sl;
...
void streets_in_quadrant(int x,int y)
{
  std::pair<street_locator::iterator,street_locator::iterator> p=
    sl.equal_range(std::make_tuple(x,y));

  while(p.first!=p.second){
    std::cout<<p.first->name<<std::endl;
    ++p.first;
  }
}

请注意，哈希是自动处理的：boost::hash 被专门化为哈希复合键作为其元素的 boost::hash 值的函数。如果我们需要为复合键的元素指定不同的哈希函数，我们可以通过使用 composite_key_hash 实用程序显式地执行此操作

struct tuned_int_hash
{
  int operator()(int x)const
  {
    // specially tuned hash for this application
  }
};

typedef multi_index_container<
  street_entry,
  indexed_by<
    hashed_non_unique< // indexed by quadrant coordinates
      composite_key<
        street_entry,
        member<street_entry,int,&street_entry::x>,
        member<street_entry,int,&street_entry::y>
      >,
      composite_key_hash<
        tuned_int_hash,
        tuned_int_hash
      >
    >,
    hashed_non_unique< // indexed by street name
      member<street_entry,std::string,&street_entry::name>
    >
  >
> street_locator;

此外，可以使用 composite_key_equal_to 调整复合键的相等性，尽管在大多数情况下，默认的相等谓词（依赖于元素类型的 std::equal_to 实例化）将是正确的选择。

与有序索引不同，我们无法执行仅指定复合键的第一个元素的部分搜索

// try to locate streets in quadrants with x==0
// compile-time error: hashed indices do not allow such operations
std::pair<street_locator::iterator,street_locator::iterator> p=
  sl.equal_range(std::make_tuple(0));

此限制的原因非常合乎逻辑：由于复合键的哈希值取决于其所有元素，因此不可能从部分信息中计算出来。

C++17 简洁键值规范语法

C++17 引入了 auto 模板参数的声明，可以利用它来消除 Boost.MultiIndex 预定义键值提取器规范中的一些冗余。例如，代替经典的

typedef multi_index_container<
  employee,
  indexed_by<
    ordered_unique<identity<employee> >,
    ordered_non_unique<member<employee,std::string,&employee::name> >,
    ordered_non_unique<
      const_mem_fun<employee,std::size_t,&employee::name_length>
    >
  >
> employee_set;

#include <boost/multi_index/key.hpp>
...
typedef multi_index_container<
  employee,
  indexed_by<
    ordered_unique<identity<employee>>,
    ordered_non_unique<key<&employee::name>>,
    ordered_non_unique<key<&employee::name_length>>
  >
> employee_set;

这会产生完全相同的已定义类型，因为 key 构造只是旧语法的别名。key 可用于缩短 member、const_mem_fun（和 变体）、mem_fun（和 变体）、global_fun 和 composite_key 的规范，并带来额外的简洁性优势

typedef multi_index_container<
  phonebook_entry,
  indexed_by<
    // composite key on family name and given name
    ordered_non_unique<
      key<&phonebook_entry::family_name,&phonebook_entry::given_name>
    >,
    // unique index on phone number
    ordered_unique<key<&phonebook_entry::phone_number>>
  >
> phonebook;

composite_key<
  phonebook_entry,
  member<phonebook_entry,std::string,&phonebook_entry::family_name>,
  member<phonebook_entry,std::string,&phonebook_entry::given_name>
>

Boost.MultiIndex 键值提取器的高级特性

键值提取器 概念允许同一对象从几种不同的类型中提取键，可能是通过适当定义的 operator() 重载

// example of a name extractor from employee and employee *
struct name_extractor
{
  typedef std::string result_type;

  const result_type& operator()(const employee& e)const{return e.name;}
  result_type&       operator()(employee* e)const{return e->name;}
};

// name_extractor can handle elements of type employee...
typedef multi_index_container<
  employee,
  indexed_by<
    ordered_unique<name_extractor>
  >
> employee_set;

// ...as well as elements of type employee *
typedef multi_index_container<
  employee*,
  indexed_by<
    ordered_unique<name_extractor>
  >
> employee_ptr_set;

Boost.MultiIndex 提供的预定义键值提取器充分利用了这种可能性，从而简化了定义 multi_index_container 的过程，其中元素是指向实际对象的指针或引用。以下指定了一个 multi_index_container，其中包含指向按名称排序的员工的指针。

typedef multi_index_container<
  employee *,
  indexed_by<
    ordered_non_unique<member<employee,std::string,&employee::name> > >
> employee_set;

请注意，这与实际 employee 对象的 multi_index_container 的指定方式完全相同：member 负责获取 employee::name 所需的额外解引用。为与 Boost.Ref 中的引用包装器的互操作性提供了类似的功能

typedef multi_index_container<
  boost::reference_wrapper<const employee>,
  indexed_by<
    ordered_non_unique<member<employee,std::string,&employee::name> > >
> employee_set;

实际上，对指针的支持进一步扩展到接受我们称之为链式指针的内容。这样的链式指针通过归纳定义为指向实际元素的原始指针或智能指针或迭代器，指向元素的引用包装器或指向另一个链式指针；也就是说，链式指针是最终解引用到要从中提取键的元素的类指针类型的任意组合。指向 employee 的链式指针的示例包括

• employee *,
• const employee *,
• std::unique_ptr<employee>,
• std::list<boost::reference_wrapper<employee> >::iterator,
• employee **,
• boost::shared_ptr<const employee *>.

为了简要总结在存在引用包装器和指针的情况下 Boost.MultiIndex 键值提取器的不同用法，请考虑以下最终类型

struct T
{
  int        i;
  const int  j;
  int        f()const;
  int        g();
  static int gf(const T&);
  static int gg(T&);
};

下表列出了基于 T 的不同指针和引用包装器类型以及其每个成员的适当键值提取器。

“适用于 const 元素？”列说明了当传递常量元素时，是否可以使用相应的键值提取器（这与第一列中指定的元素有关，而不是引用的 T 对象）。唯一的否定情况是当元素是原始 T 对象时，对于 T::g 和 T:gg，这是有道理的，因为我们正在处理非常量成员函数 (T::g) 和通过非常量引用获取 T 的函数：这也意味着 multi_index_container 的 T 元素不能按 T::g 或 T::gg 排序，因为 multi_index_container 中包含的元素被视为常量。

“读/写？”列显示了哪些组合产生 读/写键值提取器。

在 member 键值提取器的规范中，必须注意保持 const 正确性：在某种意义上，const 限定符被传递到成员部分，即使该特定成员未定义为 const。例如，如果元素类型为 const T *，则按 T::i 排序不是指定为 member<const T,int,&T::i>，而是指定为 member<T,const int,&T::i>。

有关这些键值提取器的实际演示，请参阅示例部分中的 示例 2 和 示例 6。

索引类型

Boost.MultiIndex 教程

容器创建

修订于 2020 年 4 月 19 日

© 版权所有 2003-2020 Joaquín M López Muñoz。根据 Boost 软件许可协议 1.0 版分发。（请参阅随附文件 LICENSE_1_0.txt 或在 https://boost.ac.cn/LICENSE_1_0.txt 复制）