My ForwardList Implemetation

ForwardList 实现

事先声明：本人并未参考STL实现，仅根据cppreferece的描述进行编写，且增加了我个人觉得方便的API，我是因为觉得std::forward_list<>不好用才打算写一个自己的

设计

首先，ForwardList是带哨兵（header）的单向不循环链表（循环对于单向没啥用），std::forward_list<>估计也是如此，因为有std::forward_list<>::before_begin()。

之所以带哨兵，原因数据结构也学过：简化操作，可以减少一些边界条件的判别

这里还有一个好处就是哨兵维护一些元数据（metadata）。

标准库为了遵循zero-overhead原则，没有维护总结点数，也没有维护header的前一节点（previous）。

你可以通过下面的代码验证：

std::forward_list<int> list;
static_assert(sizeof list == 8, "");

可是在很多情况下，这两个元数据很有作用，若要自己维护，显得多余，而且previous标准库并未暴露相关API，所以别想了。

这两个元数据的overhead也不过16byte（32位机则是8byte）

所以header有三个数据成员： next， previous， count

header作为特殊节点，并不维护值，而其它节点都维护值，也就是说有必要区别这两个节点，可以让它们继承共同基类，并将公共属性：next作为基类数据成员。

由于没有用到虚机制，所以这样做仍是zero-overhead的。

这样做的好处有：

• header省了（默认）值的开销（如果T不支持默认构造，这是灾难性的（ill-formed））
• 对于类模板（class template），由于共同基类没有涉及模板参数且链表的大部分算法都是不涉及值（源码可以看到），所以我们可以将算法从类模板ForwardList<>中分离出来，这样一来，就不用类模板针对每个模板实参生成不同的具体算法，而是共用一个分离的那个算法，一定程度上缓解了源码膨胀问题

这种设计技巧在红黑树中也有用到。

// include/forward_list/node_def.h
/**
 * Throught BaseLinkedNode to split the detail of algorithm
 * from class template(ForwardList<>)
 * @note In C++, "typedef struct XXX { } XXX;" is not necessary in fact.
 * @see src/forward_list/algorithm.cc
 */
typedef struct BaseLinkedNode {
  struct BaseLinkedNode* next = nullptr;
} BaseLinkedNode;

/**
 * Represents the plain node
 * which has value(related template parameter)
 */
template<typename T>
struct LinkedNode : BaseLinkedNode {
  T val;
};

/**
 * Represents the header sentinel.
 * Different from the plain node(LinkedNode<>), header doesn't maintains value domain,
 * it just maintains previous/next and count of elements.
 * @warning This is not STL-required, just useful for me.
 */
struct Header : BaseLinkedNode {
    BaseLinkedNode* prev = nullptr;
    size_t count = 0;
};

然后还有一个问题需要思考，header初始状态如何？

count和next不用想，关键是prev，

prev置为nullptr合适吗？不合适，因为当链表为空时调用insert_after(before_end(), 1)，那么就完蛋了，这时候我们希望的行为是插在header后面，所以prev应当指向header本身（链表为空时）

基础算法

我们需要关注的基础算法如下：

/** 
 * Because only the value of node is related with template parameter, 
 * we can use @c BaseLinkedNode to split the detail of algorithm to avoid every class template 
 * instantiation with implemetation itself.
 *
 * The push/insert_xxx() and extract_xxx() no need to consider the value of node
 */
void push_front(Header* header, BaseLinkedNode* new_node) noexcept;
void push_back(Header* header, BaseLinkedNode* new_node) noexcept;
void insert_after(Header* header, BaseLinkedNode* pos, BaseLinkedNode* new_node) noexcept;

BaseLinkedNode* extract_front(Header* header) noexcept;
BaseLinkedNode* extract_after(Header* header, BaseLinkedNode* pos) noexcept;
BaseLinkedNode* extract_after(Header* header, BaseLinkedNode* first, BaseLinkedNode* lsat) noexcept;

这些算法全是基于节点的，不涉及分配/释放/构造/析构这些操作，因为这些涉及值（即涉及模板实参），应由ForwardList处理

根据数据结构的知识，这些都是不难写出的，这里还是统一讲解下。

push_front

