Boost C++ 库

…世界上最受推崇和设计精良的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu，C++ 编码规范

Boost.MultiIndex 哈希索引参考

排序索引

Boost.MultiIndex 参考

顺序索引

头文件  `"boost/multi_index/hashed_index_fwd.hpp"` 概要

namespace boost{

namespace multi_index{

// index specifiers hashed_unique and hashed_non_unique

template<consult hashed_unique reference for arguments>
struct hashed_unique;
template<consult hashed_non_unique reference for arguments>
struct hashed_non_unique;

// indices

namespace detail{

template<implementation defined> class index name is implementation defined;

} // namespace boost::multi_index::detail

} // namespace boost::multi_index 

} // namespace boost

hashed_index_fwd.hpp 提供了索引说明符 hashed_unique 和 hashed_non_unique 及其关联的哈希索引类的向前声明。

头文件  `"boost/multi_index/hashed_index.hpp"` 概要

#include <initializer_list>

namespace boost{

namespace multi_index{

// index specifiers hashed_unique and hashed_non_unique

template<consult hashed_unique reference for arguments>
struct hashed_unique;
template<consult hashed_non_unique reference for arguments>
struct hashed_non_unique;

// indices

namespace detail{

template<implementation defined> class index class name implementation defined;

// index comparison:

// OP is any of ==,!=

template<implementation defined>
bool operator OP(const index class name& x,const index class name& y);

// index specialized algorithms:

template<implementation defined>
void swap(index class name& x,index class name& y);

} // namespace boost::multi_index::detail

} // namespace boost::multi_index 

} // namespace boost

索引说明符 `hashed_unique` 和 `hashed_non_unique`

这些索引说明符分别允许插入允许和不允许重复元素的哈希索引。hashed_unique 和 hashed_non_unique 的语法一致，因此我们以分组方式描述它们。hashed_unique 和 hashed_non_unique 可以根据是否提供索引的标签列表以两种不同的形式实例化。

template<
  typename KeyFromValue,
  typename Hash=boost::hash<KeyFromValue::result_type>,
  typename Pred=std::equal_to<KeyFromValue::result_type>
>
struct (hashed_unique | hashed_non_unique);

template<
  typename TagList,
  typename KeyFromValue,
  typename Hash=boost::hash<KeyFromValue::result_type>,
  typename Pred=std::equal_to<KeyFromValue::result_type>
>
struct (hashed_unique | hashed_non_unique);

如果提供，TagList 必须是类模板 tag 的实例化。模板参数由相应的索引实现使用，有关其可接受类型值的更多解释，请参阅哈希索引参考部分。

哈希索引

哈希索引通过哈希技术提供对 multi_index_container 元素的快速检索。哈希索引根据给定的 Key Extractor（从 multi_index_container 的元素中检索键）、一个返回键哈希值的 Hash 函数对象和一个作为 Key 值上等价关系的二元谓词 Pred 进行具体化。

哈希索引有两种变体：唯一索引，不允许重复元素（关于其关联的等价谓词）；和非唯一索引，接受重复元素。这两种变体的接口相同，因此它们一起记录，并在存在差异时明确指出。

除非另有说明或相应的接口不存在，否则哈希索引（唯一和非唯一）都满足 C++ 对无序关联容器的要求，位于 [unord.req]（分别支持唯一键和等价键）。迭代器（包括索引末尾的迭代器）以及指向元素的指针和引用在关联容器的生命周期内保持有效（交换时可能会更改），或者直到引用的元素被删除或提取；指向提取元素的指针和引用（迭代器则不然）在元素重新插入后再次变为有效。有时，提供的异常安全保证实际上比标准要求的更强。我们只提供对那些不完全符合或不由标准要求规定的类型和操作的描述。

namespace boost{

namespace multi_index{

namespace detail{

template<implementation defined: dependent on types Value, Allocator,
  TagList, KeyFromValue, Hash, Pred>
class name is implementation defined
{ 
public:
  // types:

  typedef typename KeyFromValue::result_type         key_type;
  typedef Value                                      value_type;
  typedef KeyFromValue                               key_from_value;
  typedef Hash                                       hasher;
  typedef Pred                                       key_equal;
  typedef boost::tuple<
    size_type,key_from_value,hasher,key_equal>       ctor_args;
  typedef TagList                                    tag_list;
  typedef Allocator                                  allocator_type;
  typedef typename Allocator::pointer                pointer;
  typedef typename Allocator::const_pointer          const_pointer;
  typedef typename Allocator::reference              reference;
  typedef typename Allocator::const_reference        const_reference;
  typedef implementation defined                     size_type;      
  typedef implementation defined                     difference_type;
  typedef implementation defined                     iterator;
  typedef implementation defined                     const_iterator;
  typedef implementation defined                     local_iterator;
  typedef implementation defined                     const_local_iterator;
  typedef same as owning container                   node_type;
  typedef following [container.insert.return] spec   insert_return_type;

