Class template skew_heap . Boost , The Boost C++ Libraries BoostBook Documentation Subset , Reference

Class template skew_heap

boost::heap::skew_heap — skew heap

Synopsis

// In header: <boost/heap/skew_heap.hpp>
template<typename T, class... Options> 
class skew_heap {
public:
  // types
  typedef T                                                                                   value_type;      
  typedef implementation_defined::size_type                                                   size_type;       
  typedef implementation_defined::difference_type                                             difference_type; 
  typedef implementation_defined::value_compare                                               value_compare;   
  typedef implementation_defined::allocator_type                                              allocator_type;  
  typedef implementation_defined::reference                                                   reference;       
  typedef implementation_defined::const_reference                                             const_reference; 
  typedef implementation_defined::pointer                                                     pointer;         
  typedef implementation_defined::const_pointer                                               const_pointer;   
  typedef implementation_defined::iterator                                                    iterator;        
  typedef implementation_defined::const_iterator                                              const_iterator;  
  typedef implementation_defined::ordered_iterator                                            ordered_iterator;
  typedef mpl::if_c< is_mutable, typename implementation_defined::handle_type, void * >::type handle_type;     
  // member classes/structs/unions
  struct implementation_defined {
    // types
    typedef T                               value_type;         
    typedef base_maker::compare_argument    value_compare;      
    typedef base_maker::allocator_type      allocator_type;     
    typedef base_maker::node_type           node;               
    typedef allocator_type::pointer         node_pointer;       
    typedef allocator_type::const_pointer   const_node_pointer; 
    typedef unspecified                     value_extractor;    
    typedef boost::array< node_pointer, 2 > child_list_type;    
    typedef child_list_type::iterator       child_list_iterator;
    typedef unspecified                     iterator;           
    typedef iterator                        const_iterator;     
    typedef unspecified                     ordered_iterator;   
    typedef unspecified                     reference;          
    typedef unspecified                     handle_type;        
  };
  // construct/copy/destruct
  explicit skew_heap(value_compare const & = value_compare());
  skew_heap(skew_heap const &);
  skew_heap(skew_heap &&);
  skew_heap & operator=(skew_heap const &);
  skew_heap & operator=(skew_heap &&);
  ~skew_heap(void);
  // public member functions
  mpl::if_c< is_mutable, handle_type, void >::type push(value_type const &);
  template<typename... Args> 
    mpl::if_c< is_mutable, handle_type, void >::type emplace(Args &&...);
  bool empty(void) const;
  size_type size(void) const;
  size_type max_size(void) const;
  void clear(void);
  allocator_type get_allocator(void) const;
  void swap(skew_heap &);
  const_reference top(void) const;
  void pop(void);
  iterator begin(void) const;
  iterator end(void) const;
  ordered_iterator ordered_begin(void) const;
  ordered_iterator ordered_end(void) const;
  void merge(skew_heap &);
  value_compare const & value_comp(void) const;
  template<typename HeapType> bool operator<(HeapType const &) const;
  template<typename HeapType> bool operator>(HeapType const &) const;
  template<typename HeapType> bool operator>=(HeapType const &) const;
  template<typename HeapType> bool operator<=(HeapType const &) const;
  template<typename HeapType> bool operator==(HeapType const &) const;
  template<typename HeapType> bool operator!=(HeapType const &) const;
  void erase(handle_type);
  void update(handle_type, const_reference);
  void update(handle_type);
  void increase(handle_type, const_reference);
  void increase(handle_type);
  void decrease(handle_type, const_reference);
  void decrease(handle_type);
  // public static functions
  static handle_type s_handle_from_iterator(iterator const &);
  // public data members
  static const bool constant_time_size;
  static const bool has_ordered_iterators;
  static const bool is_mergable;
  static const bool is_stable;
  static const bool has_reserve;
  static const bool is_mutable;
};

Description

Шаблонный параметр T - это тип, которым должен управлять контейнер. Пользователь может указать дополнительные опции и, если опции не предусмотрены, используются опции по умолчанию.

Контейнер поддерживает следующие варианты:

