定長陣列數據結構允許快速重用任意元素？ C++

Question

我對C++相對比較陌生，並且試圖爲特定問題選擇最合適的數據結構，但是我發現很難找到答案。

我希望創建一個小的（最大1000個）int或簡單結構的數組。在我的代碼中，任何時候我都需要添加和刪除我的數組中的元素，但是我不希望動態重新分配ram的開銷。此外，因爲我將有其他變量指向我的數組中的元素，我不想重新編號/重新排序元素，因爲這會搞砸這種關係。由於我可以確定數組中的最大元素數量，所以我很樂意預先分配所有需要的ram，但我不確定如何有效地跟蹤哪些元素變爲空閒，以便我可以將它們重新用於新元素，例如需要。這類問題是否有明顯的數據結構？ 在此先感謝。

Answer 1

我認爲在這種情況下，最好的辦法是使用預分配雙向鏈表...

// Untested code... just to give the idea 

struct Node 
{ 
    int data; 
    Node *prev, *next; 

    static Node *first, *last, *free; 

    // Allocates a new node before the specified node or 
    // at the end of the list if before is NULL 
    static Node *alloc(int data, Node *before) 
    { 
     // Check the free list first 
     Node *n = free; 
     if (!n) 
     { 
      // There are no free nodes... allocate a bunch of them 
      Node *page = new Node[1000]; 
      for (int i=0; i<999; i++) 
      { 
       page[i].next = &page[i+1]; 
      } 
      page[999].next = NULL; 
      n = free = &page[0]; 
     } 

     // Update the free list 
     free = n->next; 

     // Link the new node to neighbors 
     n->next = before; 
     n->prev = before ? before->prev : last; 
     if (n->prev) n->prev->next = n; else first = n; 
     if (n->next) n->next->prev = n; else last = n; 

     // Initialize it 
     n->data = data; 

     return n; 
    } 

    // Deallocates a node, placing it in the free list for reuse 
    static dealloc(Node *n) 
    { 
     if (n) 
     { 
      // Remove from double chain 
      if (n->next) n->next->prev = n->prev; else last = n->prev; 
      if (n->prev) n->prev->next = n->next; else first = n->next; 

      // Add to free list 
      n->next = free; free = n; 
     } 
    } 
}; 

當你需要分配一個節點只需要調用Node::alloc傳遞數據和在哪裏放節點。當你需要釋放它時，只需調用node dealloc。

節點在「頁面」中分配並在釋放後重新使用。這樣可以最大限度地減少對內存管理器的調用次數，並且可以顯着加快速度。

雙鏈接結構永遠不需要移動存儲器中的現有節點（因此不需要調整指針）。對元素重新排序也很容易，例如添加Node::moveTo(Node *before)方法。

這種方法的缺點是訪問第n個元素給定的索引是O（n）操作。

Answer 2

我不想的動態再分配RAM中的所有你能想到的使用vector<>的時間

的開銷。它在需要時進行動態分配，但不是全部。它是高效的書寫容器。

因爲我可以肯定在我的數組元素的最大數量的我 高興預分配所需的所有

雖然聲明的載體，你可以指定大小爲：

vector<int> vi(1000); 

您也可以參考vi從其他地方。

Answer 3

std::vector是你應該用什麼& 使用智能指針，而不是原始指針。

Answer 4

您正在尋找Pool allocator。你可以編寫自己的或使用Boost.Pool

Answer 5

既然你仍然想維護外部變量和內部數組元素之間的關係，是的，你不能重新排序它們。但是，使用std :: vector將刪除/添加無法滿足您需要的新元素時對剩餘元素進行重新排序。

您可以將bool值與數組中的每個元素進行組合，指定該元素是否正在使用。請注意，如果內存對您至關重要，您可以使用位圖。

struct CElement 
{ 
    // specify whether this element is in use 
    bool isUsed; 
    int element; 
} 

const size_t MAX_CAPACITY = 1000; 
CElement myArray[MAX_CAPACITY]; 

另一種選擇是使用鏈表。從鏈接列表中添加或刪除節點需要一段時間，而指向其他節點的指針仍保持不變。所以你可以通過讓外部變量持有指向節點的指針而不是數組索引來建立「關係」。另外，你甚至不需要預先分配1000個元素。

Answer 6

我要補充的一點是分配整數/小結構的開銷很小，如果你初始化沒有元素的vector，並使用vector.push_back()和vector.erase()這將意味着你不需要跟蹤哪些元素是免費的，哪些不是。您似乎對效率感到擔憂，但請記住按照以下順序執行操作：

1. 實施乾淨易讀的解決方案。使用表達你想要清楚的功能。
2. 如果且只有您發現該解決方案存在嚴重的性能問題，則開始使用更復雜但更高效的解決方案。

Answer 7

一個std:vector<>似乎適合您的要求相當不錯：

• 使用vector::reserve()爲您規劃陣列具有元素的最大數量分配足夠的存儲 - 注意reserve()實際上並沒有添加元素矢量。該矢量仍然具有與調用reserve()之前相同的元素數量。但是，它確實保證vector將元素添加到vector時不需要執行重新分配，除非該附加元素會導致元素數超過預留。這也意味着進入vector的指針將保持穩定。
• 元素保證位於與正常指針算術兼容的元素尋址的連續內存塊中。換句話說，如果你有一個指針指向一個元素，就可以使用正常的指針運算（或數組索引）

Answer 8

你描述的是，實質上是一個固定大小的內存池獲得一個指向另一個元素。你沒有解釋爲什麼你需要它。除非有特定的理由讓你的對象保持一個類似數組的結構，否則你應該通過new分別分配它們。除非分析人員以其他方式說服你，否則不需要池分配器。

如果您確實有理由將所有對象保留在數組中，無論出於何種原因，您將實現您自己的基於數組的池分配器。最簡單的一個使用簡單的鏈表來跟蹤空閒塊。您保留第一個未使用的元素的索引，並且每個未使用的元素保留下一個元素的索引。 你不應該這樣做，除非你確切知道你在做什麼，爲什麼。