  // construct/destroy/copy:

  index class name& operator=(const index class name& x);
  index class name& operator=(std::initializer_list<value_type> list);

  allocator_type get_allocator()const noexcept;

  // size and capacity:

  bool      empty()const noexcept;
  size_type size()const noexcept;
  size_type max_size()const noexcept;

  // iterators:

  iterator       begin()noexcept;
  const_iterator begin()const noexcept;
  iterator       end()noexcept;
  const_iterator end()const noexcept;
  const_iterator cbegin()const;
  const_iterator cend()const;
 
  iterator       iterator_to(const value_type& x);
  const_iterator iterator_to(const value_type& x)const;

  // modifiers:


  template<typename... Args>
  std::pair<iterator,bool> emplace(Args&&... args);
  template<typename... Args>
  iterator emplace_hint(iterator position,Args&&... args);
  std::pair<iterator,bool> insert(const value_type& x);
  std::pair<iterator,bool> insert(value_type&& x);
  iterator insert(iterator position,const value_type& x);
  iterator insert(iterator position,value_type&& x);
  template<typename InputIterator>
  void insert(InputIterator first,InputIterator last);
  void insert(std::initializer_list<value_type> list);
  insert_return_type insert(node_type&& nh);
  iterator insert(const_iterator position,node_type&& nh);

  node_type extract(const_iterator position);
  node_type extract(const key_type& x);

  iterator  erase(iterator position);
  size_type erase(const key_type& x);
  iterator  erase(iterator first,iterator last);

  bool replace(iterator position,const value_type& x);
  bool replace(iterator position,value_type&& x);
  template<typename Modifier> bool modify(iterator position,Modifier mod);
  template<typename Modifier,typename Rollback>
  bool modify(iterator position,Modifier mod,Rollback back);
  template<typename Modifier> bool modify_key(iterator position,Modifier mod);
  template<typename Modifier,typename Rollback>
  bool modify_key(iterator position,Modifier mod,Rollback back);
  
  void clear()noexcept;
  void swap(index class name& x);

  template<typename Index> void merge(Index&& x);
  template<typename Index>
  std::pair<iterator,bool> merge(
    Index&& x,typename std::remove_reference_t<Index>::const_iterator i);
  template<typename Index>
  void merge(
    Index&& x,
    typename std::remove_reference_t<Index>::const_iterator first,
    typename std::remove_reference_t<Index>::const_iterator last);

  // observers:

  key_from_value key_extractor()const;
  hasher         hash_function()const;
  key_equal      key_eq()const;

  // lookup:

  template<typename CompatibleKey>
  iterator find(const CompatibleKey& x)const;
  template<
    typename CompatibleKey,typename CompatibleHash, typename CompatiblePred
  >
  iterator find(
    const CompatibleKey& x,
    const CompatibleHash& hash,const CompatiblePred& eq)const; 

  template<typename CompatibleKey>
  size_type count(const CompatibleKey& x)const;
  template<
    typename CompatibleKey,typename CompatibleHash, typename CompatiblePred
  >
  size_type count(
    const CompatibleKey& x,
    const CompatibleHash& hash,const CompatiblePred& eq)const;

  template<typename CompatibleKey>
  bool contains(const CompatibleKey& x)const;
  template<
    typename CompatibleKey,typename CompatibleHash, typename CompatiblePred
  >
  bool contains(
    const CompatibleKey& x,
    const CompatibleHash& hash,const CompatiblePred& eq)const;

  template<typename CompatibleKey>
  std::pair<iterator,iterator> equal_range(const CompatibleKey& x)const;
  template<
    typename CompatibleKey,typename CompatibleHash, typename CompatiblePred
  >
  std::pair<iterator,iterator> equal_range(
    const CompatibleKey& x,
    const CompatibleHash& hash,const CompatiblePred& eq)const;

  // bucket interface:

  size_type bucket_count()const noexcept;
  size_type max_bucket_count()const noexcept;
  size_type bucket_size(size_type n)const;
  size_type bucket(const key_type& k)const;

  local_iterator       begin(size_type n);
  const_local_iterator begin(size_type n)const;
  local_iterator       end(size_type n);
  const_local_iterator end(size_type n)const;
  const_local_iterator cbegin(size_type n)const;
  const_local_iterator cend(size_type n)const;