即所谓头插，需要注意的是当链表为空时，需要更新prev
验证链表是否为空，可以用该宏：

#define FORWARD_LIST_EMPTY (header->next == nullptr)

void push_front(Header* header, BaseLinkedNode* new_node) noexcept
{
  // Update header_->prev only when list is empty
  if (FORWARD_LIST_EMPTY) {
    assert(header->prev == header);
    header->prev = new_node;
  }
  
  new_node->next = header->next;
  header->next = new_node;
}

push_back

即尾插，考虑两种情况：

• 链表为空, 更新header->next
• 链表不为空， 更新header->prev->next
  之后更新header->prev即可

  void push_back(Header* header, BaseLinkedNode* new_node) noexcept
  {
    if (header->prev != header) {
      header->prev->next = new_node;
    }
    else {
      assert(header->prev == header);
      assert(FORWARD_LIST_EMPTY);
      header->next = new_node;
    }
  
    header->prev = new_node;
  }

  insert_after

  由于单向链表不像双向链表每个节点都有两个指针，所以在不知道要删除节点的前结点的情况下删除是$O(n)$的.

当pos为header->prev的时候，表现为尾插（push_back)，所以需要更新prev

void insert_after(Header* header, BaseLinkedNode* pos, BaseLinkedNode* new_node) noexcept
{
  // Push to back, update header_->prev
  // If pos == header, and FORWARD_LIST_EMPTY == true
  // pos == heaer->prev also equal to true
  if (pos == header->prev) {
    header->prev = new_node;
  }

  new_node->next = pos->next;
  pos->next = new_node;
}

extract_front

该函数是pop_front()的实现细节，extract_front()负责将第一节点从链表移除并返回该节点

BaseLinkedNode* extract_front(Header* header) noexcept
{
  assert(!FORWARD_LIST_EMPTY);

  auto ret = header->next;
  header->next = header->next->next;
  
  if (FORWARD_LIST_EMPTY) {
    header->prev = header;
  }
  
  // Reset returned node, to avoid construct loop in some cases
  ret->next = nullptr;

  return ret;
}

调用前提是链表非空，否则触发断言

如果移除后链表为空，需要更新prev

需要注意的一点是返回的节点必须是“干净”的，即置next为nullptr，避免因为原来的链接关系导致出现double free等莫名bug

extract_after

该函数是erase_after()的实现细节，将给定节点后的节点移除并返回

需要注意的是给定节点及其下一节点都不能是nullptr，以及给定节点的下一节点为header->prev的话，需要更新prev

BaseLinkedNode* extract_after(Header* header, BaseLinkedNode* pos) noexcept
{
  ZASSERT(pos != nullptr, "The position argument must not be end()");
  ZASSERT(!FORWARD_LIST_EMPTY, "ForwardList must be not empty");
  ZASSERT(pos->next != nullptr, "The next node of the position argument mustn't be nullptr");

  auto ret = pos->next;

  // If pos->next is last element, update it
  if (ret == header->prev) {
    // FIXME Need to update head->prev = nullptr when pos == header
    header->prev = pos;
  }

  pos->next = pos->next->next;

  ret->next = nullptr;
  return ret;

}

其中ZASSERT是如下宏：

#define ZASSERT(cond, msg) \
  assert((cond) && (msg))

extract_after(range)

范围版本的extract_after()负责移除(first, last)的节点，并返回这些节点的首节点，供erase_after()删除

一般其他容器的话是左闭右开，但因为单向链表的特性是做不到左闭的

显然，区间长度至少要为1，不然返回nullptr表示没有可删节点

如果last是nullptr，即ForwardList的end()的话，那么这个区间必然包含了header->prev，需要更新prev

BaseLinkedNode* extract_after(Header* header, BaseLinkedNode* first, BaseLinkedNode* last) noexcept
{
  // The length of the range must be 1 at least
  if (first->next != last) {
    BaseLinkedNode* old_next;

    // If last is the end iterator, indicates the header_->prev need to update
    if (last == nullptr) {
      header->prev = first;
    }

    auto first_next = first->next;
    first->next = last;

    return first_next;
  }

  return nullptr;
}

迭代器

