std::max_element返回迭代器在vector清空更新后值变化及索引引用疑问

在基于vector of lists的桶排序程序中，我用std::max_element获取vector的最大元素，但发现原vector被清空并更新后，该迭代器指向的值变成了vector相同索引的新值。

原代码 #

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;

void BucketSort(std::vector<int>& vList)
{
    int i = 0;

    auto maxElem = std::max_element(vList.begin(), vList.end());
    std::vector<std::list<int>> tempList;
    std::cout << "Max element = " << *maxElem << "\n";
    for (i = 0; i <= *maxElem; i++)
        tempList.push_back({});

    for (auto x : vList)
    {
        tempList[x].push_back(x);
    }

    vList.clear();
    std::cout << "*max = " << *maxElem << "\n";
    i = 0;
    while(i <= *maxElem)
    {
        std::cout << "*max = " << *maxElem << " i = " << i << " tempList[i].size() = " << tempList[i].size() << "\n";
        if (tempList[i].empty() == false)
        {
            vList.push_back(tempList[i].front());
            tempList[i].pop_front();
        }
        else
            i++;
    }
}

int main()
{
    std::vector<int> vList = {1, 5, 4, 1 };
    BucketSort(vList);

    return 0;
}

程序输出 #

Max element = 5
*max = 5
*max = 5 i = 0 tempList[i].size() = 0
*max = 5 i = 1 tempList[i].size() = 2
*max = 5 i = 1 tempList[i].size() = 1
*max = 1 i = 1 tempList[i].size() = 0

解答 #

你观察到的现象是迭代器仍指向原索引位置，但必须明确：vector执行clear()后，所有迭代器都会失效，此时对失效迭代器的解引用属于未定义行为——你当前环境里表现出“指向原索引新值”只是巧合，换个编译器或运行环境可能会崩溃、输出乱码，或者出现其他奇怪结果。

具体到你的代码：

1. 初始时maxElem指向原vector中索引1的位置（值为5）。
2. 调用vList.clear()后，vector的元素被销毁，但底层内存可能并未释放（取决于实现），此时maxElem已经是无效迭代器。
3. 后续给vList push_back元素时，新元素会填充到原内存空间，当第二个元素（值为1）被放到原索引1的位置时，解引用失效的maxElem就会读到这个新值，这就是输出最后一行*max = 1的原因。

正确的解决方法 #

不要依赖失效的迭代器，而是在获取最大值后，把值存入普通变量：

// 替换原来的auto maxElem = ...
int max_val = *std::max_element(vList.begin(), vList.end());

之后所有用到*maxElem的地方都换成max_val，这样就彻底避免了迭代器失效的问题。

修改后的核心代码片段：

void BucketSort(std::vector<int>& vList)
{
    int i = 0;

    int max_val = *std::max_element(vList.begin(), vList.end());
    std::vector<std::list<int>> tempList;
    std::cout << "Max element = " << max_val << "\n";
    for (i = 0; i <= max_val; i++)
        tempList.push_back({});

    // ... 其余代码不变，仅把*maxElem替换为max_val
    vList.clear();
    std::cout << "*max = " << max_val << "\n";
    i = 0;
    while(i <= max_val)
    {
        std::cout << "*max = " << max_val << " i = " << i << " tempList[i].size() = " << tempList[i].size() << "\n";
        // ... 其余逻辑不变
    }
}

内容的提问来源于stack exchange，提问作者Uddesh