Как обновить существующий элемент std :: set?

Question

У меня есть std::set<Foo>, и я хотел бы обновить в нем некоторое значение существующего элемента.Обратите внимание, что значение, которое я обновляю, не меняет порядок в наборе:

#include <iostream>
#include <set>
#include <utility>

struct Foo {
  Foo(int i, int j) : id(i), val(j) {}
  int id;
  int val;
  bool operator<(const Foo& other) const {
    return id < other.id;
  }
};

typedef std::set<Foo> Set;

void update(Set& s, Foo f) {
  std::pair<Set::iterator, bool> p = s.insert(f);
  bool alreadyThere = p.second;
  if (alreadyThere)
    p.first->val += f.val; // error: assignment of data-member
                           // ‘Foo::val’ in read-only structure
}

int main(int argc, char** argv){
  Set s;
  update(s, Foo(1, 10));
  update(s, Foo(1, 5));
  // Now there should be one Foo object with val==15 in the set.                                                                
  return 0;
}

Есть ли какой-нибудь краткий способ сделать это?Или я должен проверить, если элемент уже там, и если так, удалить его, добавить значение и заново вставить?

Answer 1

Поскольку val не участвует в сравнении, его можно объявить mutable

struct Foo {
  Foo(int i, int j) : id(i), val(j) {}
  int id;
  mutable int val;
  bool operator<(const Foo& other) const {
    return id < other.id;
  }
};

Это означает, что значение val может изменяться в логически-постоянном Foo, что означает, что оно не должно влиять на другие операторы сравнения и т. Д.

Или вы можете просто удалить и вставить, что занимает O (1) дополнительное время (по сравнению с доступом и изменением), если вставка использует позицию непосредственно перед сразу после старой в качестве подсказки.

Что-то вроде:

bool alreadyThere = !p.second; // you forgot the !
if (alreadyThere)
{
    Set::iterator hint = p.first;
    hint++;
    s.erase(p.first);
    s.insert(hint, f);
}

Answer 2

Не пытайтесь решить эту проблему, работая вокруг постоянства элементов в set. Вместо этого, почему бы не использовать map, который уже выражает отношение ключ-значение, которое вы моделируете, и предоставляет простые способы обновления существующих элементов.

Answer 3

Сделать val изменяемым как:

mutable int val;

Теперь вы можете изменить / изменить / изменить val, даже если foo равно:

void f(const Foo & foo)
{
     foo.val = 10;  //ok
     foo.id  = 11;  //compilation error - id is not mutable.
}

Между прочим, из вашего кода вы, кажется, думаете, что если p.second истинно, то значение уже существует в наборе, и поэтому вы обновляете связанное значение. Я думаю, вы ошиблись. На самом деле все наоборот. doc в cpluscplus говорит:

Элемент pair :: second в паре устанавливается равным true, если был вставлен новый элемент, или false, если существовал элемент с таким же значением.

что правильно, на мой взгляд.

---

Однако, если вы используете std::map, ваше решение будет простым:

void update(std::map<int,int> & m, std::pair<int,int> value) 
{
    m[value.first] += value.second;
}

Что делает этот код? m[value.first] создает новую запись, если ключ не существует на карте, и значением новой записи является значение по умолчанию int, которое равно нулю. Таким образом, это добавляет value.second к zero. Или, если ключ существует, он просто добавляет value.second к нему. То есть приведенный выше код эквивалентен этому:

void update(std::map<int,int> & m, std::pair<int,int> value) 
{
    std::map<int,int>::iterator it = m.find(value);
    if ( it != m.end()) //found or not?
           it.second += value; //add if found
    else
    {
           m.insert(value); //insert if not found
    }
}

Но это слишком, не правда ли? Это производительность не хорошо. Более ранний вариант более лаконичен и очень производителен.

Answer 4

вы можете использовать MAP ведьма имеет очень быстрый доступ к вашему элементу, если у вас есть ключ.в этом случае я думаю, что использование MAP было бы лучшим способом достижения максимальной скорости.STD :: MAP