0

I have a std::vector<T> and a std::map<U, std::size_t>, where the map acts as a different way to index the vector, i.e. the value in a key-value pair of the map is the index of a vector element. I can guarantee that not only the keys, but also the values of the map are unique.

Now when I apply a std::sort to the vector, that obviously changes the indices under which elements can be found, and I'd like to update my map accordingly.

I have found this answer for applying a permutation to a second vector. What I want to do is apply this permutation to the values of the map.

The following code does work, but is of course terribly inefficient

template <typename T, typename U>
std::vector<T> apply_permutation(const std::vector<T>& vec,
                                 std::map<U, std::size_t>& m,
                                 const std::vector<std::size_t>& p)
{
    std::vector<T> sorted_vec(vec.size());
    std::transform(p.begin(), p.end(), sorted_vec.begin(),
                   [&](std::size_t i){ return vec[i]; });
    for (std::size_t i(0); i != p.size(); ++i)
        for (auto it = m.begin(); it != m.end(); ++it)
            if (it->second == p[i])
                it->second = i;

    return sorted_vec;
}

I'm looking for a more efficient way to keep the vector and map in sync.

Community
  • 1
  • 1
Philipp
  • 957
  • 1
  • 6
  • 20

1 Answers1

0

Lets say we start with this:

vector<char> v1{'b', 'c', 'a'};
map<char, size_t> m{{'b', 0}, {'c', 1}, {'a', 2}};

If we iterate the map from begin() to end(), we would get:

  {'a', 2}
  {'b', 0}
  {'c', 1}

since a map sorts the elements on key.

Now, if you sort the vector, it becomes

vector<char> v2{'a', 'b', 'c'};

At this point, you can just iterate over the map and change the indices 

size_t index = 0;
for (auto& elem : m) {
  assert(elem.first == v2[index]);
  elem.second = index++;
}
Arun
  • 19,750
  • 10
  • 51
  • 60