ForwardList的迭代器本质上就是节点的location，由于单向链表的特性，所以这显然是forward iterator（单向前进迭代器）

单向迭代器需要满足的操作可见LegacyForwardIterator

template<typename T>
struct ForwardListIterator : std::iterator<std::forward_iterator_tag, T> {
  // type alias...

  ForwardListIterator(BaseNode* node=nullptr) 
   : node_{ node }
  {
  }

  Ref& operator*() noexcept { return extract()->val; }
  ConstRef operator*() const noexcept { return extract()->val; }
  Pointer operator->() noexcept { return &(extract()->val); }
  ConstPointer operator->() const noexcept { return &(extract()->val); }

  Self& operator++() noexcept
  {
    node_ = node_->next;
    return *this;
  }

  Self operator++(int) noexcept
  {
    auto ret = node_;
    node_ = node_->next;
    return ret;
  }

  // Util
  void set(Node* node) noexcept { node_ = node; }
  Node* extract() const noexcept { return static_cast<Node*>(node_); }
  Self next() const noexcept { return Self(node_->next); }
private:
  BaseNode* node_;
};

// ForwardListConstIterator is same with it instead of Ref and Pointer

trick: ForwardListBase

之所以设置ForwardListBase主要是因为：

• 将header的分配/构造/释放/析构放在基类，利用RAII处理（有便于派生类的异常处理）
• 继承特定的Allocator，利用EBCO进行优化（allocator往往是空类），这样就不需要额外的数据成员表示allocator

显然，ForwardList要用到两种allocator：Header和LinkedNode<T>，所以代码如下：

template<typename Alloc>
using HeaderAllocator = typename Alloc::template rebind<Header>::other;

template<typename T, typename Alloc>
using NodeAllocator = typename Alloc::template rebind<LinkedNode<T>>::other;

/**
 * EBCO
 * Need two allocator: header and node
 * This class also manage the header allocate and deallocate
 * but don't construct and destroy it, it just a POD object.
 */
template<typename T, typename Alloc=std::allocator<T>>
class ForwardListBase 
  : protected HeaderAllocator<Alloc>, protected NodeAllocator<T, Alloc> {
protected:
  using AllocTraits = std::allocator_traits<HeaderAllocator<Alloc>>;

public:
  ForwardListBase()
  try: header_(AllocTraits::allocate(*this, sizeof(Header)))
  {
    reset();
  }
  catch (std::bad_alloc const& ex) { 
    throw;
  }

  ForwardListBase(ForwardListBase&& other) noexcept
   : header_(other.header_)
  {
    other.header_ = nullptr;
  }

  ~ForwardListBase() noexcept 
  {
    // AllocTraits::destroy(this, header_);
    AllocTraits::deallocate(*this, header_, sizeof(Header));
  }

  void reset() noexcept
  {
    header_->prev = header_;
    header_->next = nullptr;
    header_->count = 0;
  }
protected:
  Header* header_;
};

template<typename T, typename Alloc=std::allocator<T>>
class ForwardList : protected forward_list_detail::ForwardListBase<T, Alloc> { 
public:
  //...
private:
  // Expose the header_ in Base class.
  // This is necessary for base class template.
  using Base::header_;
};

这样，派生类（ForwardList）就不需要操心header和allocator的问题了

从这里也可以得到ForwardList的大小也就一个header：24字节罢了

接下来就是讲解下各类操作，我是如何思考的。

操作

插曲：Node API

在ForwardList私有成员中提供了以下API便于节点的创造（包含分配和构造）和毁坏（包含析构和释放）

/**
* create_node has two step
* allocate memory ==> construct object
* Also drop_node has two step:
* destroy object ==> free memory(/deallocate)
*/
template<typename... Args>
Node* create_node(Args&& ...args) 
{
  auto node = AllocTraits::allocate(*this, sizeof(Node));

  node->next = nullptr;
  AllocTraits::construct(*this, &node->val, std::forward<Args>(args)...);

  return node;
}

void drop_node(BaseNode* _node) noexcept
{
  auto node = static_cast<Node*>(_node);
  AllocTraits::destroy(*this, node);
  AllocTraits::deallocate(*this, node, sizeof(Node));
}

insert API

