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

Class template circular_list_algorithms

boost::intrusive::circular_list_algorithms

Synopsis

// In header: <boost/intrusive/circular_list_algorithms.hpp>
template<typename NodeTraits> 
class circular_list_algorithms {
public:
  // types
  typedef NodeTraits::node           node;          
  typedef NodeTraits::node_ptr       node_ptr;      
  typedef NodeTraits::const_node_ptr const_node_ptr;
  typedef NodeTraits                 node_traits;   
  // member classes/structs/unions
  struct stable_partition_info {
    // public data members
    std::size_t num_1st_partition;
    std::size_t num_2nd_partition;
    node_ptr beg_2st_partition;
  };
  // public static functions
  static void init(const node_ptr &);
  static bool inited(const const_node_ptr &);
  static void init_header(const node_ptr &);
  static bool unique(const const_node_ptr &);
  static std::size_t count(const const_node_ptr &);
  static node_ptr unlink(const node_ptr &);
  static void unlink(const node_ptr &, const node_ptr &);
  static void link_before(const node_ptr &, const node_ptr &);
  static void link_after(const node_ptr &, const node_ptr &);
  static void swap_nodes(const node_ptr &, const node_ptr &);
  static void transfer(const node_ptr &, const node_ptr &, const node_ptr &);
  static void transfer(const node_ptr &, const node_ptr &);
  static void reverse(const node_ptr &);
  static void move_backwards(const node_ptr &, std::size_t);
  static void move_forward(const node_ptr &, std::size_t);
  static std::size_t distance(const const_node_ptr &, const const_node_ptr &);
  template<typename Pred> 
    static void stable_partition(node_ptr, const node_ptr &, Pred, 
                                 stable_partition_info &);
  // private static functions
  static void swap_prev(const node_ptr &, const node_ptr &);
  static void swap_next(const node_ptr &, const node_ptr &);
};

Description

circular_list_algorithmsпредоставляет основные алгоритмы для манипулирования узлами, образующими круговой двойной список. Пустой круговой список формируется узлом, указатели которого указывают на себя.

circular_list_algorithmsсконфигурирован с классом NodeTraits, который инкапсулирует информацию о узле, которым нужно манипулировать. NodeTraits должен поддерживать следующий интерфейс:

Типоразмеры:

<node>Тип узла, который формирует круговой список

<node_ptr>: Указатель на узел

<const_node_ptr>: Указатель на узел const

Статические функции:

<static node_ptr get_previous(const_node_ptr n);>

<static void set_previous(node_ptr n, node_ptr prev);>

<static node_ptr get_next(const_node_ptr n);>

<static void set_next(node_ptr n, node_ptr next);>

`circular_list_algorithms` public static functions

