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 元素的快速检索。哈希索引根据给定的 键提取器 进行特定化，该提取器从 multi_index_container 的元素中检索键，一个 Hash 函数对象，它为键返回哈希值，以及一个二元谓词 Pred，它充当 Key 值的等价关系。

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

除非另有说明或相应的接口不存在，否则哈希索引（唯一和非唯一）都满足 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 的模型。Hash 是一个 CopyConstructible 一元函数对象，它接受类型为 KeyFromValue::result_type 的单个参数，并返回类型为 std::size_t 且范围为 [0, std::numeric_limits<std::size_t>::max()) 的值。Pred 是一个 CopyConstructible 二元谓词，它在 KeyFromValue::result_type 的元素上诱导等价关系。要求 Hash 对象为在 Pred 下等效的键返回相同的值。

嵌套类型

ctor_args

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

iterator
const_iterator
local_iterator
const_local_iterator

这些类型是前向迭代器。它们仅依赖于 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 的任何索引的迭代器。从 first 可以到达 last。
效果： 对于 [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 不会更改。
返回： 如果 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 可复制赋值。position 是索引的有效可解引用迭代器。
要求（第二个版本）： value_type 可移动赋值。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 被直接修改后或在修改之前（如果该操作会使 position 无效）不会调用 multi_index_container 的任何操作。
效果： 调用 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 被直接修改后或在修改之前（如果该操作会使 position 无效）不会调用 multi_index_container 的任何操作。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 读取/写入的 键提取器。mod 是接受 key_type& 类型参数的一元函数对象。position 是索引的有效可解引用迭代器。mod(k) 的执行（其中 k 是由 position 指向的元素的键）在 k 被直接修改后或在修改之前（如果该操作会使 position 无效）不会调用 multi_index_container 的任何操作。
效果： 等效于 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 读取/写入的 键提取器。mod 和 back 是接受 key_type& 类型参数的一元函数对象。position 是索引的有效可解引用迭代器。mod(k) 的执行（其中 k 是由 position 指向的元素的键）在 k 被直接修改后或在修改之前（如果该操作会使 position 无效）不会调用 multi_index_container 的任何操作。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 的迭代器仍然有效，并且表现为目标索引的迭代器。
返回： 返回值是一对 p。当且仅当发生转移或者源容器和目标容器相同时，p.second 为 true。如果 p.second 为 true，则 p.first 指向 *i；否则，p.first 指向导致插入被禁止的元素。请注意，可能有多个元素导致不允许插入。
复杂度： 如果源容器和目标容器相同，则为常数；否则，为 O(I(n)+D(x.size()))。
异常安全性： 如果源容器和目标容器相同，则为 nothrow；否则为强异常安全。

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);

要求： 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() 成员函数的多个重载。

在兼容扩展或兼容键的上下文中，“等效键”表达式采用其显而易见的解释。

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

要求： CompatibleKey 是 (hasher, key_equal) 的兼容键。
效果： 返回指向键与 x 等效的元素的指针，如果不存在此类元素，则返回 end()。
复杂度： 平均情况 O(1)（常数），最坏情况 O(n_dist)。

template<
  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)。

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

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

template<
  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)。

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

要求： CompatibleKey 是 (hasher, key_equal) 的兼容键。
效果： 当且仅当存在键与 x 等效的元素时，返回 true。
复杂度： 平均情况 O(1)（常数），最坏情况 O(n_dist)。

template<
  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。
复杂度： 平均情况 O(1)（常数），最坏情况 O(n_dist)。

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

要求： CompatibleKey 是 (hasher, key_equal) 的兼容键。
效果： 返回一个范围，其中包含键与 x 等效的所有元素（且仅包含这些元素），如果不存在此类元素，则返回 (end(),end())。
复杂度： 平均情况 O(1)（常数），最坏情况 O(n_dist)。

template<
  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()));

比较

template<实现定义>
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"` 概要