C++迭代器失效解決辦法詳解

更新時間：2024年12月31日 08:32:35 作者：Octopus2077

這篇文章主要介紹了迭代器失效的概念,以及在vector、list和map等容器中插入和刪除操作導致迭代器失效的情況,文中通過代碼介紹的非常詳細,需要的朋友可以參考下

迭代器失效

定義

? 迭代器失效是指在使用迭代器遍歷容器（如vector、list、map等）的過程中，由于容器內(nèi)部結構發(fā)生了變化，導致原來的迭代器不再有效，不能正確地指向它原本所指向的元素或者不能按照預期的方式進行遍歷。

以 vector 為例說明

插入操作導致的迭代器失效

? 當在vector中插入元素時，如果插入操作導致了內(nèi)存重新分配，那么所有指向該vector的迭代器都會失效。這是因為vector的存儲是連續(xù)的內(nèi)存空間，當插入元素使得當前容量不夠時，vector會重新分配一塊更大的內(nèi)存空間，將原來的元素復制或移動到新的空間中，原來的迭代器所指向的內(nèi)存地址就不再有效。

例：

#include <iostream>
#include <vector>
int main() {
    std::vector<int> v = {1, 2, 3};
    auto it = v.begin();
    v.push_back(4);  // 插入元素可能導致內(nèi)存重新分配
    // 此時it可能已經(jīng)失效，下面的操作可能會導致程序出錯
    std::cout << *it << std::endl;
    return 0;
}

調(diào)整一下：

刪除操作導致的迭代器失效

? 在vector中刪除元素后，被刪除元素之后的迭代器都會失效。這是因為刪除元素會導致后面的元素向前移動，迭代器原本指向的元素位置發(fā)生了改變。

如：

#include <iostream>
#include <vector>
int main() {
    std::vector<int> v = {1, 2, 3, 4};
    auto it = v.begin() + 1;  // 指向元素2
    v.erase(it);  // 刪除元素2
    // 此時it已經(jīng)失效，下面的操作可能會導致程序出錯
    std::cout << *it << std::endl;
    return 0;
}

以 list 為例說明

插入操作

? 對于list容器，插入操作不會導致迭代器失效。因為list是由節(jié)點組成的鏈表結構，插入新節(jié)點只是修改節(jié)點之間的鏈接關系，迭代器指向的節(jié)點本身并沒有改變。

? 例如：

#include <iostream>
#include <list>
int main() {
    std::list<int> l = {1, 2, 3};
    auto it = l.begin();
    l.insert(it, 0);  // 在頭部插入元素0
    std::cout << *it << std::endl;  // it仍然有效，輸出1
    return 0;
}

刪除操作

? 在list中刪除一個元素后，只有指向被刪除元素的迭代器會失效。其他迭代器不受影響，因為鏈表結構的特點使得刪除操作只是調(diào)整節(jié)點之間的連接，不會像vector那樣引起其他元素的移動。

? 例如：

#include <iostream>
#include <list>
int main() {
    std::list<int> l = {1, 2, 3};
    auto it = l.begin();
    l.erase(it);  // 刪除第一個元素1
    // it已經(jīng)失效，不能再使用
    // 可以重新獲取迭代器來遍歷
    for (auto new_it = l.begin(); new_it!= l.end(); ++new_it) {
        std::cout << *new_it << std::endl;
    }
    return 0;
}

? 又如：

在關聯(lián)容器中的情況

對于關聯(lián)容器（以map為例），插入操作不會導致迭代器失效，因為插入新元素只是在紅黑樹（map通常的底層實現(xiàn)）中添加一個節(jié)點，不會改變已有節(jié)點的地址。

刪除操作會導致指向被刪除元素的迭代器失效，但其他迭代器仍然有效，因為紅黑樹的結構調(diào)整不會影響其他節(jié)點的內(nèi)存位置。
? 例如：

#include <iostream>
#include <map>
int main() {
    std::map<int, int> m = {{1, 10}, {2, 20}};
    auto it = m.find(1);
    m.erase(it);  // 刪除鍵為1的元素
    // it已經(jīng)失效，不能再使用
    for (auto new_it = m.begin(); new_it!= m.end(); ++new_it) {
        std::cout << new_it->first << " " << new_it->second << std::endl;
    }
    return 0;
}