Boost.MultiIndex Documentation - Ranked indices reference

Boost , , Boost.MultiIndex Documentation - Reference

Boost.MultiIndex Ranked indices reference

Ordered indices

Boost.MultiIndex reference

Hashed indices

Contents

• Заголовок"boost/multi_index/ranked_index_fwd.hpp"синопсис
• Заголовок"boost/multi_index/ranked_index.hpp"Синопсис
  • Указатели индексовranked_uniqueиranked_non_unique
  • Ранжированные индексы
    • Сложная подпись
    • Типы обоснований
    • Ранговые операции
    • Сериализация

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 предоставляет форвардные декларации для указателей индексов ranked_unique и ranked_non_unique и связанных с ними классов ranked index.

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

Эти указатели индексов позволяют вставлять рейтинговые индексы без и с учетом дублирующих элементов, соответственно. Синтаксис ranked_unique и ranked_non_unique совпадают, поэтому мы описываем их сгруппированным образом. ranked_unique и ranked_non_unique могут быть представлены в двух различных формах, в зависимости от того, предоставляется ли список тегов для индекса:

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

При наличии TagList должен представлять собой инстанциацию шаблона класса tag. Аргументы шаблона используются соответствующей реализацией индекса, см. раздел ссылки ранжированных индексов для дальнейших объяснений их приемлемых значений типа.

Ranked indices

Ранжированные индексы представляют собой вариацию упорядоченных индексов, обеспечивающую дополнительные возможности для расчета и доступа по рангу; ранг элемента - расстояние до него от начала индекса. Помимо этого расширения ранжированные индексы воспроизводят публичный интерфейс упорядоченных индексов с разницей, сложностью, что удаление выполняется в логарифмическом, а не в постоянном времени. Кроме того, ожидается, что время выполнения и потребление памяти будут хуже из-за внутренней бухгалтерской отчетности, необходимой для поддержания информации, связанной с рангом. Как и упорядоченные индексы, ранжированные индексы могут быть уникальными (не допускаются дублирующие элементы) или неуникальными: любая версия связана с другим указателем индекса, но интерфейс обоих типов индексов одинаков.

Ниже мы описываем только дополнительные операции, предоставляемые ранжированными индексами: для остальных ссылаемся на документацию для упорядоченных индексов, имея в виду случайные различия в сложности.

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

Мы следуем терминологии, описанной в разделе сложность подписи . Сигнатура сложности ранжированных индексов:

• Приступ:c(n)=n*log(n),
• i(n)=log(n),
h(n)=log(n) в противном случае,
• d(n)=log(n),
• r(n)=1[править]
m(n)=1 (постоянно), если положение элемента не изменяется, m(n)=log(n) в противном случае.

Копирование:c(n)=n*log(n),

вставка:i(n)=log(n),

h(n)=1(постоянно), если элемент подсказки находится сразу после точки вставки,h(n)=log(n)в противном случае,

d(n)=log(n),

замена:r(n)=1(постоянная), если положение элемента не изменяется,r(n)=log(n)в противном случае,

m(n)=1(постоянно), если положение элемента не изменяется,m(n)=log(n)в противном случае.

[ORIG_END] -->

Эти гарантии сложности такие же, как у упорядоченных индексов. За исключением удаления, которое является log(n) здесь и амортизированной постоянной там.

Instantiation types

Упорядоченные индексы инстанцируются внутри multi_index_container и указываются посредством indexed_by с указателями индексов ranked_unique и ranked_non_unique. Обоснования зависят от следующих типов:

• отmulti_index_container,
• multi_index_container[multi_index_container]
• [] [] [tag<>]] [[tag<>]] [[tag<>]]] [[[]]]] [[[[]]]]] [[[[]]]] [[[[]]]]]] [[[[]]]]] [[[[[]]]]]] [[[[[]]]]]] [[[[[]]]]]]] [[[[[]]]]] [[[[[]]]]]][[[[[[]]]]]][[[[[[]]]]]][[[[]]]]]]][[[[[[]]]]]]][[[[[[]]]]]][[[[[[]]]]]]][[[[[]]]]]]][[[[]]]]]][[[[[[]]]]]]][[[[[[]]]]]]]
• , [скрыто], [скрыто], [скрыто], [скрыто]
• СравнитеЩедрость тела.

На эти типы распространяются те же требования, что и на упорядоченные индексы .Valueизmulti_index_container,

Allocatorизmulti_index_container,

TagListиз указателя индекса (если предусмотрено, в противном случаеtag<>предполагается),

KeyFromValueиз указателя индекса,

Compareиз указателя индекса.

These types are subject to the same requirements as specified for ordered indices. [ORIG_END] -->

Rank operations

ранг итератора it заданного контейнера c (и, в более широком смысле, элемента, на который он указывает, если итератор является сносным) является std::distance(c.begin(),it).

См. документацию упорядоченных индексов для объяснения понятий совместимое расширение, совместимый ключ, нижняя граница и верхняя граница, о которых говорится ниже.

iterator nth(size_type n)const;

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

size_type rank(iterator position)const;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

template<typename LowerBounder,typename UpperBounder>
std::pair<size_type,size_type> range_rank(
  LowerBounder lower,UpperBounder upper)const;

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

Предпосылки и постусловия, связанные с сериализацией multi_index_containers с ранжированными индексами, точно такие же, как и у ordered index.

---

Упорядоченные индексы

Boost.MultiIndex ссылка

<8 Индексы хэширования

<23

Пересмотрено 4 мая 2015 года

© Copyright 2003-2015 Joaquín M López Muñoz. Распространяется под лицензией Boost Software License, версия 1.0. (См. сопроводительный файл) LICENSE_1_0.txt или копировать на http://www.boost.org/LICENSE_1_0.txt

Статья Boost.MultiIndex Documentation - Ranked indices reference раздела Boost.MultiIndex Documentation - Reference может быть полезна для разработчиков на c++ и boost.

Материалы статей собраны из открытых источников, владелец сайта не претендует на авторство. Там где авторство установить не удалось, материал подаётся без имени автора. В случае если Вы считаете, что Ваши права нарушены, пожалуйста, свяжитесь с владельцем сайта.

---

:: Главная :: Boost.MultiIndex Documentation - Reference ::

---

реклама

---