intrusive list

介入式容器的 元素的生命周期由元素自身管理而不是由容器管理。 folly 提供了IntrusiveList和CountedLinklist,是boost instrusive_list的一些alias,能覆盖大部分使用场景。

#include <folly/init/Init.h>
#include <folly/ObserverContainer.h>
#include <folly/IntrusiveList.h>
#include <iostream>
#include <gtest/gtest.h>

class Node
{
 public:
  int data;
  folly::IntrusiveListHook hook_;
};
TEST(intrusive, automode)
{
  using List=folly::IntrusiveList<Node,&Node::hook_>;//元素的析构函数使元素本身从list中自动unlink
  Node a {3};
  Node b {5};
  List l ;
  l.push_back(a);
  l.push_back(b);
  for (auto&& i : l)
  {
    std::cout<<i.data<<std::endl;
  }
  std::cout<<l.size()<<std::endl;//O(n) time
}

class SafeNode
{
 public:
  int data;
  folly::SafeIntrusiveListHook hook_;
};
TEST(intrusive, countLinkList)
{
  using List=folly::CountedIntrusiveList<SafeNode,&SafeNode::hook_>;
  SafeNode a {3};
  SafeNode b {5};
  List l ;
  l.push_back(a);
  l.push_back(b);
  for (auto&& i : l)
  {
    std::cout<<i.data<<std::endl;
  }
  {
    SafeNode c {5};
    l.push_back(c);
    // ...
    l.pop_back();// should be called to prevent dangling reference,NOT auto unlink
  }
  std::cout<<l.size()<<std::endl;//constant time
  l.erase(l.iterator_to(b));//erase node b
  for (auto&& i : l)
  {
    std::cout<<i.data<<std::endl;
  }
  std::cout<<l.size()<<std::endl;//constant time
  l.pop_front();
}
Posted 2023-05-16