如何有效地訪問C++中的列表信息？

我原來是用Python做這個遊戲的，然後在一個學校項目中將它轉換爲C++。如何有效地訪問C++中的列表信息？

的問題是，C++的std::list不允許我訪問像Python的list項目做（list[1]），更是這樣，訪問是一個列表（list[2][5]）內列出的項目。我一直無法找到一種有效的方法來做到這一點，或者找到一個可行的列表的替代方案。

來源

2016-01-20 Shadow

列表無法通過索引訪問。如果你想隨機訪問，使用矢量。 –

將C++與Python進行比較時，不要混淆術語* list *。一個'std :: list'是C++中的一個雙向鏈表。這意味着不能隨機訪問列表中的元素。 – PaulMcKenzie

添加到@PaulMcKenzie中，與Python list最直接等價的是std :: vector（它們都是作爲一個動態調整大小的數組實現的，它執行重定位以在序列末尾插入/刪除攤銷'O（1）'）。 – ShadowRanger

請勿使用std::list。它實現了一個雙向鏈表，它不提供下標運算符，因爲鏈表的隨機訪問不能以恆定的複雜度實現。

取而代之的是，使用std::vector實現動態增長的數組，其中下標運算符定義。

由於@ShadowRanger已評論，你也許發現std::deque有用。它支持像std::vector這樣的恆定時間隨機存取功能，另外還可以在刪除元素時自動釋放存儲空間。（對於std::vector，您必須明確地通過調用shrink_to_fit來做到這一點，並且這可能很容易走錯方向）。當您需要在開始和結束時追加元素時，它也會更好。但據我所知，你不想改變容器中元素的數量。

另請注意Python和C++之間的另一個區別。在Python中，如果你寫

my_things = [1, 2, 3, 4] 
your_things = [5, 6, 7] 
our_things = [my_things, your_things]

然後your_things和our_things[1]指向同一個列表。這是因爲Python中的對象是通過引用來引用的。另一方面，在C++中，容器具有價值語義。也就是說，如果你寫

std::vector<int> my_things = {1, 2, 3, 4}; 
std::vector<int> your_things = {5, 6, 7}; 
std::vector<std::vector<int>> our_things = {my_things, your_things};

our_things將包含副本my_things和your_things以及在改變不會影響其他。如果這不是你想要的，你可以改爲一次定義嵌套列表。

std::vector<std::vector<int>> our_things = { 
    {1, 2, 3, 4}, // my things 
    {5, 6, 7},  // your things 
};

來源

2016-01-20 18:15:30 5gon12eder

如果您需要（有效）恆定的時間插入/移除元素開始和結束時使用'std :: deque' （相對於開始時矢量的「O（n）」成本，最後將「O（1）」分期償還，但間歇性的高成本重新分配）。 'deque'仍然提供'O（1）'隨機訪問，（支付的價格是更高的內存開銷和碎片感謝從一堆小固定大小的數組，而不是'vector'的單個動態大小的數組）。 'deque'唯一讓你失去的是能夠在迭代過程中有效地添加和移除序列中間的元素。 – ShadowRanger

@ShadowRanger在理論上'O'的複雜性很好，如果你已經對你的代碼進行了剖析以確定瓶頸，但vector應該是默認的順序訪問容器。由於緩存，預取等因素，Moder CPU喜歡連貫的內存訪問。 – Angew

我不會考慮'std :: deque'，除非我有一些特定的需求，比如前面的大量插入。即使插入時間不變，常數也比矢量大。如果我們有這樣的動物，那麼「O（1）」隨機存取更像「O（2）」。 –

您可以使用矢量而不是列表。

來源

2016-01-20 18:14:29

在C++中，標準::列表不經由操作符[]支持隨機訪問查找。如果你要繼續使用列表，你應該看看std :: advance函數。

list<string>::iterator itr = whichList.begin(); 
std::advance(itr, i); 
if (itr->empty()) 
{ 
/* ... assuming that you're testing for an empty string */ 
}

如果可能的話，你可能要考慮其他的標準容器，比如std ::向量或std :: deque的，兩者通過操作[]提供隨機存取查找。

來源

2016-01-20 18:17:56 GutiMac

如果您不需要更改列表的大小，你可以使用普通的數組。

這甚至可能是最快的選擇。但是，只要不更改大小，std::vector的性能相似。

來源

2016-01-20 18:23:46 woodtluk

不「相似」：「相同」！ –

如何有效地訪問C++中的列表信息？

回答

相關問題