Boost C++库

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

Boost.MultiIndex有序索引参考

index reference
索引参考
Boost.MultiIndex reference
Boost.MultiIndex参考
ranked indices
排名索引

目录

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

namespace boost{

namespace multi_index{

// index specifiers ordered_unique and ordered_non_unique

template<consult ordered_unique reference for arguments>
struct ordered_unique;
template<consult ordered_non_unique reference for arguments>
struct ordered_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

ordered_index_fwd.hpp 提供了索引说明符 ordered_unique 和 ordered_non_unique 以及它们相关的 有序索引 类的向前声明。

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

#include <initializer_list>

namespace boost{

namespace multi_index{

// index specifiers ordered_unique and ordered_non_unique

template<consult ordered_unique reference for arguments>
struct ordered_unique;
template<consult ordered_non_unique reference for arguments>
struct ordered_non_unique;

// indices

namespace detail{

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

// index comparison:

// OP is any of ==,<,!=,>,>=,<=

template<arg set 1,arg set 2>
bool operator OP(
  const index class name<arg set 1>& x,const index class name<arg set 2>& 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

索引说明符ordered_unique和ordered_non_unique

这些 索引说明符 分别允许插入具有和不具有重复元素的 有序索引。ordered_unique 和 ordered_non_unique 的语法一致，因此我们以分组方式对其进行描述。ordered_unique 和 ordered_non_unique 可以根据是否提供索引的标签列表以两种不同的形式实例化。

template<
  typename KeyFromValue,
  typename Compare=std::less<KeyFromValue::result_type>
>
struct (ordered_unique | ordered_non_unique);

template<
  typename TagList,
  typename KeyFromValue,
  typename Compare=std::less<KeyFromValue::result_type>
>
struct (ordered_unique | ordered_non_unique);

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

有序索引

有序索引为 multi_index_container 中包含的底层元素堆提供了类似集合的接口。有序索引根据给定的 键提取器 (Key Extractor)（从 multi_index_container 的元素中检索键）和比较谓词进行特化。

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

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

namespace boost{

namespace multi_index{

implementation defined unbounded; // see range()

namespace detail{

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

  typedef typename KeyFromValue::result_type         key_type;
  typedef Value                                      value_type;
  typedef KeyFromValue                               key_from_value;
  typedef Compare                                    key_compare;
  typedef implementation defined                     value_compare;
  typedef boost::tuple<key_from_value,key_compare>   ctor_args;
  typedef TagList                                    tag_list;
  typedef Allocator                                  allocator_type;
  typedef typename Allocator::reference              reference;
  typedef typename Allocator::const_reference        const_reference;
  typedef implementation defined                     iterator;
  typedef implementation defined                     const_iterator;
  typedef implementation defined                     size_type;      
  typedef implementation defined                     difference_type;
  typedef typename Allocator::pointer                pointer;
  typedef typename Allocator::const_pointer          const_pointer;
  typedef equivalent to
    std::reverse_iterator<iterator>                  reverse_iterator;
  typedef equivalent to
    std::reverse_iterator<const_iterator>            const_reverse_iterator;
  typedef same as owning container                   node_type;
  typedef following [container.insert.return] spec   insert_return_type;

  // construct/copy/destroy:

  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;

  // iterators:

  iterator               begin()noexcept;
  const_iterator         begin()const noexcept;
  iterator               end()noexcept;
  const_iterator         end()const noexcept;
  reverse_iterator       rbegin()noexcept;
  const_reverse_iterator rbegin()const noexcept;
  reverse_iterator       rend()noexcept;
  const_reverse_iterator rend()const noexcept;
  const_iterator         cbegin()const noexcept;
  const_iterator         cend()const noexcept;
  const_reverse_iterator crbegin()const noexcept;
  const_reverse_iterator crend()const noexcept;
 
  iterator       iterator_to(const value_type& x);
  const_iterator iterator_to(const value_type& x)const;

  // capacity:

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

  // 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 swap(index class name& x);
  void clear()noexcept;

  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;
  key_compare    key_comp()const;
  value_compare  value_comp()const;

  // set operations:

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

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

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

  template<typename CompatibleKey>
  iterator lower_bound(const CompatibleKey& x)const;
  template<typename CompatibleKey,typename CompatibleCompare>
  iterator lower_bound(
    const CompatibleKey& x,const CompatibleCompare& comp)const;

  template<typename CompatibleKey>
  iterator upper_bound(const CompatibleKey& x)const;
  template<typename CompatibleKey,typename CompatibleCompare>
  iterator upper_bound(
    const CompatibleKey& x,const CompatibleCompare& comp)const;

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

  // range:

  template<typename LowerBounder,typename UpperBounder>
  std::pair<iterator,iterator> range(
    LowerBounder lower,UpperBounder upper)const;
};

// index comparison:

template<arg set 1,arg set 2>
bool operator==(
  const index class name<arg set 1>& x,
  const index class name<arg set 2>& y)
{
  return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
}

template<arg set 1,arg set 2>
bool operator<(
  const index class name<arg set 1>& x,
  const index class name<arg set 2>& y)
{
  return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
}

template<arg set 1,arg set 2>
bool operator!=(
  const index class name<arg set 1>& x,
  const index class name<arg set 2>& y)
{
  return !(x==y);
}

template<arg set 1,arg set 2>
bool operator>(
  const index class name<arg set 1>& x,
  const index class name<arg set 2>& y)
{
  return y<x;
}

template<arg set 1,arg set 2>
bool operator>=(
  const index class name<arg set 1>& x,
  const index class name<arg set 2>& y)
{
  return !(x<y);
}

template<arg set 1,arg set 2>
bool operator<=(
  const index class name<arg set 1>& x,
  const index class name<arg set 2>& 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

复杂度签名

在这里以及有序索引操作的描述中，我们采用在 复杂度签名部分 中概述的方案。有序索引的复杂度签名是：

实例化类型

有序索引在 multi_index_container 中内部实例化，并通过使用 indexed_by 和 索引说明符 ordered_unique 和 ordered_non_unique 来指定。实例化取决于以下类型：

TagList 必须是 tag 的实例化。类型 KeyFromValue（确定从 Value 提取键的机制）必须是来自 Value 的 键提取器 (Key Extractor) 的模型。Compare 是一个 CopyConstructible 二元谓词，它在 KeyFromValue::result_type 的元素上诱导严格弱序。

嵌套类型

迭代器 (iterator)
常量迭代器 (const_iterator)
这些类型仅取决于 node_type 和 multi_index_container 中索引的位置。

构造函数、复制和赋值

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

索引类名& 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 中进行就地构造 (EmplaceConstructible)。
效果：如果以下条件成立，则将使用 std::forward<Args>(args)... 构造的 value_type 对象插入到索引所属的 multi_index_container 中： 返回值：返回值是一个对 p。当且仅当插入发生时，p.second 为 true。成功插入后，p.first 指向插入的元素；否则，p.first 指向导致插入被禁止的元素。请注意，可能有多个元素导致插入不被允许。
复杂度：O(I(n))。
异常安全性：强 (Strong)。
template<typename... Args>
iterator emplace_hint(iterator position, Args&&... args);
前提条件：value_type 可以从 args 中在 multi_index_container 中进行就地构造 (EmplaceConstructible)。position 是索引的有效迭代器。
效果：如果以下条件成立，则将使用 std::forward<Args>(args)... 构造的 value_type 对象插入到索引所属的 multi_index_container 中： position 用作提示以提高操作效率。如果成功，插入将尽可能靠近 position 之前的那个位置发生。
返回值：成功插入后，返回指向新插入元素的迭代器。否则，返回指向导致插入被禁止的元素的迭代器。请注意，可能有多个元素导致插入不被允许。
复杂度：O(H(n))。
异常安全性：强 (Strong)。
std::pair<iterator,bool> insert(const value_type& x);
std::pair<iterator,bool> insert(value_type&& x);
前提条件（第一版）：value_type 可以复制插入到 multi_index_container 中 (CopyInsertable)。
前提条件（第二版）：value_type 可以移动插入到 multi_index_container 中 (MoveInsertable)。
效果：如果以下条件成立，则将 x 插入到索引所属的 multi_index_container 中： 返回值：返回值是一个对 p。当且仅当插入发生时，p.second 为 true。成功插入后，p.first 指向插入的元素；否则，p.first 指向导致插入被禁止的元素。请注意，可能有多个元素导致插入不被允许。
复杂度：O(I(n))。
异常安全性：强 (Strong)。
iterator insert(iterator position,const value_type& x);
iterator insert(iterator position,value_type&& x);
前提条件（第一版）：value_type 可以复制插入到 multi_index_container 中 (CopyInsertable)。position 是索引的有效迭代器。
前提条件（第二版）：value_type 可以移动插入到 multi_index_container 中 (MoveInsertable)。position 是索引的有效迭代器。
效果：如果以下条件成立，则将 x 插入到索引所属的 multi_index_container 中： position 用作提示以提高操作效率。如果成功，插入将尽可能靠近 position 之前的那个位置发生。
返回值：成功插入后，返回指向新插入元素的迭代器。否则，返回指向导致插入被禁止的元素的迭代器。请注意，可能有多个元素导致插入不被允许。
复杂度：O(H(n))。
异常安全性：强 (Strong)。
template<typename InputIterator>
void insert(InputIterator first,InputIterator last);
前提条件：InputIterator 是输入迭代器。value_type 可以从 *first 中在 multi_index_container 中进行就地构造 (EmplaceConstructible)。first 和 last 不是指向此索引所属的 multi_index_container 的任何索引的迭代器。last 可以从 first 到达。
效果：按照此顺序，对于 [first, last) 中的每个元素，如果以下条件成立，则将其插入到此索引所属的 multi_index_container 中： 复杂度：O(m*H(n+m))，其中 m 是 [first, last) 中元素的数量。
异常安全性：基本 (Basic)。
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 中： 后置条件：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))。
异常安全性：强 (Strong)。如果抛出异常，则不会更改 nh。
iterator insert(const_iterator position,node_type&& nh);
前提条件：nh.empty() || get_allocator()==nh.get_allocator()。position 是索引的有效迭代器。
效果：如果 nh 为空，则不执行任何操作；否则，如果以下条件成立，则将 nh 拥有的节点插入到索引所属的 multi_index_container 中： position 用作提示以提高操作效率。如果成功，插入将尽可能靠近 position 之前的那个位置发生。
后置条件：如果插入成功，则 nh 为空，否则保持不变。
返回值：如果 nh 为空，则返回 end()。成功插入后，返回指向新插入元素的迭代器；否则，返回指向导致插入被禁止的元素的迭代器。请注意，可能有多个元素导致插入不被允许。
复杂度：O(H(n))。
异常安全性：强 (Strong)。如果抛出异常，则不会更改 nh。
node_type extract(const_iterator position);
前提条件：position 是索引的有效可解引用的迭代器。
效果：提取 position 指向的元素的节点。
返回值：拥有已提取节点的节点句柄。
复杂度：O(D(n))。
异常安全性：nothrow。
node_type extract(const key_type& x);
效果：如果存在，则提取键与 x 等效的第一个元素的节点。
返回值：拥有已提取节点的节点句柄，否则为空。
复杂度：O(log(n) + D(n))。
异常安全性：强 (Strong)。
iterator erase(iterator position);
前提条件：position 是索引的有效可解引用的迭代器。
效果：删除 position 指向的元素。
返回值：指向已删除元素后一个元素的迭代器，如果不存在这样的元素，则返回 end()。
复杂度：O(D(n))。
异常安全性：nothrow。
size_type erase(const key_type& x);
效果：删除键与 x 等效的元素。
返回值：删除的元素数量。
复杂度：O(log(n) + m*D(n))，其中 m 是删除的元素数量。
异常安全性：基本 (Basic)。
iterator erase(iterator first,iterator last);
前提条件：[first,last) 是索引的有效范围。
效果：删除 [first,last) 中的元素。
返回值：last。
复杂度：O(log(n) + 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指向的元素到所属多索引容器中， 后置条件：在所有情况下都保留position的有效性。如果新值的键与被替换值的键等效，则元素的位置不会改变。
返回值：如果替换发生，则返回true，否则返回false。
复杂度：O(R(n))。
异常安全性：强异常安全性。如果某个用户提供的操作抛出异常，则所属多索引容器保持其原始状态。
template<typename Modifier> bool modify(iterator position,Modifier mod);
需求：mod是一个一元函数对象，接受value_type&类型的参数。position 是索引中一个有效的可解引用的迭代器。mod(e) 的执行（其中e是由position指向的元素）不会在e被直接修改后调用多索引容器的任何操作，或者在修改之前，如果该操作会使position失效。
效果：调用mod(e)（其中e是由position指向的元素）并将*position重新排列到多索引容器的所有索引中。如果如果重新排列失败，则删除该元素。
后置条件：如果操作成功，则保留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失效。back(e)不会调用多索引容器的任何操作。
效果：调用mod(e)（其中e是由position指向的元素），并尝试将*position重新排列到多索引容器的所有索引中。如果重新排列成功，则如果重新排列失败，则调用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失效。
效果：等效于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失效。back(k)不会调用多索引容器的任何操作。
效果：等效于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中一个有效的可解引用的迭代器。
效果：如果源容器和目标容器相同，则不执行任何操作；否则，如果请注意，在此过程中不会复制或销毁任何元素。
后置条件：如果传输成功，对于源容器中任何与目标容器中相应索引具有相同iterator/const_iterator类型的索引，引用*i的迭代器将保持有效，并充当目标索引的迭代器。
返回值：返回值是一个pair 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)中的每个节点，按此顺序，如果请注意，在此过程中不会复制或销毁任何元素。
后置条件：对于源容器中任何与目标容器中相应索引具有相同iterator/const_iterator类型的索引，引用已传输元素的迭代器将保持有效，并充当目标索引的迭代器。
复杂度：如果源容器和目标容器相同，则为常数；否则，为O(m*(I(n+m)+D(x.size())))，其中m是[first, last)中元素的数量。
异常安全性：如果源容器和目标容器相同，则为nothrow；否则为基本异常安全性。

观察器

除了标准的key_comp和value_comp之外，有序索引还有一个用于检索所使用的内部键提取器的成员函数。

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

集合操作

有序索引提供[associative.reqmts]所需的全套查找功能，即find、count、lower_bound、upper_bound和equal_range。此外，这些成员函数是模板化的，允许使用非标准参数，从而扩展允许的搜索操作类型。调用查找成员函数时允许的参数类型由以下概念定义。

考虑一个二元谓词Compare，它对Key类型的数值引起严格弱排序。如果 (CompatibleKey, CompatibleCompare) 对被称为Compare的兼容扩展，则

  1. CompatibleCompare是(Key, CompatibleKey)上的二元谓词，
  2. CompatibleCompare是(CompatibleKey, Key)上的二元谓词，
  3. 如果c_comp(ck,k1)则!c_comp(k1,ck)，
  4. 如果!c_comp(ck,k1)且!comp(k1,k2)则!c_comp(ck,k2)，
  5. 如果!c_comp(k1,ck)且!comp(k2,k1)则!c_comp(k2,ck)，
对于每种类型为CompatibleCompare的c_comp、类型为Compare的comp、类型为CompatibleKey的ck以及类型为Key的k1、k2。

此外，如果 (CompatibleKey, Compare) 是Compare的兼容扩展，则类型CompatibleKey被称为Compare的兼容键。这意味着Compare除了是严格弱排序外，还接受CompatibleKey类型的参数，这通常意味着它有几个operator()的重载。

在兼容扩展或兼容键的上下文中，“等价”、“小于”和“大于”采用其明显的解释。

template<typename CompatibleKey> iterator find(const CompatibleKey& x)const;
要求：CompatibleKey 是 key_compare 的兼容键。
效果：返回指向其键等价于 x 的元素的指针，如果这样的元素不存在则返回 end()。
复杂度：O(log(n))。
template<typename CompatibleKey,typename CompatibleCompare>
iterator find(const CompatibleKey& x,const CompatibleCompare& comp)const;
要求：(CompatibleKey, CompatibleCompare) 是 key_compare 的兼容扩展。
效果：返回指向其键等价于 x 的元素的指针，如果这样的元素不存在则返回 end()。
复杂度：O(log(n))。
template<typename CompatibleKey>
size_type count(const CompatibleKey& x)const;
要求：CompatibleKey 是 key_compare 的兼容键。
效果：返回键等价于 x 的元素数量。
复杂度：O(log(n) + count(x))。
template<typename CompatibleKey,typename CompatibleCompare>
size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const;
要求：(CompatibleKey, CompatibleCompare) 是 key_compare 的兼容扩展。
效果：返回键等价于 x 的元素数量。
复杂度：O(log(n) + count(x,comp))。
template<typename CompatibleKey>
bool contains(const CompatibleKey& x)const;
要求：CompatibleKey 是 key_compare 的兼容键。
效果：如果存在键等价于 x 的元素，则返回 true；否则返回 false。
复杂度：O(log(n))。
template<typename CompatibleKey,typename CompatibleCompare>
bool contains(const CompatibleKey& x,const CompatibleCompare& comp)const;
要求：(CompatibleKey, CompatibleCompare) 是 key_compare 的兼容扩展。
效果：如果存在键等价于 x 的元素，则返回 true；否则返回 false。
复杂度：O(log(n))。
template<typename CompatibleKey>
iterator lower_bound(const CompatibleKey& x)const;
要求：CompatibleKey 是 key_compare 的兼容键。
效果：返回指向第一个键不小于 x 的元素的迭代器，如果这样的元素不存在则返回 end()。
复杂度：O(log(n))。
template<typename CompatibleKey,typename CompatibleCompare>
iterator lower_bound(const CompatibleKey& x,const CompatibleCompare& comp)const;
要求：(CompatibleKey, CompatibleCompare) 是 key_compare 的兼容扩展。
效果：返回指向第一个键不小于 x 的元素的迭代器，如果这样的元素不存在则返回 end()。
复杂度：O(log(n))。
template<typename CompatibleKey>
iterator upper_bound(const CompatibleKey& x)const;
要求：CompatibleKey 是 key_compare 的兼容键。
效果：返回指向第一个键大于 x 的元素的迭代器，如果这样的元素不存在则返回 end()。
复杂度：O(log(n))。
template<typename CompatibleKey,typename CompatibleCompare>
iterator upper_bound(const CompatibleKey& x,const CompatibleCompare& comp)const;
要求：(CompatibleKey, CompatibleCompare) 是 key_compare 的兼容扩展。
效果：返回指向第一个键大于 x 的元素的迭代器，如果这样的元素不存在则返回 end()。
复杂度：O(log(n))。
template<typename CompatibleKey>
std::pair<iterator,iterator> equal_range(
  const CompatibleKey& x)const;
要求：CompatibleKey 是 key_compare 的兼容键。
效果：等价于 make_pair(lower_bound(x),upper_bound(x))。
复杂度：O(log(n))。
template<typename CompatibleKey,typename CompatibleCompare>
std::pair<iterator,iterator> equal_range(
  const CompatibleKey& x,const CompatibleCompare& comp)const;
要求：(CompatibleKey, CompatibleCompare) 是 key_compare 的兼容扩展。
效果：等价于 make_pair(lower_bound(x,comp),upper_bound(x,comp))。
复杂度：O(log(n))。

范围操作

成员函数 range 未为已排序的关联容器定义，但有序索引将其作为方便的实用程序提供。范围或区间由下界和上界的两个条件定义，这些条件是根据以下概念建模的。

考虑一个二元谓词 Compare，它在类型为 Key 的值上诱导一个严格的弱序。如果满足以下条件，则称类型 LowerBounder 为 Compare 的下界：

  1. LowerBounder 是 Key 上的谓词，
  2. 如果 lower(k1) 且 !comp(k2,k1)，则 lower(k2)，
对于每个类型为 LowerBounder 的 lower、类型为 Compare 的 comp 以及类型为 Key 的 k1、k2。
  1. 类似地，上界是一个类型为 UpperBounder 的类型，满足以下条件：
  2. UpperBounder 是 Key 上的谓词，
如果 upper(k1) 且 !comp(k1,k2)，则 upper(k2)，

template<typename LowerBounder,typename UpperBounder>
std::pair<iterator,iterator> range(
  LowerBounder lower,UpperBounder upper)const;
要求：LowerBounder 和 UpperBounder 分别是 key_compare 的下界和上界。
效果：返回一对迭代器，它们指向同时满足 lower 和 upper 的元素子序列的开头和结尾之后的一个位置。如果不存在这样的元素，则两个迭代器都指向满足 lower 的第一个元素，或者如果后者元素不存在，则等于 end()。
复杂度：O(log(n))。
变体：可以提供单值 boost::multi_index::unbounded 来代替 lower 或 upper（或两者）。这充当所有类型为 key_type 的值都满足的谓词。

序列化

索引本身不能被序列化，而只能作为将其嵌入其中的 multi_index_container 的一部分进行序列化。在描述与嵌入容器的序列化相关的有序索引的附加前提条件和保证时，我们使用 multi_index_container 序列化部分 中定义的概念。

操作：将 multi_index_container m 保存到输出存档（XML 存档）ar 中。
要求：容器没有施加额外的要求。
操作：从输入存档（XML 存档）ar 中加载 multi_index_container m'。
要求：除了常规要求外，value_comp() 必须与 m.get<i>().value_comp() 兼容序列化，其中 i 是容器中排序索引的位置。
后置条件：成功加载后，[begin(), end()) 中的每个元素都是 [m.get<i>().begin(), m.get<i>().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，反之亦然。
index reference
索引参考
Boost.MultiIndex reference
Boost.MultiIndex参考
ranked indices
排名索引


2022年2月5日修订

© 版权所有 2003-2022 Joaquín M López Muñoz。根据 Boost 软件许可证版本 1.0 分发。（参见随附文件 LICENSE_1_0.txt 或复制自 https://boost.ac.cn/LICENSE_1_0.txt)