<boost::heap::compare<>>, по умолчанию<compare<std::less<T>>>
<boost::heap::stable<>>, по умолчанию<stable<false>>
<boost::heap::stability_counter_type<>>, по умолчанию<stability_counter_type<boost::uintmax_t>>
<boost::heap::allocator<>>, по умолчанию<allocator<std::allocator<T>>>
<boost::heap::constant_time_size<>><constant_time_size<true>>[<constant_time_size<true>>]
<boost::heap::store_parent_pointer<>>,<store_parent_pointer<true>><store_parent_pointer<true>>. Поддержание родительского указателя добавляет некоторые расходы на обслуживание и размер, но повторение кучи более эффективно.
<boost::heap::mutable<>>, по умолчанию<mutable<false>>
.

`skew_heap` public types

typedefimplementation_defined::iteratoriterator;
Примечание:Итератор не пересекает очередь приоритетов в порядке приоритетов.

`skew_heap` public construct/copy/destruct

<
```
explicitskew_heap(value_compareconst&cmp=value_compare());
```
>
Эффекты:строит пустую очередь приоритета.
Сложность:Постоянство.
<
```
skew_heap(skew_heapconst&rhs);
```
>
Эффекты:копирование-конструирование приоритетной очереди из rhs.
Сложность:Линейный.
<
```
skew_heap(skew_heap&&rhs);
```
>
Эффекты:Конструктор движений в стиле C++11.
Сложность:Постоянство.
Примечание:Доступно только при наличии BOOST_NO_CXX11_RVALUE_REFERENCES Не определено
.
<
```
skew_heap&operator=(skew_heapconst&rhs);
```
>
Эффекты:Назначает приоритетную очередь из rhs.
Сложность:Линейная.
```
skew_heap&operator=(skew_heap&&rhs);
```
Эффекты:Задание на перемещение в стиле C++11.
Сложность:Постоянная.
Примечание:Доступно только при наличии BOOST_NO_CXX11_RVALUE_REFERENCES Не определено
<
```
~skew_heap(void);
```
>

`skew_heap` public member functions

