3

我有一个类，它需要一个std::unordered_set包含不可复制、不可移动的实体对象，并且其哈希函数对实例的地址进行哈希处理。类似于以下内容：

class A
{
public:
    A();
    A(const A&) = delete;
    A(A&&) = delete;
    void operator=(const A&) = delete;
    void operator=(A&&) = delete;

    bool operator==(const A& other) { return this == &other; }
};

template<>
struct std::hash<A>
{
    size_t operator()(const A& obj) const
    {
        return std::hash<A*>()(&obj);
    }
};

class B
{
private:
    std::unordered_set<A> entities;
};

如果emplace()总是使用而不是insert()，以这种方式使用是否安全unordered_set？标准是否指定实现在构造节点对象后不能移动它们？

如果A是可移动的呢？是否保证将在集合拥有的对象上调用散列函数，或者由于标准库更喜欢将所有内容视为值对象，是否允许在为inserted 对象分配存储之前对其进行散列？

作为最后的想法，我知道我可以通过使用来解决所有这些问题std::unordered_set<std::unique_ptr<A>>，但我想为A对象使用自定义分配器，并且我不想覆盖new和deletefor A。

4

3 回答 3

2

使用对象的地址作为哈希几乎可以保证您不会找到该对象，除非您已经持有指向该对象的指针，而不是通过哈希进行迭代。您需要想出一种不同的方法来从您的对象中获取哈希值。也就是说，一旦在散列中构建，对象的地址就不会改变。

于 2013-10-13T17:13:14.900 回答
1

我仍然认为您最好使用std::list. 考虑：

#include <iostream>
#include <list>

class A
{
public:
    int i_;
    A(int i) : i_(i) {}
    A(const A&) = delete;
    A(A&&) = delete;
    void operator=(const A&) = delete;
    void operator=(A&&) = delete;
};

int main()
{
    std::list< A > l;

    // inserting elements
    auto it1 = l.emplace( l.end(), 1 ); // note: complexity is O(1)
    auto it2 = l.emplace( l.end(), 2 );
    auto it3 = l.emplace( l.end(), 3 );
    auto it4 = l.emplace( l.end(), 4 );

    // deleting an element by iterator
    l.erase( it2 ); // note: complexity is O(1)
    // note: it2 is now invalid

    // accessing element by iterator
    it3->i_ = 42;

    for( const auto& e : l ) {
        std::cout << e.i_ << std::endl;
    }

    // silence compiler warnings
    (void)it1;
    (void)it4;
}

在上面，您的所有用例都应该有一个有效的实现。您可以避免计算哈希和拥有哈希映射的开销。作为基于散列的方法，它甚至更有效，因为列表的两个操作都是 O(1) 并且实现起来更轻量级。并且存储迭代器与直接存储指向元素的指针没有太大区别。

此外，保证这适用于不可复制和不可移动的类型。请参阅std::list::emplace.

于 2013-10-14T09:51:28.933 回答
0

正如 Dietmar 所提到的，一旦构建，值的地址就不能改变。至于问题的第二部分，该标准似乎不仅允许，而且要求实现在insert()通过引用传递的对象上调用 hash/equal_to 函子，而不是要求首先构建节点并调用函数那个对象：

来自 23.2.5 表 103——无序关联容器要求

pair<iterator, bool> a_uniq.insert(t)

效果：t当且仅当容器中没有与 的键等效的元素时才插入t。

于 2013-10-13T18:39:59.347 回答