C++固定大小链表

Question

非重复：

• Which STL C++ container to use for a fixed size list?（具体使用情况）
• std::list fixed size（见下文）

动机：

分配发生一次（在构造函数中）并且释放一次（在析构函数中）。 （1）在列表中的任何位置插入和移除元素而不需要处理内存管理开销。这对于基于阵列的实现来说是不可能的。

是否有直接的方法来实现这个使用标准库？在Boost中是否有这样的实现？

Answer 1

当我读到时，我首先想到的是使用不同分配器的方法，即预先分配给定数量的元素以避免分配的代价。尽管我对定义分配器并不熟悉，但是如果你发现我对结果感兴趣。

没有这个，这里有一个不同的方法。我救了自己template ...的东西，但我想你可以自己做，如果你需要。

typedef std::list<...> list_t; 

struct fslist: private list_t 
{ 
    // reuse some parts from the baseclass 
    using list_t::iterator; 
    using list_t::const_iterator; 
    using list_t::begin; 
    using list_t::end; 
    using list_t::empty; 
    using list_t::size; 

    void reserve(size_t n) 
    { 
     size_t s = size(); 
     // TODO: Do what std::vector does when reserving less than the size. 
     if(n < s) 
      return; 
     m_free_list.resize(n - s); 
    } 

    void push_back(element_type const& e) 
    { 
     reserve_one(); 
     m_free_list.front() = e; 
     splice(end(), m_free_list, m_free_list.begin()); 
    } 

    void erase(iterator it) 
    { 
     m_free_list.splice(m_free_list.begin(), *this, it); 
    } 

private: 
    // make sure we have space for another element 
    void reserve_one() 
    { 
     if(m_free_list.empty()) 
      throw std::bad_alloc(); 
    } 
    list_t m_free_list; 
}; 

这是不完整的，但它应该让你开始。还要注意，splice（）不公开，因为将元素移动到另一个列表将会改变大小和容量。

Answer 2

我认为最简单的方法就是拥有2个数据结构。一个固定大小的数组/矢量用于“分配”。您只需从数组中获取一个元素来创建一个节点并将其插入到您的列表中。像这样的东西似乎满足你的要求：

struct node { 
    node *prev; 
    node *next; 
    int value; 
}; 

node storage[N]; 
node *storage_ptr = storage; 

然后创建一个新的节点：

if(node == &[storage + N]) { 
    /* out of space */ 
} 

node *new_node = *storage_ptr++; 
// insert new_node into linked list 

这是固定的大小，分配全部一次，当storage超出范围，节点将会随着它而毁灭。

至于有效地从列表中删除项目，它是可行的，但稍微复杂一点。我将有一个“已删除”节点的辅助链接列表。当您从主列表中删除node时，请将其插入“已删除”列表的末尾/开头。

分配时，请在去storage阵列之前先检查已删除的列表。如果它是NULL则使用storage，否则，将其从列表中摘下。

Answer 3

我最终为这个名为rigid_list写了一个模板。 这是远远没有完成，但它是一个开始：

https://github.com/eltomito/rigid_list

（乌尔里希·艾克哈特的答案动机）