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

（烏爾裏希·艾克哈特的答案動機）