// Insert after header
template<typename ...Args>
void emplace_front(Args&&... args) { push_front(create_node(STD_FORWARD(Args, args)...)); }
// It is may be better for builtin type that use value-passed parameter.
// But we can not suppose the move operation for ValueType is cheap
// Thus, I still write const&/&& or better.
void push_front(ValueType const& val) { push_front(create_node(val)); }
void push_front(ValueType&& val) { push_front(create_node(std::move(val))); }

// Insert before header
// Not standard required
template<typename ...Args>
void emplace_back(Args&&... args) { push_back(create_node(STD_FORWARD(Args, args)...)); }
void push_back(ValueType const& val) { push_back(create_node(val)); }
void push_back(ValueType&& val) { push_back(create_node(std::move(val))); }

// Insert after given position(presented by iterator)
template<typename ...Args> 
void emplace_after(ConstIterator pos, Args&&... args) 
{ insert_after(pos, ConstIterator(create_node(STD_FORWARD(Args, args)...))); }
void insert_after(ConstIterator pos, ValueType const& val) 
{ insert_after(pos, ConstIterator(create_node(val))); }
void insert_after(ConstIterator pos, ValueType&& val) 
{ insert_after(pos, ConstIterator(create_node(std::move(val)))); }

// Based on Node, thus we can reuse extracted node(throught call extract_xxx())
// Maybe this is the implementation function of std::forward_list<>
// But I expose these.
// Not standard required
inline void push_front(Node* new_node) noexcept;
inline void push_back(Node* new_node) noexcept;
inline void insert_after(ConstIterator pos, Node* new_node);

// Range insert
void insert_after(ConstIterator pos, SizeType count, ValueType const& val);
template<typename InputIterator, typename = 
  zstl::enable_if_t<zstl::is_input_iterator<InputIterator>::value>>
void insert_after(ConstIterator pos, InputIterator first, InputIterator last);  

基本上都是基础算法的API的一个wrapper，所以没有什么困难的，类似于下面这个：

template<typename T, typename A>
void FORWARD_LIST_TEMPLATE::push_front(Node* new_node) noexcept
{
  forward_list_detail::push_front(header_, new_node);
  ++header_->count;
}

值得一提的是我将基于节点的插入API也暴露了出来，这个一般是搭配extract_xxx()返回的节点使用的，这样就省了一次重新分配(malloc)和释放(free)，只需要设值即可插入链表。你可能会说用std::swap或直接设值就可以解决这个问题，实际确实如此，但是std::swap()对T做出了要求：必须满足std::is_swappable_v<T>，引入了额外的复杂度，并且std::swap一次性破坏了两个有效迭代器，而复用节点没有破坏除了该节点以外的任何节点，更别说因为显式调用了extract_xxx()，该节点就应该通过新的链表去访问，不会去再使用原来的那个迭代器，因此这样实际上并没有破坏任何有效迭代器。在之后的reverse和sort等算法中你也会注意，链表的这些算法都是stable的，它们以节点为单位，而不是通过std::swap()或std::iter_swap()，不会破坏任何迭代器。

erase API

// pop/erase/clear
inline ValueType pop_front();
inline Iterator erase_after(ConstIterator pos);
inline Iterator erase_after(ConstIterator first, ConstIterator last);
inline void clear();

// The implematation detial of pop_front() and erase_after()
// But these don't free the node in fact, just remove it from list
// The user can reuse the returnd node
// Not standard required
inline Node* extract_front() noexcept;
inline Node* extract_after(ConstIterator pos) noexcept;

基本都是wrapper，除了clear()：

template<typename T, typename A>
void FORWARD_LIST_TEMPLATE::clear()
{
  while (header_->next) {
    auto node = header_->next;
    header_->next = node->next;
    drop_node(node);
  }

  Base::reset();  
}

基本上没什么好讲的

search API

// Search the before iterator of the given value.
// It's useful for calling erase_after() and insert_after().
// Not standard required
Iterator search_before(ValueType const& val, ConstIterator pos);
template<typename UnaryPred>
Iterator search_before_if(UnaryPred pred, ConstIterator pos);
Iterator search_before(ValueType const& val) { return search_before(val, cbefore_begin()); }
template<typename UnaryPred>
Iterator search_before(UnaryPred pred) { return search_before(pred, cbefore_begin()); }