  local_iterator       local_iterator_to(const value_type& x);
  const_local_iterator local_iterator_to(const value_type& x)const;

  // hash policy:

  float load_factor()const noexcept;
  float max_load_factor()const noexcept;
  void  max_load_factor(float z);
  void  rehash(size_type n);
  void  reserve(size_type n);
};

// index comparison:

template<implementation defined>
bool operator==(const index class name& x,const index class name& y);

template<implementation defined>
bool operator!=(const index class name& x,const index class name& y)
{
  return !(x==y);
}

// index specialized algorithms:

template<implementation defined>
void swap(index class name& x,index class name& y);

} // namespace boost::multi_index::detail

} // namespace boost::multi_index 

} // namespace boost

复杂度签名

在此处以及哈希索引操作的描述中，我们采用复杂度签名部分中概述的方案。哈希索引的复杂度签名是：

复制：c(n)=n*log(n)，
插入：平均情况 i(n)=1（摊销常数），最坏情况 i(n)=n_dist，
提示插入：平均情况 h(n)=1（摊销常数），最坏情况 h(n)=n_dist，
删除：d(n)=1（常数），
替换
- 如果新元素键与原始键等价，则 r(n)=1（常数），
- 否则，平均情况 r(n)=1（常数），最坏情况 r(n)=n_dist，
修改：平均情况 m(n)=1（常数），最坏情况 m(n)=n_dist，

其中 n_dist 是总共 n 个元素中不相等元素的数量。

实例化类型

哈希索引在内部实例化为 multi_index_container，并通过使用 indexed_by 和索引说明符 hashed_unique 和 hashed_non_unique 来指定。实例化取决于以下类型：

来自 multi_index_container 的 Value，
来自 multi_index_container 的 Allocator，
来自索引说明符的 TagList（如果提供，否则假定为 tag<>），
来自索引说明符的 KeyFromValue，
来自索引说明符的 Hash，
来自索引说明符的 Pred。

TagList 必须是 tag 的实例化。KeyFromValue 类型确定从 Value 提取键的机制，它必须是来自 Value 的 Key Extractor 的模型。Hash 是一个 CopyConstructible 一元函数对象，它接受一个 KeyFromValue::result_type 类型的参数，并返回一个 std::size_t 类型的值，该值在 [0, std::numeric_limits<std::size_t>::max()) 范围内。Pred 是一个 CopyConstructible 二元谓词，它在 KeyFromValue::result_type 的元素上诱导等价关系。要求 Hash 对象对在 Pred 下等价的键返回相同的值。

嵌套类型

构造函数参数

此元组的第一个元素指示索引在构造时设置的最小桶数。如果使用默认值 0，则使用实现定义的数字。

迭代器
常量迭代器
局部迭代器
常量局部迭代器

这些类型是前向迭代器。它们仅取决于 node_type、索引在 multi_index_container 中的位置以及索引是否唯一（这意味着，例如，从唯一索引转移到非唯一索引的元素的迭代器将失效）。

构造函数、复制和赋值

如索引概念部分所述，索引没有公共构造函数或析构函数。另一方面，提供了赋值。构造后，max_load_factor() 为 1.0。

索引类名称& operator=(const 索引类名称& x);

效果
a=b;
其中 a 和 b 是 *this 和 x 分别所属的 multi_index_container 对象。
返回值：*this。

索引类名称& operator=(std::initializer_list<value_type> list);

效果
a=list;
其中 a 是 *this 所属的 multi_index_container 对象。
返回值：*this。

迭代器

iterator       iterator_to(const value_type& x);
const_iterator iterator_to(const value_type& x)const;

要求：x 是对容器中元素的引用。
返回值：指向 x 的迭代器。
复杂度：常数。
异常安全：nothrow。

修改器

template<typename... Args>
std::pair<iterator,bool> emplace(Args&&... args);

要求：value_type 可以从 args 中就地构造到 multi_index_container 中。
效果：如果以下条件成立，则将使用 std::forward<Args>(args)... 构造的 value_type 对象插入到索引所属的 multi_index_container 中：

索引是非唯一的，或者不存在其他具有等价键的元素，

并且插入被 multi_index_container 的所有其他索引允许。

返回值：返回值是一个对 p。当且仅当插入成功时，p.second 为 true。插入成功时，p.first 指向插入的元素；否则，p.first 指向导致插入被禁止的元素。请注意，可能有多个元素导致插入不被允许。
复杂度：O(I(n))。
异常安全：强异常安全，但即使操作失败，也可能会发生重新哈希。