<
```
staticvoidinit(constnode_ptr&this_node);
```
>
Эффекты: Конструирует неиспользуемый элемент списка, так что inited(this_node) == true
Сложность: Constant
Бросает: Ничего.
<
```
staticboolinited(constconst_node_ptr&this_node);
```
>
Эффекты: Верно, что «this_node» находится в неиспользуемом состоянии, как если бы он был инициализирован функцией «init».
Сложность: Постоянная
Бросает: Ничего.
<
```
staticvoidinit_header(constnode_ptr&this_node);
```
>
Эффекты: Конструирует пустой список, делая этот узел единственным узлом кругового списка:<NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node) == this_node>.
Сложность: Константа
Бросает: Ничего.
<
```
staticboolunique(constconst_node_ptr&this_node);
```
>
Требуется: Этот узел должен быть в круговом списке или быть пустым круговым списком.
Эффекты: Верно то, что «это_узел» является единственным узлом кругового списка:<return NodeTraits::get_next(this_node) == this_node>
Сложность: Постоянная
Бросает: Ничего.
<
```
staticstd::size_tcount(constconst_node_ptr&this_node);
```
>
Требуется: Этот узел должен быть в круговом списке или быть пустым круговым списком.
Эффекты: Возвращает количество узлов в круговой список. Если круговой список пуст, возвращает 1.
Сложность: Линейный
Бросает: Ничего.
<
```
staticnode_ptrunlink(constnode_ptr&this_node);
```
>
Требуется: Этот узел должен быть в круговом списке или быть пустым круговым списком.
Эффекты: Развязывает узел из кругового списка.
Сложность: Постоянная
Бросает: Ничего.
<
```
staticvoidunlink(constnode_ptr&b,constnode_ptr&e);
```
>
Требуется: b и e должны быть узлами одного и того же кругового списка или пустого диапазона.
Эффекты: Отсоединяют узел [b, e] от кругового списка.
Сложность: Постоянная
Броски: Ничего.
<
```
staticvoidlink_before(constnode_ptr&nxt_node,constnode_ptr&this_node);
```
>
Требуется: nxt_node должен быть узлом кругового списка.
Эффекты: Связывает этот_узл перед nxt_узлом в круговом списке.
Сложность: Константа
Бросает: Ничего.
<
```
staticvoidlink_after(constnode_ptr&prev_node,constnode_ptr&this_node);
```
>
Требуется: prev_node должен быть узлом кругового списка.
Эффекты: Связывает этот_узл после prev_узла в круговом списке.
Сложность: Постоянная
Бросает: Ничего.
<
```
staticvoidswap_nodes(constnode_ptr&this_node,
                      constnode_ptr&other_node);
```
>
Требуется: Этот_узл и другой_узл должны быть узлами, вставленными в круглые списки или пустыми круглыми списками.
Эффекты: Изменяет положение узлов: этот_узл вставляется в положение других_узлов во втором круговом списке, а другой_узл вставляется в положение этого_узла в первом круговом списке.
Сложность: Константа
Бросает: Ничего.
<
```
staticvoidtransfer(constnode_ptr&p,constnode_ptr&b,
                    constnode_ptr&e);
```
>
Требуется: b и e должны быть узлами одного и того же кругового списка или пустого диапазона. и p должен быть узлом другого кругового списка или не может быть итератором вЭффекты: Удаляет узлы из [b, e] диапазона от их кругового списка и вставляет их перед p в круговой список p.
Сложность: Постоянная
Броски: Ничего.
<
```
staticvoidtransfer(constnode_ptr&p,constnode_ptr&i);
```
>
Требуется: i должен быть узлом кругового списка, а p должен быть узлом другого кругового списка.
Эффекты: Удаляет узел i из своего кругового списка и вставляет его перед p в круговой список p. Если p == i или p == NodeTraits::get_next(i), эта функция является нулевой операцией.
Сложность: Постоянная
Броски: Ничего.
<
```
staticvoidreverse(constnode_ptr&p);
```
>
Эффекты: Обратный порядок элементов в списке.
Бросок: Ничего.
Сложность: Эта функция является линейным временем.
<
```
staticvoidmove_backwards(constnode_ptr&p,std::size_tn);
```
>
Эффекты: Переносит узел p n позиций в конец списка.
Бросает: Ничего.
Сложность: Линейные по количеству перемещаемых позиций.
<
```
staticvoidmove_forward(constnode_ptr&p,std::size_tn);
```
>
Эффекты: Перемещает узел p n позиций в начало списка.
Бросок: Ничего.
Сложность: Линейные по количеству перемещаемых позиций.
<
```
staticstd::size_t
distance(constconst_node_ptr&f,constconst_node_ptr&l);
```
>
Требуется: f и l должны быть в круговом списке.
Эффекты: Возвращает число узлов в диапазоне [f, l]
Сложность: Линейный
Бросает: Ничего.

template<typenamePred>
 staticvoidstable_partition(node_ptrbeg,constnode_ptr&end,Predpred,
                              stable_partition_info&info);

`circular_list_algorithms` private static functions

staticvoidswap_prev(constnode_ptr&this_node,constnode_ptr&other_node);

staticvoidswap_next(constnode_ptr&this_node,constnode_ptr&other_node);

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

Class template circular_list_algorithms

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

Boost C++ Libraries

Class template circular_list_algorithms

Synopsis

Description

circular_list_algorithms public static functions

circular_list_algorithms private static functions

`circular_list_algorithms` public static functions

`circular_list_algorithms` private static functions