这个是我自己加的，我觉得某些情形可以简化操作，标准库并没有这种算法。

实现很简单，这里就不放了。

operation API

merge

// Operations
void merge(Self& list);
void merge(Self&& list) { merge(list); }
template<typename BinaryPred>
void merge(Self& list, BinaryPred pred);
template<typename BinaryPred>
void merge(Self&& list, BinaryPred pred) { merge(list, std::move(pred)); }

merge()操作是将两个有序链表合并成一个有序链表

这个操作同时也是sort()的一个实现细节

merge()由于要修改作为参数的链表，不能const&将左右值并收，这里并不是为了完美转发（perfect forwarding）

首先，我们肯定从header开始，然后比较下一节点的值

下图中other表示作为参数的链表，this表示被调用方法的链表

如果other的比this小，那么就插入到this的后面，反之，直接前进，因为此时满足不变式（有序）

如果other比this先遍历完，那么说明other已经嵌入this，成为了一条新的完整的有序链表

相反，this先遍历完，那么余下的other直接插在this后面

template<typename T, typename A>
void FORWARD_LIST_TEMPLATE::merge(Self& list)
{
  if (list.empty()) return;

  BaseNode* beg = header_;
  BaseNode* obeg = list.header_;
  
  while (beg->next != nullptr && obeg->next != nullptr) {
    if (GET_LINKED_NODE_VALUE(obeg->next) < GET_LINKED_NODE_VALUE(beg->next)) {
      auto old_node = obeg->next->next;
      insert_after(beg, list.extract_after(obeg));
      beg = beg->next;
      obeg->next = old_node;
    }
    else {
      beg = beg->next;
    }
  }

  if (beg->next == nullptr) {
    // It's also ok when list is empty
    splice_after(before_end(), list);
  }

  assert(list.empty());
  list.reset();
}

splice_after(list)

void splice_after(ConstIterator pos, Self& list);
void splice_after(ConstIterator pos, Self&& list) { splice_after(pos, list); }

splice_after()将作为参数的链表链接到pos参数后

由于是整个链表，所以处理十分简单，需要注意的一点是list不能为空，因为更新prev会出问题，指向的将是list的header

处理完后，list为空，重置list

// ForwardListBase
void reset() noexcept
{
  header_->prev = header_;
  header_->next = nullptr;
  header_->count = 0;
}

这个算法对于std::forward_list<>是$O(n)$，但是我这里是$O(1)$，为什么呢？

template<typename T, typename A>
void FORWARD_LIST_TEMPLATE::splice_after(ConstIterator pos, Self& list)
{
  // If list is empty,
  // it is wrong to update prev.
  if (list.empty()) return ;

  auto pos_node = pos.to_iterator().extract();
  auto old_next = pos_node->next;

  if (pos == before_end()) 
  {
    header_->prev = list.before_end().extract();
  }

  pos_node->next = list.begin().extract();
  list.before_end().extract()->next = old_next;
  
  header_->count += list.size();
  
  list.reset();
  ZASSERT(list.empty(), "The list must be empty");
}

splice_after(single node)

void splice_after(ConstIterator pos, Self& list, ConstIterator it);
void splice_after(ConstIterator pos, Self&& list, ConstIterator it) { splice_after(pos, list, it); }

过于简单，直接上代码

template<typename T, typename A>
void FORWARD_LIST_TEMPLATE::splice_after(ConstIterator pos, Self& list, ConstIterator it)
{
  insert_after(pos, list.extract_after(it));
}

splice_after(range)

void splice_after(ConstIterator pos, Self& list, ConstIterator first, ConstIterator last);
void splice_after(ConstIterator pos, Self&& list, ConstIterator first, ConstIterator last)
{ splice_after(pos, list, first, last); }

这个很草的一点是不能$O(1)$实现，不然splice_after()list版本可以直接转发给range版本

因为last的前一节点不知道，所以无论如何都得$O(n)$，于是索性写成下面这样：

template<typename T, typename A>
void FORWARD_LIST_TEMPLATE::splice_after(ConstIterator pos, Self& list, ConstIterator first, ConstIterator last)
{
  // (first, last)
  while (first.next() != last) {
    insert_after(pos, list.extract_after(first));
  }
}