template<typename... Args>
iterator emplace_hint(iterator position, Args&&... args);

要求：value_type 可以从 args 中就地构造到 multi_index_container 中。position 是索引的有效迭代器。
效果：如果以下条件成立，则将使用 std::forward<Args>(args)... 构造的 value_type 对象插入到索引所属的 multi_index_container 中：

索引是非唯一的，或者不存在其他具有等价键的元素，

并且插入被 multi_index_container 的所有其他索引允许。

position 用作提示以提高操作效率。
返回值：插入成功时，返回指向新插入元素的迭代器。否则，返回指向导致插入被禁止的元素的迭代器。请注意，可能有多个元素导致插入不被允许。
复杂度：O(H(n))。
异常安全：强异常安全，但即使操作失败，也可能会发生重新哈希。

std::pair<iterator,bool> insert(const value_type& x);
std::pair<iterator,bool> insert(value_type&& x);

要求（第一版）：value_type 可以复制插入到 multi_index_container 中。
要求（第二版）：value_type 可以移动插入到 multi_index_container 中。
效果：如果以下条件成立，则将 x 插入到索引所属的 multi_index_container 中：

索引是非唯一的，或者不存在其他具有等价键的元素，

并且插入被 multi_index_container 的所有其他索引允许。

返回值：返回值是一个对 p。当且仅当插入成功时，p.second 为 true。插入成功时，p.first 指向插入的元素；否则，p.first 指向导致插入被禁止的元素。请注意，可能有多个元素导致插入不被允许。
复杂度：O(I(n))。
异常安全：强异常安全，但即使操作失败，也可能会发生重新哈希。

iterator insert(iterator position,const value_type& x);
iterator insert(iterator position,value_type&& x);

要求（第一版）：value_type 可以复制插入到 multi_index_container 中。position 是索引的有效迭代器。
要求（第二版）：value_type 可以移动插入到 multi_index_container 中。position 是索引的有效迭代器。
效果：如果以下条件成立，则将 x 插入到索引所属的 multi_index_container 中：

索引是非唯一的，或者不存在其他具有等价键的元素，

并且插入被 multi_index_container 的所有其他索引允许。

position 用作提示以提高操作效率。
返回值：插入成功时，返回指向新插入元素的迭代器。否则，返回指向导致插入被禁止的元素的迭代器。请注意，可能有多个元素导致插入不被允许。
复杂度：O(H(n))。
异常安全：强异常安全，但即使操作失败，也可能会发生重新哈希。

template<typename InputIterator>
void insert(InputIterator first,InputIterator last);

要求：InputIterator 是输入迭代器。value_type 可以从 *first 就地构造到 multi_index_container 中。first 和 last 不是指向此索引所属的 multi_index_container 的任何索引的迭代器。last 可以从 first 访问。
效果：按照此顺序，对于 [first, last) 中的每个元素，如果以下条件成立，则将其插入到此索引所属的 multi_index_container 中：

索引是非唯一的，或者不存在其他具有等价键的元素，

并且插入被 multi_index_container 的所有其他索引允许。

复杂度：O(m*I(n+m))，其中 m 是 [first, last) 中元素的数量。
异常安全性：基本。

void insert(std::initializer_list<value_type> list);

效果

insert(list.begin(),list.end());

insert_return_type insert(node_type&& nh);

要求：nh.empty() || get_allocator()==nh.get_allocator()。
效果：如果nh为空，则不执行任何操作；否则，如果满足条件，则将nh拥有的节点插入索引所属的multi_index_container中

索引是非唯一的，或者不存在其他具有等价键的元素，

并且插入被 multi_index_container 的所有其他索引允许。

后置条件：nh为空。
返回：类型为insert_return_type的值p。如果nh为空，则p.position为end()，p.inserted为false，并且p.node为空；如果插入成功，则p.position指向插入的元素，p.inserted为true，并且p.node为空；如果插入失败，则p.position指向导致插入被禁止的元素，p.inserted为false，并且p.node拥有原始节点。请注意，可能有多个元素导致插入不被允许。
复杂度：O(I(n))。
异常安全性：强，但即使操作失败，也可能发生重新哈希。如果抛出异常，则nh不会改变。

iterator insert(const_iterator position,node_type&& nh);

要求：nh.empty() || get_allocator()==nh.get_allocator()。position是索引的有效迭代器。
效果：如果nh为空，则不执行任何操作；否则，如果满足条件，则将nh拥有的节点插入索引所属的multi_index_container中

索引是非唯一的，或者不存在其他具有等价键的元素，

并且插入被 multi_index_container 的所有其他索引允许。

