unordered_set of shared_ptr не находит эквивалентные объекты, которые он сохранил

Question

У меня есть класс, в котором хранится std::vector вещей.В моей программе я создаю std::unordered_set из std::shared_ptr для объектов этого класса (см. Код ниже).Я определил пользовательские функции для вычисления хэшей и равенства, чтобы unordered_set «работал» с объектами вместо указателей.Это означает: два разных указателя на разных объектов, которые имеют одинаковое содержимое, должны рассматриваться как равные, назовем его "эквивалентным".

Пока все работало, как и ожидалось, но теперь я наткнулся на странное поведение: я добавляю указатель на объект к unordered_set и создаю другой указатель на другой объект с тем же содержимым.Как уже было сказано, я ожидаю, что my_set.find(different_object) вернет действительный итератор к эквивалентному указателю, хранящемуся в наборе.Но это не так.

---

Вот пример минимального рабочего кода.

#include <boost/functional/hash.hpp>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <memory>
#include <unordered_set>
#include <vector>

class Foo {
public:
    Foo() {}
    bool operator==(Foo const & rhs) const {
        return bar == rhs.bar;
    }
    std::vector<int> bar;
};

struct FooHash {
    size_t operator()(std::shared_ptr<Foo> const & foo) const {
        size_t seed = 0;
        for (size_t i = 0; i < foo->bar.size(); ++i) {
            boost::hash_combine(seed, foo->bar[i]);
        }
        return seed;
    }
};

struct FooEq {
    bool operator()(std::shared_ptr<Foo> const & rhs, 
                    std::shared_ptr<Foo> const & lhs) const {
        return *lhs == *rhs;
    }
};

int main() {
    std::unordered_set<std::shared_ptr<Foo>, FooHash, FooEq> fooSet;
    auto empl = fooSet.emplace(std::make_shared<Foo>());
    (*(empl.first))->bar.emplace_back(0);

    auto baz = std::make_shared<Foo>();
    baz->bar.emplace_back(0);

    auto eqFun = fooSet.key_eq();
    auto hashFun = fooSet.hash_function();

    if (**fooSet.begin() == *baz) {
        std::cout << "Objects equal" << std::endl;
    }
    if (eqFun(*fooSet.begin(), baz)) {
        std::cout << "Keys equal" << std::endl;
    }
    if (hashFun(*fooSet.begin()) == hashFun(baz)) {
        std::cout << "Hashes equal" << std::endl;
    }
    if (fooSet.find(baz) != fooSet.end()) {
        std::cout << "Baz in fooSet" << std::endl;
    } else {
        std::cout << "Baz not in fooSet" << std::endl;
    }

    return 0;
}

Вывод

Objects equal
Keys equal
Hashes equal

И вот в чем проблема:

Baz not in fooSet

---

Чего мне здесь не хватает?Почему набор не находит эквивалентный объект?

Возможно, интерес: я поэкспериментировал с этим и обнаружил, что если мой класс хранит обычный int вместо std::vector, он работает.Если я придерживаюсь std::vector, но меняю свой конструктор на

Foo(int i) : bar{i} {}

и инициализирую свои объекты с

std::make_shared<Foo>(0);

, это также работает.Если я удаляю весь указатель, он ломается, так как std::unordered_set::find возвращает константы-итераторы, и, таким образом, модификация объектов в наборе невозможна (таким образом).Тем не менее, ни одно из этих изменений не применимо в моей реальной программе, так или иначе.

Я компилирую с g++ версии 7.3.0, используя -std=c++17

Answer 1

Любая операция, в результате которой результат хеширования или == элемента в unordered_set нарушает правила unordered_set, неверен;результат - неопределенное поведение.

Вы изменили результат хэша элемента в unordered_set, потому что ваши элементы являются общими указателями, но их хеш и == основаны на значении, указанном для,И ваш код меняет значение, указанное на.

Сделайте все std::shared_ptr<Foo> в вашем коде std::shared_ptr<Foo const>.

Это включает в себя равные и хэш-код и неупорядоченный код набора.