remove

// In C++20, the return type is modified to size_type(i.e. SizeType here).
// It indicates the number of removed elements
SizeType remove(ValueType const& val);
template<typename UnaryPred>
SizeType remove_if(UnaryPred pred);

remove()的逻辑很简单，用search_before()迭代就行了。

需要注意的一点是，返回值在C++20变化了（见注释），所以我也就按20的标准来了，更合理，毕竟可能有这种需求嘛

template<typename T, typename A>
auto FORWARD_LIST_TEMPLATE::remove(ValueType const& val)
 -> SizeType
{
  SizeType count = 0;

  auto it = search_before(val);
  while (it != end()) {
    ++count;
    erase_after(it);
    it = search_before(val, it);
  }

  return count;
}

reverse

void reverse() noexcept;

reverse()的实现思维其实就是典型的栈，所以用递归也可以实现，这里我是用std::vector<>模拟栈（实际上，std::stack<>的默认容器就是std::vector<>）

显然，这个也与值无关，因此我将它分离了。

void reverse(Header* header) noexcept
{
  // Or use recurrsion to implemetation
  std::vector<BaseLinkedNode*> nodes;
  nodes.reserve(header->count);

  while (!FORWARD_LIST_EMPTY) {
    nodes.push_back(extract_front(header));
  }
  
  assert(FORWARD_LIST_EMPTY); 
  assert(nodes.size() == nodes.capacity());

  using SizeType = decltype(header->count);
  for (SizeType i = 0; i < nodes.size(); ++i) {
    push_front(header, nodes[i]);
  }
}

unique

// In C++20, the return type is modified to size_type(i.e. SizeType here).
// It indicates the number of removed elements
SizeType unique();
template<typename BinaryPred>
SizeType unique(BinaryPred pred);

unique()的作用和std::unique()一样，不过std::unique()会破坏迭代器（因为是通过覆盖实现的），因此有必要为ForwardList写个自己的。

遇到值相同的相邻节点，删到相邻节点不等位置便可，否则前进即可

template<typename T, typename A>
auto FORWARD_LIST_TEMPLATE::unique()
 -> SizeType
{
  SizeType count = 0;
  for (BaseNode* beg = header_; beg->next != nullptr && beg->next->next != nullptr; ) {
    // Adjacent node with same value
    if (GET_LINKED_NODE_VALUE(beg->next) == GET_LINKED_NODE_VALUE(beg->next->next)) {
      erase_after(beg->next);
      ++count;
    }
    else {
      beg = beg->next;
      if (beg == nullptr) break;
    }
  }

  return count;
}

sort

void sort();
template<typename Compare>
void sort(Compare cmp);

sort()我一开始是用的Quick Sort，效果还行，但是不如我曾经写list时用的那个Merge Sort，代码如下：

（sort()是Merge Sort, 而sort2()是Quick Sort）

template<typename T, typename A>
void FORWARD_LIST_TEMPLATE::sort()
{
  // TODO Optimization
  // lists store non-header list
  // To small list, maybe better a little.
  // It is not significant for large list.
  Self lists[64];
  Self list;  
  int8_t end_of_lists = 0;

  while (!empty()) {
    list.push_front(extract_front());
    
    for (int8_t i = 0; ; ++i) {
      if (lists[i].empty()) {
        list.swap(lists[i]);
        if (i == end_of_lists) end_of_lists++;
        break;
      } 
      else {
        // Merge non-empty list
        // larger list merge shorter list
        if (lists[i].size() > list.size()) {
          lists[i].merge(list);
          list.swap(lists[i]);
        }
        else
          list.merge(lists[i]);
      }
    }
  } 
    
  assert(list.empty());

  for (int i = end_of_lists - 1; i >= 0; --i) {
    list.merge(lists[i]);
  }

  *this = std::move(list);
}