position 用作提示以提高操作效率。
后置条件：如果插入成功，则nh为空，否则保持不变。
返回：如果nh为空，则返回end()。如果插入成功，则返回指向新插入元素的迭代器；否则，返回指向导致插入被禁止的元素的迭代器。请注意，可能有多个元素导致插入不被允许。
复杂度：O(H(n))。
异常安全性：强，但即使操作失败，也可能发生重新哈希。如果抛出异常，则nh不会改变。

node_type extract(const_iterator position);

要求：position是索引的有效可解引用的迭代器。
效果：提取position指向的元素的节点。
返回：拥有已提取节点的节点句柄。
复杂度：O(D(n))。
异常安全：nothrow。

node_type extract(const key_type& x);

效果：如果存在，则提取键与x等效的第一个元素的节点。
返回：拥有已提取节点的节点句柄，否则为空。
复杂度：平均情况O(1 + D(n))，最坏情况O(n_dist + D(n))。
异常安全性：强。

iterator erase(iterator position);

要求：position是索引的有效可解引用的迭代器。
效果：删除position指向的元素。
返回：指向被删除元素后一个元素的迭代器，如果不存在这样的元素，则返回end()。
复杂度：O(D(n))。
异常安全：nothrow。

size_type erase(const key_type& x);

效果：删除键与x等效的元素。
返回：已删除元素的数量。
复杂度：平均情况O(1 + m*D(n))，最坏情况O(n_dist + m*D(n))，其中m是已删除元素的数量。
异常安全性：基本。

iterator erase(iterator first,iterator last);

要求：[first,last)是索引的有效范围。
效果：删除[first,last)中的元素。
返回：last。
复杂度：O(m*D(n))，其中m是[first,last)中元素的数量。
异常安全：nothrow。

bool replace(iterator position,const value_type& x);
bool replace(iterator position,value_type&& x);

要求（第一个版本）：value_type是CopyAssignable。position是索引的有效可解引用的迭代器。
要求（第二个版本）：value_type是MoveAssignable。position是索引的有效可解引用的迭代器。
效果：如果对于值x，将值x赋给position指向的元素到索引所属的multi_index_container中

索引是非唯一的，或者不存在其他具有等效键的元素（可能除了*position之外），

并且multi_index_container的所有其他索引都允许替换。

后置条件：在所有情况下都保留position的有效性。如果新值的键与被替换值的键等效，则元素的位置不会改变。
返回：如果替换成功，则返回true，否则返回false。
复杂度：O(R(n))。
异常安全性：强。如果某些用户提供的操作抛出异常，则索引所属的multi_index_container将保持其原始状态。

template<typename Modifier> bool modify(iterator position,Modifier mod);

要求：mod是接受类型为value_type&的参数的单目函数对象。position是索引的有效可解引用的迭代器。mod(e)的执行（其中e是由position指向的元素）不会在e被直接修改后调用multi_index_container的任何操作，或者在修改之前，如果该操作会使position失效。
效果：调用mod(e)（其中e是由position指向的元素），并将*position重新排列到multi_index_container的所有索引中。如果满足以下条件，则重新排列成功：

索引是非唯一的，或者不存在其他具有等价键的元素，

并且multi_index_container的所有其他索引都允许重新排列。

如果重新排列失败，则会删除该元素。
后置条件：如果操作成功，则保留position的有效性。如果修改后的值的键与原始值的键等效，则元素的位置不会改变。
返回：如果操作成功，则返回true，否则返回false。
复杂度：O(M(n))。
异常安全性：基本。如果某些用户提供的操作（包括mod）抛出异常，则position指向的元素将被删除。

template<typename Modifier,typename Rollback>
bool modify(iterator position,Modifier mod,Rollback back);

要求：mod和back是接受类型为value_type&的参数的单目函数对象。position是索引的有效可解引用的迭代器。mod(e)的执行（其中e是由position指向的元素）不会在e被直接修改后调用multi_index_container的任何操作，或者在修改之前，如果该操作会使position失效。back(e)不会调用multi_index_container的任何操作。
效果：调用mod(e)（其中e是由position指向的元素），并尝试将*position重新排列到multi_index_container的所有索引中。如果满足以下条件，则重新排列成功：

索引是非唯一的，或者不存在其他具有等价键的元素，

并且multi_index_container的所有其他索引都允许重新排列。

