Intrusive singly linked list: slist . Boost , The Boost C++ Libraries BoostBook Documentation Subset , Chapter 17. Boost.Intrusive

Intrusive singly linked list: slist

slist hooks
slist container
Example

<slist>— самый простой интрузивный контейнерBoost.Intrusive: Единый связанный список. Память, которую он накладывает, составляет 1 указатель на узел. Размер пустого, непостоянного времени<slist>равен размеру 1 указателя. Тем не менее, этот легкий объем памяти имеет недостатки: многие операции имеют линейную временную сложность, даже те, которые обычно являются постоянным временем, например<swap>.<slist>только передовые итераторы.

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

slist hooks

Как и остальныеBoost.Intrusiveконтейнеры,<slist>имеет два типа крючков:

template <class ...Options>
class slist_base_hook;

<slist_base_hook>: класс пользователя происходит от<slist_base_hook>, чтобы сделать его<slist>-совместимым.

template <class ...Options>
class slist_member_hook;

<slist_member_hook>: класс пользователя содержит публичный<slist_member_hook>, чтобы сделать его<slist>-совместимым.

<slist_base_hook>и<slist_member_hook>получают те же варианты, описанные в разделеКак использовать Boost.Intrusive:

<tag<classTag>>(только для базовых крючков): Этот аргумент служит тегом, поэтому вы можете извлечь из более чем одного крючка списка. Дефолт:<tag<default_tag>>.
<link_mode<link_mode_type LinkMode>>: Связывающая политика. Дефолт:<link_mode<safe_link>>.
<void_pointer<classVoidPointer>>: Тип указателя, который должен использоваться внутри крючка и распространяться на контейнер. Дефолт:<void_pointer<void*>>.

slist container

template <class T, class ...Options>
class slist;

<slist>получает варианты, описанные в разделеКак использовать Boost.Intrusive

<base_hook<classHook>>/<member_hook<classT,classHook,HookT::*PtrToMember>>/<value_traits<classValueTraits>>: Чтобы указать тип крючка или характеристики значения, используемые для настройки контейнера. (Чтобы узнать о ценностных чертах, перейдите в разделКонтейнеры с пользовательскими стоимостными чертами.)
<constant_time_size<boolEnabled>>: Для активации операции постоянного времени<size()>. Дефолт:<constant_time_size<true>>
<size_type<boolEnabled>>: Указать тип, который будет использоваться для хранения размера контейнера. Дефолт:<size_type<std::size_t>>.

<slist>может получить дополнительные опции:

<linear<boolEnable>>: Единый связанный список реализуется как нулевой список вместо кругового списка. Это позволяет<O(1)>обменять, но теряет некоторые операции, такие как<container_from_end_iterator>.
<cache_last<boolEnable>>:<slist>также содержит указатель на последний элемент единственно связанного списка. Это позволяет<O(1)>своп,<splice_after(iterator, slist&)>и делает список предложений новых функций, как<push_back(reference)>и<back()>. По логике, размер пустого списка увеличивается в<sizeof(void_pointer)>, и кэшированный указатель последнего узла должен обновляться в каждой операции, и это может повлечь за собой небольшое влияние на производительность.

<auto_unlink>Крючки не используются, если используются<linear<true>>и/или<cache_last<true>>опции. Если используются<auto_unlink>крючки и указаны эти варианты, будет поднято статическое утверждение.

Example

Теперь рассмотрим небольшой пример с использованием обоих крючков:

#include <boost/intrusive/slist.hpp>
#include <vector>
using namespace boost::intrusive;
                  //This is a base hook
class MyClass : public slist_base_hook<>
{
   int int_;
   public:
   //This is a member hook
   slist_member_hook<> member_hook_;
   MyClass(int i)
      :  int_(i)
   {}
};
//Define an slist that will store MyClass using the public base hook
typedef slist<MyClass> BaseList;
//Define an slist that will store MyClass using the public member hook
typedef member_hook<MyClass, slist_member_hook<>, &MyClass::member_hook_> MemberOption;
typedef slist<MyClass, MemberOption> MemberList;
int main()
{
   typedef std::vector<MyClass>::iterator VectIt;
   typedef std::vector<MyClass>::reverse_iterator VectRit;
   //Create several MyClass objects, each one with a different value
   std::vector<MyClass> values;
   for(int i = 0; i < 100; ++i)  values.push_back(MyClass(i));
   BaseList baselist;
   MemberList memberlist;
   //Now insert them in the reverse order in the base hook list
   for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
      baselist.push_front(*it);
   //Now insert them in the same order as in vector in the member hook list
   for(BaseList::iterator it(baselist.begin()), itend(baselist.end())
      ; it != itend; ++it){
      memberlist.push_front(*it);
   }
   //Now test lists
   {
      BaseList::iterator bit(baselist.begin());
      MemberList::iterator mit(memberlist.begin());
      VectRit rit(values.rbegin()), ritend(values.rend());
      VectIt  it(values.begin()), itend(values.end());
      //Test the objects inserted in the base hook list
      for(; rit != ritend; ++rit, ++bit)
         if(&*bit != &*rit)   return 1;
      //Test the objects inserted in the member hook list
      for(; it != itend; ++it, ++mit)
         if(&*mit != &*it)    return 1;
   }
   return 0;
}

Статья Intrusive singly linked list: slist раздела The Boost C++ Libraries BoostBook Documentation Subset Chapter 17. Boost.Intrusive может быть полезна для разработчиков на c++ и boost.