template<typename T, typename A>
void FORWARD_LIST_TEMPLATE::sort2() 
{   
  ForwardList less;
  ForwardList equal;
  ForwardList larger;
  
  if (size() < 2) {
    return ;
  } 

  auto pivot = *begin();
  Node* tmp;

  equal.push_back(extract_front());

  while (!empty()) {
    tmp = extract_front();
    if (tmp->val < pivot) {
      less.push_back(tmp);
    }
    else if (pivot < tmp->val) {
      larger.push_back(tmp);
    }
    else {
      equal.push_back(tmp);
    }
  }
  
  less.sort();
  larger.sort();

  less.splice_after(less.cbefore_end(), equal);
  less.splice_after(less.cbefore_end(), larger);

  *this = std::move(less);
}

Quick Sort暂且不谈，学过的都看得懂

这个Merge Sort很有趣，它没有用递归实现，并且最多也只用65个链表，而Quick Sort递归层次深了的话，估摸着也不止65吧。

为什么整64是因为，这个表示它可以存的元素最大值为$2^{64}-1$，它的思路是这样的：

this表示当前待排序链表（假设其初始无序），lists也就是一开始预设的链表,它们就是merge sort中的partition，不过这里并不需要对partition进行排序，因为它们就是有序的，只需要merge（这是我觉得性能优越的一点）。我们用一个中间链表list保存与lists中非空链表merge的结果。

流程是这样的，从this中将一个个节点通过extract_front()提取，然后插入list，lists从第一个开始直到遇到空链表为止，我们一路merge，最后将最终的有序链表放到遇到空链表的位置，供下次merge，list重置。

起初，list仅一个节点，然后放到lists[0]，之后合并为两个节点，放到lists[1]，之后合并为4个节点时，放到lists[2]，合并为8个节点之前，如下图所示：

再加入一个节点，会依次与list[0], list[1],list[2]合并，然后放到list[3]

也就是说lists[i]最多存放之前的链表最多元素的累计+1， 即$1+2+2^{i-1}+1 = 2^i$。

当链表中的所有节点处理完，然后合并lists中所有非空链表，end_of_lists是用来提前终止该过程的，因为end_of_lists包括后面的链表几乎都为空。

最后附上一张benckmark的图，可以看出sort()性能优于sort2()

assign

void assign(SizeType count, ValueType const& value);
template<typename InputIterator,
typename = zstl::enable_if_t<zstl::is_input_iterator<InputIterator>::value>>
void assign(InputIterator first, InputIterator last);
template<typename U>
void assign(std::initializer_list<U> il) { assign(il.begin(), il.end()); }

assign()这玩意挺尬尴的，不如直接拷贝赋值（实际这个也是拷贝赋值的实现细节）

需要注意的问题就是复用节点了，因为不管this的节点数是否大于参数的链表，它都有节点复用，然后决定是否新增节点或删除节点即可

template<typename T, typename A>
template<typename InputIterator, typename>
void FORWARD_LIST_TEMPLATE::assign(InputIterator first, InputIterator last)
{
  Iterator beg;
  for (beg = before_begin(); beg.next() != end() && first != last; ++beg, ++first) {
    AllocTraits::destroy(*this, &*beg.next());
    AllocTraits::construct(*this, &*beg.next(), *first);
  }
  
  // size() < distance(first, last) 
  if (beg.next() == end()) {
    while (first != last) {
      // insert_after(beg, *first);
      push_back(*first++);
    }  
  }
  else if (first == last) {
    // size() > distance(first, last)
    while (beg.next() != end()) {
      erase_after(beg);
    }
  }
}

resize

void resize(SizeType n);
void resize(SizeType n, ValueType const& val);

这个实现十分简单，直接上代码：

template<typename T, typename A>
void FORWARD_LIST_TEMPLATE::resize(SizeType n)
{
  if (size() <= n) {
    auto diff = n - size();

    while (diff--) {
      push_back(T{});
    }
  }
  else {
    auto it = zstl::advance_iter(before_begin(), n);

    while (it.next() != end()) {
      erase_after(it);
    }
  }
}

对比std::forward_list<>，第一种情形（size() <= n）我的写法更快，因为可以直接获取$O(1)$获取size，第二种差不多，读者可以自己尝试不用size()写一下。

结语

暂时就写这些，可能以后会补充（可能有bug）

代码

类模板，节点定义等

分离的算法源文件

测试文件和sort的benchmark