如果重新排列失败，则调用back(e)：如果e的结果值与其在所有索引中的原始位置和约束一致，则保留该元素，否则将其删除。
后置条件：保留position的有效性，除非在下面描述的条件下元素被删除。如果修改后的值的键与原始值的键等效，则元素的位置不会改变。
返回：如果操作成功，则返回true，否则返回false。
复杂度：O(M(n))。
异常安全性：强，除非mod或back抛出异常，或者back(e)未能正确恢复元素，或者在调用back(e)之后存在抛出异常的用户提供的操作，在这种情况下，修改后的元素将被删除。如果在某些其他用户提供的操作抛出异常后执行的处理代码中back抛出异常，则重新抛出由back生成的异常。

template<typename Modifier> bool modify_key(iterator position,Modifier mod);

要求：key_from_value是从value_type到Key Extractor的读/写。mod是接受类型为key_type&的参数的单目函数对象。position是索引的有效可解引用的迭代器。mod(k)的执行（其中k是由position指向的元素的键）不会在k被直接修改后调用multi_index_container的任何操作，或者在修改之前，如果该操作会使position失效。
效果：等效于modify(position,mod')，其中mod'的定义方式使得mod'(x)与mod(key(x))相同，其中key是索引的内部KeyFromValue对象。

template<typename Modifier,typename Rollback>
bool modify_key(iterator position,Modifier mod,Rollback back);

要求：key_from_value是从value_type到Key Extractor的读/写。mod和back是接受类型为key_type&的参数的单目函数对象。position是索引的有效可解引用的迭代器。mod(k)的执行（其中k是由position指向的元素的键）不会在k被直接修改后调用multi_index_container的任何操作，或者在修改之前，如果该操作会使position失效。back(k)不会调用multi_index_container的任何操作。
效果：等效于modify(position,mod',back')，其中mod'和back'的定义方式使得mod'(x)与mod(key(x))相同，并且back'(x)与back(key(x))相同，其中key是索引的内部KeyFromValue对象。

template<typename Index> void merge(Index&& x);

要求：x是对节点兼容multi_index_container的索引的非常量引用。get_allocator()==x.get_allocator()。
效果
merge(x,x.begin(),x.end());

template<typename Index> std::pair<iterator,bool> merge(
  Index&& x,typename std::remove_reference_t<Index>::const_iterator i);

要求：x是对节点兼容multi_index_container的索引的非常量引用。get_allocator()==x.get_allocator()。i是x的有效可解引用的迭代器。
效果：如果源容器和目标容器相同，则不执行任何操作；否则，如果满足条件，则将i引用的元素的节点转移到目标索引所属的multi_index_container中

索引是非唯一的，或者不存在其他具有等价键的元素，

并且插入被 multi_index_container 的所有其他索引允许。

请注意，在此过程中不会复制或销毁任何元素。
后置条件：如果转移成功，对于源容器中与目标容器中对应索引具有相同iterator/const_iterator类型的任何索引，引用*i的迭代器仍然有效，并表现为目标索引的迭代器。
返回值：返回值是一个pair p。p.second 为 true 当且仅当转移发生或源容器和目标容器相同。如果 p.second 为 true，则 p.first 指向 *i；否则，p.first 指向导致插入被禁止的元素。请注意，可能有多个元素导致不允许插入。
复杂度：如果源容器和目标容器相同，则为常数时间；否则，为O(I(n)+D(x.size()))。
异常安全性：如果源容器和目标容器相同，则为nothrow；否则为强异常安全性。

模板<typename Index> void merge(
  Index&& x,
  typename std::remove_reference_t<Index>::const_iterator first,
  typename std::remove_reference_t<Index>::const_iterator last);

需求：x 是对节点兼容multi_index_container索引的非常量引用。get_allocator()==x.get_allocator()。[first,last) 是x 的有效范围。
作用：如果源容器和目标容器相同，则不执行任何操作；否则，对于[first,last)中的每个节点，按照此顺序，如果满足条件，则将该节点转移到目标索引所属的multi_index_container。

索引是非唯一的，或者不存在其他具有等价键的元素，

并且插入被 multi_index_container 的所有其他索引允许。

请注意，在此过程中不会复制或销毁任何元素。
后置条件：对于源容器中与目标容器中对应索引具有相同iterator/const_iterator类型的任何索引，引用已转移元素的迭代器仍然有效，并表现为目标索引的迭代器。
复杂度：如果源容器和目标容器相同，则为常数时间；否则，为O(m*(I(n+m)+D(x.size())))，其中m 是[first, last)中元素的数量。
异常安全性：如果源容器和目标容器相同，则为nothrow；否则为基本异常安全性。

观察器

除了标准的hash_function和key_eq之外，哈希索引还具有用于检索所用内部键提取器的成员函数。

key_from_value key_extractor()const;

返回用于构造索引的key_from_value对象的副本。
复杂度：常数。

查找

哈希索引提供[unord.req]所需的完整查找功能，即find、count和equal_range。此外，这些成员函数采用模板化，允许使用非标准参数，从而扩展允许的搜索操作的类型。调用查找成员函数时允许的参数类型由以下概念定义。

考虑一个(Hash, Pred)对，其中Hash是类型为Key的值的哈希函子，Pred是诱导Key上等价关系的二元谓词，并附加约束：等价键具有相同的哈希值。(CompatibleKey, CompatibleHash, CompatiblePred)三元组被称为(Hash, Pred)的兼容扩展，如果

CompatibleHash是类型为CompatibleKey的值的哈希函子，
CompatiblePred是(Key, CompatibleKey)上的二元谓词，
CompatiblePred是(CompatibleKey, Key)上的二元谓词，
如果c_eq(ck,k1)，则c_eq(k1,ck)，
如果c_eq(ck,k1)且eq(k1,k2)，则c_eq(ck,k2)，
如果c_eq(ck,k1)且c_eq(ck,k2)，则eq(k1,k2)，
如果c_eq(ck,k1)，则c_hash(ck)==hash(k1)，

对于每个类型为CompatibleHash的c_hash、类型为CompatiblePred的c_eq、类型为Hash的hash、类型为Pred的eq、类型为CompatibleKey的ck以及类型为Key的k1、k2。

此外，如果(CompatibleKey, Hash, Pred)是(Hash, Pred)的兼容扩展，则类型CompatibleKey被称为(Hash, Pred)的兼容键。这意味着Hash和Pred接受类型为CompatibleKey的参数，这通常意味着它们具有其对应operator()成员函数的多个重载。

在兼容扩展或兼容键的上下文中，“等价键”具有其明显的解释。

模板<typename CompatibleKey> iterator find(const CompatibleKey& x)const;

需求：CompatibleKey 是 (hasher, key_equal) 的兼容键。
作用：返回指向其键等价于x的元素的指针，如果不存在这样的元素，则返回end()。
复杂度：平均情况O(1)（常数时间），最坏情况O(n_dist)。

模板<
  typename CompatibleKey,typename CompatibleHash, typename CompatiblePred

>
iterator find(
  const CompatibleKey& x,
  const CompatibleHash& hash,const CompatiblePred& eq)const;

需求：(CompatibleKey, CompatibleHash, CompatiblePred) 是 (hasher, key_equal) 的兼容扩展。
作用：返回指向其键等价于x的元素的指针，如果不存在这样的元素，则返回end()。
复杂度：平均情况O(1)（常数时间），最坏情况O(n_dist)。

模板<typename CompatibleKey>
size_type count(const CompatibleKey& x)const;

需求：CompatibleKey 是 (hasher, key_equal) 的兼容键。
作用：返回键等价于x的元素数量。
复杂度：平均情况O(count(x))，最坏情况O(count(x)+n_dist)。

模板<
  typename CompatibleKey,typename CompatibleHash, typename CompatiblePred

>
size_type count(
  const CompatibleKey& x,
  const CompatibleHash& hash,const CompatiblePred& eq)const;

需求：(CompatibleKey, CompatibleHash, CompatiblePred) 是 (hasher, key_equal) 的兼容扩展。
作用：返回键等价于x的元素数量。
复杂度：平均情况O(count(x,hash,eq))，最坏情况O(count(x,hash,eq)+n_dist)。

模板<typename CompatibleKey>
bool contains(const CompatibleKey& x)const;

需求：CompatibleKey 是 (hasher, key_equal) 的兼容键。
作用：如果存在键等价于x的元素，则返回true；否则返回false。
复杂度：平均情况O(1)（常数时间），最坏情况O(n_dist)。

模板<
  typename CompatibleKey,typename CompatibleHash, typename CompatiblePred

>
bool contains(
  const CompatibleKey& x,
  const CompatibleHash& hash,const CompatiblePred& eq)const;

需求：(CompatibleKey, CompatibleHash, CompatiblePred) 是 (hasher, key_equal) 的兼容扩展。
作用：如果存在键等价于x的元素，则返回true；否则返回false。
复杂度：平均情况O(1)（常数时间），最坏情况O(n_dist)。

模板<typename CompatibleKey>
std::pair<iterator,iterator> equal_range(const CompatibleKey& x)const;

需求：CompatibleKey 是 (hasher, key_equal) 的兼容键。
作用：返回包含所有键等价于x的元素（且仅包含这些元素）的范围，如果不存在这样的元素，则返回(end(),end())。
复杂度：平均情况O(1)（常数时间），最坏情况O(n_dist)。

模板<
  typename CompatibleKey,typename CompatibleHash, typename CompatiblePred

>
std::pair<iterator,iterator> equal_range(
  const CompatibleKey& x,
  const CompatibleHash& hash,const CompatiblePred& eq)const;

需求：(CompatibleKey, CompatibleHash, CompatiblePred) 是 (hasher, key_equal) 的兼容扩展。
作用：返回包含所有键等价于x的元素（且仅包含这些元素）的范围，如果不存在这样的元素，则返回(end(),end())。
复杂度：平均情况O(1)（常数时间），最坏情况O(n_dist)。

桶接口

local_iterator       local_iterator_to(const value_type& x);
const_local_iterator local_iterator_to(const value_type& x)const;

要求：x 是对容器中元素的引用。
返回值：指向 x 的迭代器。
复杂度：常数。
异常安全：nothrow。

哈希策略

void rehash(size_type n);

作用：必要时增加内部桶的数量，以使size()/bucket_count()不超过最大负载因子，并且bucket_count()>=n。
后置条件：包含元素的迭代器和引用的有效性保持不变。
复杂度：O(m)，其中m是索引中非等价元素的数量。
异常安全性：强。

void reserve(size_type n);

效果

rehash(std::ceil(n/max_load_factor()));

比较

模板<实现定义>
bool operator==(const 索引类名& x,const 索引类名& y);

需求：x.key_extractor()、x.hash_function()和x.key_eq()的行为与y中的对应对象相同。对于x或y中的任意两个元素e1、e2，如果e1==e2，则它们的键是等价的。
返回值：如果x和y具有相同的大小，并且对于x中存在的每个键k，x.equal_range(k)范围等于（考虑value_type的==运算符）y.equal_range(k)（在元素排列下），则返回true。
复杂度：设k₁,...,k_m是x中存在的不同键

如果对于每个k_i，x.equal_range(k_i)的排列顺序与y.equal_range(k_i)相同，则平均情况为O(x.size())，最坏情况为O(x.size()²)。

否则，平均情况为O(Σ(x.count(k_i)²))，最坏情况为O(x.size()²)。

（对于唯一索引，上述公式简化为平均情况O(x.size())，最坏情况O(x.size()²)。）

序列化

索引不能单独序列化，只能作为其嵌入的multi_index_container的一部分进行序列化。在描述与嵌入容器的序列化相关的哈希索引的其他前提条件和保证时，我们使用multi_index_container 序列化部分中定义的概念。

操作：将multi_index_container m保存到输出归档（XML归档）ar。

需求：容器没有施加其他额外要求。

操作：从输入归档（XML归档）ar加载multi_index_container m'。

需求：除了通用要求之外，二元谓词value_eq(m'.get())必须与value_eq(m.get())序列化兼容，其中value_eq(c)(x,y)定义为c.key_eq()(c.key_extractor()(x),c.key_extractor()(y))，i是容器中哈希索引的位置。
后置条件：成功加载后，范围[begin(), end())包含[m.get().begin(), m.get().end())中每个元素的已恢复副本，但顺序可能不同。

操作：将iterator或const_iterator it保存到输出归档（XML归档）ar。

需求：it是索引的有效迭代器。关联的multi_index_container已保存。

操作：从输入归档（XML归档）ar加载iterator或const_iterator it'。

后置条件：成功加载后，如果it可解引用，则*it'是*it的已恢复副本；否则it'==end()。
注意：it可以是const_iterator，而已恢复的it'是iterator，反之亦然。

操作：将local_iterator或const_local_iterator it保存到输出归档（XML归档）ar。

需求：it是索引的有效局部迭代器。关联的multi_index_container已保存。

操作：从输入归档（XML归档）ar加载local_iterator或const_local_iterator it'。

后置条件：成功加载后，如果it可解引用，则*it'是*it的已恢复副本；如果it是某个n的m.get().end(n)，则it'==m'.get().end(n)（其中m是原始multi_index_container，m'是其已恢复的副本，i是索引的序号）。
注意： 允许it 是一个 const_local_iterator 而恢复后的 it' 是一个 local_iterator，反之亦然。

排序索引

Boost.MultiIndex 参考

顺序索引

2024年3月15日修订

Boost.MultiIndex 哈希索引参考

目录

头文件 "boost/multi_index/hashed_index_fwd.hpp" 概要

头文件 "boost/multi_index/hashed_index.hpp" 概要

头文件 `"boost/multi_index/hashed_index_fwd.hpp"` 概要

头文件 `"boost/multi_index/hashed_index.hpp"` 概要