For a BucketSort program using a vector of lists. I used std::max_element to find out the maximum element from the vector.

But it looks like once the original vector is cleared and updated, the iterator returned by max_element also changes the value to the updated value from vector (vList) from same index.

#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;
}

Produces below output

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

Does the iterator retain the reference to the index returned even after clearing the vector?

CodePudding user response：

The iterators provided in C store an address that is referenced. When you clear the vector and fill it with new values, the iterator is still pointing to the same place and will show the new value in that location. Take a look at this example:

[0,1,2,3,4]
     ^

You have an iterator pointing to the third element of the vector. Now imagine you clear the vector and fill it with new values:

[5,6,7,8,9]
     ^

Now the pointer points to the same address, but that memory now holds a new value. You can get around this by storing the data in a local variable and use it throughout the rest of your code: int maxValue = *maxElem

CodePudding user response：

You already wrote the line using namespace std; I think u needn't use std in every single line..