如何用鏈表替換std :: vector？

我用std::vector來製作我的算法。我想用鏈接列表替換向量。如何用鏈表替換std :: vector？

爲了做到這一點，我想用std::list的，但我不知道如何做到這一點，例如我曾嘗試下面的示例爲矢量/列表中找到一個值：

void find_values_in_vector(const std::vector<int>& input_vector, int value, int &rv1, int &rv2) 
{ 
    if (input_vector[0] >= value) { // too small 
    rv1 = 0; rv2 = 0; return; 
    } 
    int index = (int)input_vector.size() - 1; 
    if (input_vector[index] <= value) { // too big 
    rv1 = index; rv2 = index; return; 
    } 
    // somewhere inside 
    index = 0; 
    while (input_vector[index] <= value) { 
    index++; 
    } 
    rv1 = index - 1; rv2 = index; return; 
} 

void find_values_in_list(const std::list<int>& input_list, int value, int &rv1, int &rv2) 
{ 
    if (*input_list.begin() >= value) { // too small 
    rv1 = 0; rv2 = 0; return; 
    } 
    if (*input_list.end() <= value) { // too big 
    rv1 = (int)input_list.size() - 1; rv2 = (int)input_list.size() - 1; return; 
    } 
    // somewhere inside 
    int index = 0; int temp = *input_list.begin(); 
    while (temp <= value) { 
    temp = *input_list.next(); index++; 
    } 
    rv1 = index - 1; rv2 = index; return; 
}

這似乎不起作用，因爲成員函數next()不存在。不過我記得瀏覽鏈表是通過開始，然後進一步移動到下一個元素，直到達到某個點。我已經看到有一種方法可以通過在for循環中使用interator來完成此操作，但是我不知道我的方法有什麼問題？我的印象是std::list是一個雙向鏈表的標準實現，或者我錯了，在這種情況下，類是鏈表的實現（它不需要是雙向的鏈表）？

來源

2016-09-08 Dominique

與stl中的所有容器相同：您主要通過迭代器來導航它們。如果你來自其他語言，它已經有點習慣了，但它非常整齊，因爲它在任何地方都是一致的。是否有任何理由順便說一句。爲什麼你切換到列表？向量在大多數情況下更好。 – Hayt

如果要使用整數（不是'std :: list'）進行索引，請將其設置爲'size_t'，而不是'int'。 – LogicStuff

通過集裝箱進行迭代的標準方法是這樣的：

for(std::list<int>::iterator it = input_list.begin(); 
    it != input_list.end(); 
    it++) 
{ 
    .... 
}

這也適用於矢量地圖，雙端隊列，等等。 Iterator的概念在整個STL中始終得到實現，所以最好習慣這個概念。

還有一些迭代器操作，如std::distance和std::advance等，爲不同類型的迭代器（我建議你對他們和他們的優點/侷限性讀了）

如果你有C++ 11提供你也可以使用這個語法（可能對您的問題沒有幫助）

for(const auto& value : input_list) 
{ 
    ... 
}

這也適用於整個STL容器。

來源

2016-09-08 08:02:01 Hayt

另一個問題：我選擇了矢量，因爲它很容易得到它的第n個元素，但使用列表意味着需要一個迭代器，但我不明白這一點：似乎在處理一個迭代器'it'，如果你做了++ n次，那麼你將會到達第n個元素。爲什麼'it + n'不起作用？那不一樣嗎？ – Dominique

++運算符重載並創建此行爲。你可以用'std :: advance'做你想做的事情，迭代器根據它們是什麼類型的迭代器而有不同的行爲。向量有隨機訪問迭代器，這就是爲什麼你可以使用索引。列表不，這就是爲什麼你必須提前n次。 – Hayt

但是，如果有疑問，請使用'++ it'而不是'it ++'：它可能會避免複製迭代器。 http://stackoverflow.com/a/24904/5293824 – kubanrob

這應該適用於vector，list，deque和set（假設內容已排序）。

template <class T> 
void find_values_in_container(const T& container, int value, int &rv1, int &rv2) 
{ 
    rv1 = rv2 = 0; // Initialize 
    if (container.empty() || container.front() >= value) 
    { 
    return; 
    } 
    for (const auto& v : container) 
    { 
    rv2++; 
    if (v > value) 
    { 
     break; 
    } 
    rv1++; 
    } 
    return; 
}

來源

2016-09-08 09:06:47

如何用鏈表替換std :: vector？

回答

相關問題