Boost.MultiIndex Ranked indices reference

Ordered indices

Boost.MultiIndex reference

Hashed indices

Contents

• Header "boost/multi_index/ranked_index_fwd.hpp" synopsis
• Header "boost/multi_index/ranked_index.hpp" synopsis
  • Index specifiers ranked_unique and ranked_non_unique
  • Ranked indices
    • Complexity signature
    • Instantiation types
    • Nested types
    • Set operations
    • Rank operations
    • Serialization

Header "boost/multi_index/ranked_index_fwd.hpp" synopsis

namespace boost{

namespace multi_index{

// index specifiers ranked_unique and ranked_non_unique

template<consult ranked_unique reference for arguments>
struct ranked_unique;
template<consult ranked_non_unique reference for arguments>
struct ranked_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

ranked_index_fwd.hpp provides forward declarations for index specifiers ranked_unique and ranked_non_unique and their associated ranked index classes.

Header "boost/multi_index/ranked_index.hpp" synopsis

#include <initializer_list>

namespace boost{

namespace multi_index{

// index specifiers ranked_unique and ranked_non_unique

template<consult ranked_unique reference for arguments>
struct ranked_unique;
template<consult ranked_non_unique reference for arguments>
struct ranked_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

Index specifiers ranked_unique and ranked_non_unique

These index specifiers allow for insertion of ranked indices without and with allowance of duplicate elements, respectively. The syntax of ranked_unique and ranked_non_unique coincide, thus we describe them in a grouped manner. ranked_unique and ranked_non_unique can be instantiated in two different forms, according to whether a tag list for the index is provided or not:

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

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

If provided, TagList must be an instantiation of the class template tag. The template arguments are used by the corresponding index implementation, refer to the ranked indices reference section for further explanations on their acceptable type values.

Ranked indices

Ranked indices are a variation of ordered indices providing additional capabilities for calculation of and access by rank; the rank of an element is the distance to it from the beginning of the index. Besides this extension, ranked indices replicate the public interface of ordered indices with the difference, complexity-wise, that hinted insertion and deletion are done in logarithmic rather than constant time. Also, execution times and memory consumption are expected to be poorer due to the internal bookkeeping needed to maintain rank-related information (an exception being count operations, which are actually faster). As with ordered indices, ranked indices can be unique (no duplicate elements are allowed) or non-unique: either version is associated to a different index specifier, but the interface of both index types is the same.

In what follows, we only describe the extra operations provided by ranked indices or those operations with improved performance: for the rest refer to the documentation for ordered indices, bearing in mind the occasional differences in complexity.

namespace boost{

namespace multi_index{

implementation defined unbounded; // see range_rank()

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;

  // rank operations:

  iterator  nth(size_type n)const;
  size_type rank(iterator position)const;

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

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

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

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

  template<typename LowerBounder,typename UpperBounder>
  std::pair<size_type,size_type>
  range_rank(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

Complexity signature

We follow the terminology described in the complexity signature section. The complexity signature of ranked indices is:

• copying: c(n)=n*log(n),
• insertion: i(n)=log(n),
• hinted insertion: h(n)=log(n),
• deletion: d(n)=log(n) ,
• replacement: r(n)=1 (constant) if the element position does not change, r(n)=log(n) otherwise,
• modifying: m(n)=1 (constant) if the element position does not change, m(n)=log(n) otherwise.

These complexity guarantees are the same as those of ordered indices except for hinted insertion and deletion, which are log(n) here and amortized constant there.

Instantiation types

Ranked indices are instantiated internally to multi_index_container and specified by means of indexed_by with index specifiers ranked_unique and ranked_non_unique. Instantiations are dependent on the following types:

• Value from multi_index_container,
• Allocator from multi_index_container,
• TagList from the index specifier (if provided, otherwise tag<> is assumed),
• KeyFromValue from the index specifier,
• Compare from the index specifier.

Nested types

These types depend only on node_type and the position of the index in the multi_index_container.

Set operations

See the documentation of ordered indices for an explanation of the notions of compatible extension and compatible key, which are referred to below.

Requires: CompatibleKey is a compatible key of key_compare.
Effects: Returns the number of elements with key equivalent to x.
Complexity: O(log(n)).

Requires: (CompatibleKey, CompatibleCompare) is a compatible extension of key_compare.
Effects: Returns the number of elements with key equivalent to x.
Complexity: O(log(n)).

Rank operations

The rank of an iterator it of a given container c (and, by extension, of the element it points to if the iterator is dereferenceable) is std::distance(c.begin(),it).

See the documentation of ordered indices for an explanation of the notions of compatible extension, compatible key, lower bounder and upper bounder, which are referred to below.

Effects: Returns an iterator with rank n, or end() if n>=size().
Complexity: O(log(n)).

Requires: position is a valid iterator of the index.
Effects: Returns the rank of position.
Complexity: O(log(n)).

Requires: CompatibleKey is a compatible key of key_compare.
Effects: Equivalent to rank(find(k)).
Complexity: O(log(n)).

Requires: (CompatibleKey, CompatibleCompare) is a compatible extension of key_compare.
Effects: Equivalent to rank(find(x,comp)).
Complexity: O(log(n)).

Requires: CompatibleKey is a compatible key of key_compare.
Effects: Equivalent to rank(lower_bound(x)).
Complexity: O(log(n)).

Requires: (CompatibleKey, CompatibleCompare) is a compatible extension of key_compare.
Effects: Equivalent to rank(lower_bound(x,comp)).
Complexity: O(log(n)).

Requires: CompatibleKey is a compatible key of key_compare.
Effects: Equivalent to rank(upper_bound(x)).
Complexity: O(log(n)).

Requires: (CompatibleKey, CompatibleCompare) is a compatible extension of key_compare.
Effects: Equivalent to rank(upper_bound(x,comp)).
Complexity: O(log(n)).

Requires: CompatibleKey is a compatible key of key_compare.
Effects: Equivalent to make_pair(lower_bound_rank(x),upper_bound_rank(x)).
Complexity: O(log(n)).

Requires: (CompatibleKey, CompatibleCompare) is a compatible extension of key_compare.
Effects: Equivalent to make_pair(lower_bound_rank(x,comp),upper_bound_rank(x,comp)).
Complexity: O(log(n)).

Requires: LowerBounder and UpperBounder are a lower and upper bounder of key_compare, respectively.
Effects: Equivalent to

auto p=range(lower,upper);
return make_pair(rank(p.first),rank(p.second));

Complexity: O(log(n)).
Variants: In place of lower or upper (or both), the singular value boost::multi_index::unbounded can be provided. This acts as a predicate which all values of type key_type satisfy.

Serialization

The prerequisites and postconditions associated to serialization of multi_index_containers with ranked indices are exactly the same as those of ordered indices.

Ordered indices

Boost.MultiIndex reference

Hashed indices

Revised February 5th 2022

© Copyright 2003-2022 Joaquín M López Muñoz. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)