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 支持这种键提取。考虑以下容器，其中第三个索引的排序基于 name 字段的长度

#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 的类型，它是 引用限定的，与 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 的函数：这也意味着 T 元素的 multi_index_container 不能通过 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 中复制）