<
```
mpl::if_c<is_mutable,handle_type,void>::typepush(value_typeconst&v);
```
>
Эффекты:Добавляет новый элемент в очередь приоритетов.
Сложность:Логарифмический (амортизированный).
<
```
template<typename...Args>
 mpl::if_c<is_mutable,handle_type,void>::typeemplace(Args&&...args);
```
>
Эффекты:Добавляет новый элемент в очередь приоритетов. Элемент непосредственно построен на месте.
Сложность:Логарифмическая (амортизированная).
```
boolempty(void)const;
```
Эффекты:Возвращается верно, если очередь приоритета не содержит элементов.
Сложность:Постоянная.
<
```
size_typesize(void)const;
```
>
Эффекты:Возвращает количество элементов, содержащихся в очереди приоритетов.
Сложность:Константа, если конфигурируется с константой_time_size, иначе линейная.
<
```
size_typemax_size(void)const;
```
>
Эффекты:Возвращает максимальное количество элементов, которые может содержать очередь приоритета.
Сложность:Постоянство.
<
```
voidclear(void);
```
>
Эффекты:Удаляет все элементы из очереди приоритетов.
Сложность:Линейная.
```
allocator_typeget_allocator(void)const;
```
Эффекты:Возвращается распределитель.
Сложность:Постоянная.
```
voidswap(skew_heap&rhs);
```
Эффекты:Замена двух очередей приоритетов.
Сложность:Постоянство.
<
```
const_referencetop(void)const;
```
>
Эффекты:Возвращает ссылку на максимальный элемент.
Сложность:Константа.
```
voidpop(void);
```
Эффекты:Удалите верхний элемент из очереди приоритета.
Сложность:Логарифмическая (амортизированная).
```
iteratorbegin(void)const;
```
Эффекты:Возвращает итератор к первому элементу, содержащемуся в очереди приоритета.
Сложность:Постоянство.
<
```
iteratorend(void)const;
```
>
Эффекты:Возвращает итератор в конец очереди приоритетов.
Сложность:Констант.
```
ordered_iteratorordered_begin(void)const;
```
Эффекты:Возвращает упорядоченный итератор к первому элементу, содержащемуся в очереди приоритета.
Примечание:Заказные итераторы проходят приоритетную очередь в кучном порядке.
<
```
ordered_iteratorordered_end(void)const;
```
>
Эффекты:Возвращает заказанный итератор к первому элементу, содержащемуся в очереди приоритетов.
Примечание:Заказанные итераторы проходят приоритетную очередь в кучном порядке.
```
voidmerge(skew_heap&rhs);
```
Эффекты:Слить все элементы из rhs в это
Сложность:Логарифмический (амортизированный).
<
```
value_compareconst&value_comp(void)const;
```
>
Эффект:Возвращает значение_сравните объект, используемый в очереди приоритетов
```
template<typenameHeapType>booloperator<(HeapTypeconst&rhs)const;
```
Возврат:Элементное сравнение кучных структур данных
Требование:value_compareобъект обеих груд должен совпадать.
<
```
template<typenameHeapType>booloperator>(HeapTypeconst&rhs)const;
```
>
Возвращение:Элементное сравнение кучных структур данных
Требование:<value_compare>объект обеих груд должен совпадать.
```
template<typenameHeapType>booloperator>=(HeapTypeconst&rhs)const;
```
Возврат:Элементное сравнение кучных структур данных
Требование:value_compareобъект обеих груд должен совпадать.
<
```
template<typenameHeapType>booloperator<=(HeapTypeconst&rhs)const;
```
>
Возврат:Элементное сравнение кучных структур данных
Требование:<value_compare>объект обеих кучи должен совпадать.
<
```
template<typenameHeapType>booloperator==(HeapTypeconst&rhs)const;
```
>Эквивалентное сравнениеВозвращение:Правда, если обе кучные структуры данных эквивалентны.
Требование:<value_compare>объект обеих кучи должен совпадать.
```
template<typenameHeapType>booloperator!=(HeapTypeconst&rhs)const;
```
Эквивалентное сравнениеВозврат:Правда, если обе кучи структур данных не эквивалентны.
Требование:value_compareобъект обеих груд должен совпадать.
<
```
voiderase(handle_typeobject);
```
>
Эффекты:Удалите элемент, обработанный<handle>из<priority_queue>.
Сложность:Логарифмическая (амортизированная).
```
voidupdate(handle_typehandle,const_referencev);
```
Эффекты:Назначаетvэлемент, обрабатываемыйhandle& обновляет очередь приоритета.
Сложность:Логарифмический (амортизированный).
```
voidupdate(handle_typehandle);
```
Эффекты:Обновляет кучу после того, как элемент, обработанныйhandle, был изменен.
Сложность:Логарифмический (амортизированный).
Примечание:Если это не называется, после обновления ручки поведение структуры данных не определено!
```
voidincrease(handle_typehandle,const_referencev);
```
Эффекты:Назначаетvэлемент, обрабатываемыйhandle& обновляет очередь приоритета.
Сложность:Логарифмический (амортизированный).
Примечание:Ожидается, что новое значение будет больше нынешнего
.
<
```
voidincrease(handle_typehandle);
```
>
Эффекты:Обновляет кучу после того, как элемент, обработанный<handle>, был изменен.
Сложность:Логарифмическая (амортизированная).
Примечание:Если это не называется, после обновления ручки поведение структуры данных не определено!
```
voiddecrease(handle_typehandle,const_referencev);
```
Эффекты:Назначаетvэлемент, обрабатываемыйhandle& обновляет очередь приоритетов.
Сложность:Логарифмический (амортизированный).
Примечание:Ожидается, что новое значение будет меньше текущего
.
<
```
voiddecrease(handle_typehandle);
```
>
Эффекты:Обновляет кучу после того, как элемент, обработанный<handle>, был изменен.
Сложность:Логарифмическая (амортизированная).
Примечание:Ожидается, что новая стоимость будет меньше текущей. Если это не называется, после обновления ручки поведение структуры данных не определено!

`skew_heap` public static functions

```
statichandle_types_handle_from_iterator(iteratorconst&it);
```
Эффекты:Отбрасывает итератор на ручку узла.
Сложность:Константа.
Требование:структура данных должна быть сконфигурирована как изменяемая

Статья Class template skew_heap раздела The Boost C++ Libraries BoostBook Documentation Subset Reference может быть полезна для разработчиков на c++ и boost.

Class template skew_heap

Boost , The Boost C++ Libraries BoostBook Documentation Subset , Reference

Boost C++ Libraries

Class template skew_heap

Synopsis

Description

skew_heap public types

skew_heap public construct/copy/destruct

skew_heap public member functions

skew_heap public static functions

`skew_heap` public types

`skew_heap` public construct/copy/destruct

`skew_heap` public member functions

`skew_heap` public static functions