Сотрите те значения, которые уже существуют в значениях других ключей в карте c ++

Question

Предположим, у меня есть карта со значениями, указанными ниже:

std::map<int, std::set<int>> myMap;
key 0: 1,2,3,4,5,6,7,8,9,10
key 1: 1,2,3,4,5,6
key 2: 4,5,6,7
key 3: 6,7

Теперь я хочу стереть все те значения в ключе 0, которые существуют в других ключах, следующих за ним. Аналогично для ключа 1 и так далее. Итак, окончательный вывод (myMap) должен выглядеть так:

key 0: 8,9,10
key 1: 1,2,3
key 2: 4,5
key 3: 6,7

Насколько я знаю, поиск по значениям на карте не так прост. И для моего кода поиск по значениям невозможен, так как мои данные чрезвычайно велики. Это было бы много времени.

Есть ли лучший способ сделать это, не просматривая каждое значение в каждом из следующих ключей, чтобы удалить общие значения?

Answer 1

std::set<int> to_remove;
for(auto&& e:backwards(myMap)) {
  std::set<int> r;
  std::set_difference(
    r.second.begin(), r.second.end(),
    to_remove.begin(), to_remove.end(),
    std::inserter(r)
  );
  std::copy(r.second.begin(), r.second.end(), std::inserter(to_remove));
  r.second = std::move(r);
}

, где backwards - это:

template<class It>
struct range_t {
  It b, e;
  It begin() const { return b; }
  It end() const { return e; }
};
template<class C>
auto backwards( C& c )
-> range_t< typename C::reverse_iterator  >
{
  return {c.rbegin(), c.rend()};
}
template<class C>
auto backwards( C const& c )
-> range_t< typename C::const_reverse_iterator >
{
  return {c.rbegin(), c.rend()};
}

, что позволяет быстро и легко перебирать контейнер назад.

Это O (nlgn), тогда как ваше решение было O(п ^ 2lgn).