Обновление C ++ std :: set утомительно: я не могу изменить элемент на месте

Question

Я нахожу операцию обновления на std::set утомительной, поскольку на cppreference такого API нет. Так что я сейчас делаю что-то вроде этого:

//find element in set by iterator
Element copy = *iterator;
... // update member value on copy, varies
Set.erase(iterator);
Set.insert(copy);

Как правило, возвращаемое итератором значение Set равно const_iterator, и вы не можете изменить его значение напрямую.

Есть ли лучший способ сделать это? Или, может быть, я должен переопределить std::set, создав свой собственный (который я не знаю точно, как это работает ..)

Answer 1

set возвращает const_iterators (согласно стандарту set<T>::iterator равно const, и что set<T>::const_iterator и set<T>::iterator на самом деле могут быть одного типа - см. 23.2.4 / 6 в n3000.pdf) потому что это заказанный контейнер. Если бы он возвращал обычное значение iterator, вам было бы разрешено изменить значение элементов из-под контейнера, что потенциально может изменить порядок.

Ваше решение - идиоматический способ изменения предметов в set.

Answer 2

В простом случае это можно сделать двумя способами:

• Вы можете использовать mutable для переменной, которая не является частью ключа
• Вы можете разделить ваш класс на пару Key Value (и использовать std::map)

Теперь вопрос для хитрого случая: что происходит, когда обновление фактически изменяет часть key объекта? Ваш подход работает, хотя я признаю, что это утомительно.

Answer 3

Обновление: Хотя на настоящий момент верно следующее, поведение считается дефектом и будет изменено в следующей версии стандарта. Как очень грустно.

---

Есть несколько моментов, которые делают ваш вопрос довольно запутанным.

1. Функции могут возвращать значения, классы - нет. std::set является классом, и поэтому не может ничего вернуть.
2. Если вы можете позвонить s.erase(iter), то iter не является const_iterator. erase требуется неконстантный итератор.
3. Все функции-члены std::set, которые возвращают итератор, возвращают неконстантный итератор, если набор также неконстантен.

Вам разрешено изменять значение элемента набора, если обновление не меняет порядок элементов. Следующий код компилируется и работает просто отлично.

#include <set>

int main()
{
    std::set<int> s;
    s.insert(10);
    s.insert(20);

    std::set<int>::iterator iter = s.find(20);

    // OK
    *iter = 30;

    // error, the following changes the order of elements
    // *iter = 0;
}

Если ваше обновление меняет порядок элементов, вам нужно стереть и заново вставить.

Answer 4

В C ++ 17 вы можете добиться большего успеха с extract(), благодаря P0083 :

// remove element from the set, but without needing
// to copy it or deallocate it
auto node = Set.extract(iterator);
// make changes to the value in place
node.value() = 42;
// reinsert it into the set, but again without needing 
// to copy or allocate
Set.insert(std::move(node));

Это позволит избежать дополнительной копии вашего типа и дополнительного выделения / освобождения, а также будет работать с типами только для перемещения.

Вы также можете extract по ключу. Если ключ отсутствует, будет возвращен пустой узел:

auto node = Set.extract(key);
if (node) // alternatively, !node.empty()
{
    node.value() = 42;
    Set.insert(std::move(node));
}

Answer 5

Вместо этого вы можете использовать std::map. Используйте часть Element, которая влияет на порядок ключей, и укажите все Element в качестве значения. Будет небольшое дублирование данных, но у вас будут более простые (и, возможно, более быстрые) обновления.

Answer 6

Я столкнулся с той же проблемой в C ++ 11, где действительно ::std::set<T>::iterator является константой и, следовательно, не позволяет изменять его содержимое, даже если мы знаем, что преобразование не повлияет на инвариант <. Вы можете обойти это, обернув ::std::set в тип mutable_set или написать оболочку для содержимого:

  template <typename T>
  struct MutableWrapper {
    mutable T data;
    MutableWrapper(T const& data) : data(data) {}
    MutableWrapper(T&& data) : data(data) {}
    MutableWrapper const& operator=(T const& data) { this->data = data; }
    operator T&() const { return data; }
    T* operator->() const { return &data; }
    friend bool operator<(MutableWrapper const& a, MutableWrapper const& b) {
      return a.data < b.data;
    }   
    friend bool operator==(MutableWrapper const& a, MutableWrapper const& b) {
      return a.data == b.data;
    }   
    friend bool operator!=(MutableWrapper const& a, MutableWrapper const& b) {
      return a.data != b.data;
    }   
  };

Я считаю, что это намного проще, и это работает в 90% случаев, когда пользователь даже не замечает, что есть что-то между набором и фактическим типом.

Answer 7

В некоторых случаях это быстрее:

std::pair<std::set<int>::iterator, bool> result = Set.insert(value);
if (!result.second) {
  Set.erase(result.first);
  Set.insert(value);
}

Если значение обычно отсутствует в std::set, это может повысить производительность.