Изменение значения определенного пользователем типа в `std :: set` - PullRequest
Новая
       103

Изменение значения определенного пользователем типа в `std :: set`

1 голос
/ 10 февраля 2020

Рассмотрим случай, когда у меня есть пользовательский тип, скажем, с id() функцией-членом, которая возвращает уникальный std::string.

. Я хочу контейнер с этими объектами, где id() однозначно идентифицирует элементы, но я хочу «использовать» объекты, чтобы делать другие вещи, которые могут изменять их члены.

В настоящее время я создаю objects.by, вызывая std::set::emplace и захватывая возвращенный итератор, bool pair.

Но тогда мне не разрешено изменять его значение, поскольку итератор является константой.

Есть ли хороший способ сделать то, что я хочу? Единственные два, о которых я могу думать:

  1. Сохранить unique_ptr s для объекта в set, таким образом, значение указателя - это то, что отличает его, а не имя и объект, на который указывает могут быть изменены.
  2. Сохраните map, используя id() в качестве Ключа, но это означает, что я продублировал ключи.

Я счастлив использовать хорошо принятые и современные библиотеки, такие как boost, если у них есть подходящий контейнер для моей проблемы.

Ответы [ 3 ]

1 голос
/ 11 февраля 2020

Есть ли хороший способ сделать то, что я хочу?

Нет, не совсем. Гранулярность std::set находится на уровне объекта. express невозможно, чтобы часть объекта вносила вклад в ключ.

Некоторые люди рекомендуют объявлять все неключевые элементы mutable. Это неправильно, так как mutable предназначен для вещей, которые скрыты от интерфейса объекта publi c (например, мьютекс).

"Официальный" способ - вывести объект из набора , измените его и вставьте обратно. C ++ 17 имеет set::extract, что немного улучшает производительность этой задачи (что, конечно, остается неэффективным, если вы никогда не модифицируете ключ, так как дерево все еще должен быть проверен / перебалансирован).

Я хочу "использовать" объекты для выполнения других действий, которые могут изменить их элементы.

Если вы абсолютно уверены, что никогда не изменяете ключ объекта, просто отбросьте const ness. С юридической точки зрения нормально отбрасывать постоянство от объектов, которые не родились const. Для дополнительной безопасности вы можете заключить ключ в другой член const: 

struct Element {
    const Key key;
    Value value;
};

Это не поможет, если у вас есть куб данных с несколькими наборами, каждый из которых использует свое собственное «представление» ключа.

1. Сохраните unique_ptr s для объекта в set

Это будет пессимизацией из-за дополнительного косвенного обращения. Так как элементы находятся в куче, вы получите дополнительную потерю кеша. И снова получите UB, если вы случайно измените ключ.

2. Сохраните map, используя id() в качестве ключа

Да, возможны различные варианты этого подхода, но вы все равно должны убедиться, что никогда не модифицируете ключ.

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

1 голос
/ 11 февраля 2020

Я бы предложил использовать Boost.MultiIndex в качестве замены для std::set, так как он добавляет метод modify, который позволяет модифицировать элемента, проверяющего, изменилась ли позиция в контейнере: 

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>

struct S { /* ... */ };
boost::multi_index_container<S> t; // default configuration emulates std::set<S>
auto [it, inserted] = t.emplace(...);
t.modify(it, [&](S& s) {
    // modify s here
    // if the key is unchanged, s does not move
    // the iterator `it` remains valid regardless
});

Пример .

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

0 голосов
/ 11 февраля 2020

std::set поддерживает сортировку своих элементов, а клавиши , по которым отсортированы элементы, соответствуют самим элементам. В результате элементы в std::set квалифицированы как const, чтобы пользователь не мог изменить элементы (то есть ключи) и тем самым нарушить порядок std::set.

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

Начиная с C ++ 17 вы можете удалять и повторно вставлять элемент в std::set без выделения внутреннего узла std::set благодаря std::set::extract(). Эта функция-член возвращает дескриптор узла, соответствующий запрошенному элементу. После изменения элемента через этот возвращенный узел вы можете повторно вставить узел с соответствующей перегрузкой insert(). При повторном использовании уже выделенного узла выделение узлов не происходит.

Недостаток этих подходов - независимо от того, происходит ли выделение - состоит в том, что повторная вставка элемента в std::set занимает логарифмическое c время в размере набора (если вы не можете воспользоваться подсказкой до insert()).

Отбрасывание констант и изменение std::set элементов

Вы можете по-прежнему отбрасывайте const от элемента std::set и изменяйте его элементы данных, если функция сравнения std::set не учитывает элементы данных, которые вы изменяете. То есть, если вы изменяете только элементы данных элемента, принадлежащего std::set, функция сравнения которого не учитывает, порядок не будет нарушен.

...