auto empl = fooSet.emplace(std::make_shared<Foo>());
(*(empl.first))->bar.emplace_back(0);

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

Если вы хотите преобразовать элемент в fooSet,

template<class C, class It, class F>
void mutate(C& c, It it, F&& f) {
  auto e = *it->first;
  f(e); // do this before erasing, more exception-safe
  auto new_elem = std::make_shared<decltype(e)>(std::move(e));
  c.erase(it);
  c.insert( new_elem ); // could throw, but hard to avoid.
}

теперь код читает:

auto empl = fooSet.emplace(std::make_shared<Foo>());
mutate(fooSet, empl.first, [&](auto&& elem) {
  elem.emplace_back(0);
});

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

Конечно, в этом случае он тупой;мы просто вставляем его, а теперь вынимаем, изменяем и возвращаем обратно.

Но в более общем случае это будет менее глупо.

Answer 2

Здесь вы добавляете объект, и он сохраняется с использованием текущего значения хеш-функции.

auto empl = fooSet.emplace(std::make_shared<Foo>());

Здесь вы меняете значение хеш-функции:

(*(empl.first))->bar.emplace_back(0);

В наборе теперь объект хранится с использованиемстарое / неправильное хеш-значение.Если вам нужно изменить что-либо в объекте, что влияет на его хеш-значение, вам нужно извлечь объект, изменить его и заново вставить.Если все изменяемые члены класса используются для вычисления значения хеша, вместо этого сделайте для него набор <const Foo>.

Чтобы упростить будущие объявления наборов shared_ptr<const Foo>, выможет также расширить пространство имен std вашими специализациями.

class Foo {
public:
    Foo() {}
    size_t hash() const {
        size_t seed = 0;
        for (auto& b : bar) {
            boost::hash_combine(seed, b);
        }
        return seed;
    }
    bool operator==(Foo const & rhs) const {
        return bar == rhs.bar;
    }
    std::vector<int> bar;
};

namespace std {
    template<>
    struct hash<Foo> {
        size_t operator()(const Foo& foo) const {
            return foo.hash();
        }
    };
    template<>
    struct hash<std::shared_ptr<const Foo>> {
        size_t operator()(const std::shared_ptr<const Foo>& foo) const {
            /* A version using std::hash<Foo>:
            std::hash<Foo> hasher;
            return hasher(*foo);
            */
            return foo->hash();
        }
    };
    template<>
    struct equal_to<std::shared_ptr<const Foo>> {
        bool operator()(std::shared_ptr<const Foo> const & rhs,
                        std::shared_ptr<const Foo> const & lhs) const {
            return *lhs == *rhs;
        }
    };
}

Имея это в виду, вы можете просто объявить свой unordered_set следующим образом:

std::unordered_set<std::shared_ptr<const Foo>> fooSet;

, который теперь аналогичен объявлению егокак это:

std::unordered_set<
    std::shared_ptr<const Foo>,
    std::hash<std::shared_ptr<const Foo>>,
    std::equal_to<std::shared_ptr<const Foo>>
> fooSet;

Answer 3

Вы не можете изменить элемент набора (и ожидать, что набор будет работать).Поскольку вы предоставили FooHash и FooEq, которые проверяют значение референта, это делает референт частью значения с точки зрения набора!

Если мы измениминициализация fooSet для установки элемента перед вставкой его, мы получаем желаемый / ожидаемый результат:

std::unordered_set<std::shared_ptr<Foo>, FooHash, FooEq> fooSet;
auto e = std::make_shared<Foo>();
e->bar.emplace_back(0);  // modification is _before_
fooSet.insert(e);        // insertion

Поиск объекта в наборе зависит от значения хеш-функциине меняетсяЕсли нам действительно нужно изменить члена после его добавления, нам нужно удалить его, внести изменения, а затем добавить измененный объект - см. ответ Якка .

Чтобы избежать столкновения сПодобные проблемы могут быть более безопасными при использовании std::shared_ptr<const Foo> в качестве элементов, что предотвратит изменение наведенного на Foo набора (хотя вы по-прежнему несете ответственность за использование любых неконстантных указателей, вы также можетеесть).