Boost C++ 库

...世界上最受推崇和专业设计的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu, C++ 编码标准

Boost.MultiIndex 有序索引参考

索引参考

Boost.MultiIndex 参考

排名索引

头文件  `"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 中包含的元素底层堆提供类似 set 的接口。有序索引根据给定的 Key Extractor 进行特殊化，该提取器从 multi_index_container 的元素中检索键和比较谓词。

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

除非另有说明或相应的接口不存在，否则有序索引（unique 和 non-unique）满足 [associative.reqmts] 中关联容器的 C++ 要求（分别支持 unique 和等效键。）迭代器（包括索引末尾的迭代器）以及指向元素的指针和引用在关联容器的生命周期内（容器可以在交换时更改）或直到引用的元素被擦除或提取之前仍然有效；指向提取元素的指针和引用（但不包括迭代器）在元素重新插入后再次变为有效。我们仅提供那些不完全符合或不是标准要求强制要求的类型和操作的描述。

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

复杂度特征

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

复制：c(n)=n*log(n)，
插入：i(n)=log(n)，
提示插入：如果提示元素紧跟在插入点之后，则 h(n)=1（摊销常数），否则 h(n)=log(n)，
删除：d(n)=1（摊销常数），
替换：如果元素位置未更改，则 r(n)=1（常数），否则 r(n)=log(n)，
修改：如果元素位置未更改，则 m(n)=1（常数），否则 m(n)=log(n)。

实例化类型

有序索引在内部实例化到 multi_index_container，并通过 indexed_by 与索引说明符 ordered_unique 和 ordered_non_unique 一起指定。实例化取决于以下类型

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

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 中。
效果： 如果满足以下条件，则将使用 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 用作提示，以提高操作效率。如果成功，插入发生在尽可能靠近 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 用作提示，以提高操作效率。如果成功，插入发生在尽可能靠近 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*H(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 用作提示，以提高操作效率。如果成功，插入发生在尽可能靠近 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(log(n) + D(n))。
异常安全性： 强。

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 是删除的元素数。
异常安全性： 基本。

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 指向的元素到索引所属的 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 的读/写 Key Extractor。 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 的读/写 Key Extractor。 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；否则为基本。

观察器

除了标准 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 的兼容扩展

CompatibleCompare 是 (Key, CompatibleKey) 上的二元谓词，
CompatibleCompare 是 (CompatibleKey, Key) 上的二元谓词，
如果 c_comp(ck,k1)，则 !c_comp(k1,ck)，
如果 !c_comp(ck,k1) 且 !comp(k1,k2)，则 !c_comp(ck,k2)，
如果 !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。
复杂度： O(log(n))。

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

要求： (CompatibleKey, CompatibleCompare) 是 key_compare 的兼容扩展。
效果： 当且仅当存在键与 x 等效的元素时，返回 true。
复杂度： 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 的下界限定符

LowerBounder 是 Key 上的谓词，
如果 lower(k1) 且 !comp(k2,k1)，则 lower(k2)，

对于类型为 LowerBounder 的每个 lower、类型为 Compare 的 comp 以及类型为 Key 的 k1、k2。类似地，上界限定符是类型 UpperBounder，使得

UpperBounder 是 Key 上的谓词，
如果 upper(k1) 且 !comp(k1,k2)，则 upper(k2)，

对于类型为 UpperBounder 的每个 upper、类型为 Compare 的 comp 以及类型为 Key 的 k1、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，反之亦然。

索引参考

Boost.MultiIndex 参考

排名索引

修订于 2022 年 2 月 5 日

Boost.MultiIndex 有序索引参考

目录

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

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

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

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