使用std::unique_ptr的std::unordered_set

Question

假设我有一组 unique_ptr：

std::unordered_set <std::unique_ptr <MyClass>> my_set;

我不确定如何安全地检查集合中是否存在给定指针。通常的方法可能是调用my_set.find()，但我应该传递什么参数？

从外部获取到的只有一个原始指针。因此，我必须创建另一个unique_ptr来自指针，将其传递给find()，然后释放该指针，否则对象会被析构（两次）。当然，这个过程可以在函数中完成，这样调用者就可以传递原始指针，我进行转换。

这种方法安全吗？是否有更好的方法来处理一组unique_ptr？

- cfa45ca55111016ee9269f0a52e771

---

谢谢。我不需要移动或复制任何东西，所以unique_ptr可以。我只需要让调用者给我一个原始指针，并且我需要检查集合中是否存在匹配的unique_ptr。 - cfa45ca55111016ee9269f0a52e771

unique_ptr 显然不是你需要的，因为你明显有指向该对象的其他指针。 - James Kanze

unique_ptr 的所有者是内存的唯一所有者，其他所有人只是持有引用。我可以在所有者中使用 shared_ptr，而在其他地方使用 weak_ptr，但这样每个对象都会被一个共享的 shared_ptr 引用。我不需要共享，只需要一个单独的所有者。 - cfa45ca55111016ee9269f0a52e771

我认为 std::unique_ptr 并不一定是某个对象的唯一指针。"unique"并不是指唯一地址，而是指独自拥有。一个不拥有其所指对象的std::shared_ptr是更严重的正确性问题。 - Christian Rau

不是重复的问题。链接的问题要求使用 set，而这个问题要求使用 unordered_set，这是一个很大的区别。 - IS4

同意@IllidanS4的观点。set对于find()有透明的比较器，而unordred_set则没有。 - Mikhail

Answer 1

您可以使用一个可选不执行任何操作的删除器。

template<class T>
struct maybe_deleter{
  bool _delete;
  explicit maybe_deleter(bool doit = true) : _delete(doit){}

  void operator()(T* p) const{
    if(_delete) delete p;
  }
};

template<class T>
using set_unique_ptr = std::unique_ptr<T, maybe_deleter<T>>;

template<class T>
set_unique_ptr<T> make_find_ptr(T* raw){
    return set_unique_ptr<T>(raw, maybe_deleter<T>(false));
}

// ...

int* raw = new int(42);
std::unordered_set<set_unique_ptr<int>> myset;
myset.insert(set_unique_ptr<int>(raw));

auto it = myset.find(make_find_ptr(raw));

现场演示。

这是一个现场演示的链接。

- Xeo

---

我会考虑在这里使用隐式构造函数，这样你就可以使用set_unique_ptr<T>(raw, false)。你有什么想法？（我知道我知道。隐式转换很“邪恶”。但是，具体来说，对于这个特定的用例，有什么问题吗？） - sehe

虽然我喜欢你的解决方案，但我仍然认为它是一个hack。 - Tanveer Badar

Answer 2

请注意，在标准容器上执行异构查找的能力是一些提案的主题。 http://cplusplus.github.io/LWG/lwg-proposal-status.html 列出了：

- N3465 向关联容器添加异构比较查找以用于TR2（Rev 2）[与N3573一起处理] - N2882 id。 - N3573 无序容器的异构扩展 [与N3465一起处理]

特别是后者看起来似乎可以涵盖您的用例。

目前，这里有一个我认为不太美观但有效的替代解决方法（O(n)）：

#include <iterator>
#include <iostream>
#include <algorithm>

#include <unordered_set>
#include <memory>

#include <cassert>

struct MyClass {};

template <typename T>
struct RawEqualTo
{
    RawEqualTo(T const* raw) : raw(raw) {}

    bool operator()(T const* p) const  
        { return raw == p; }
    bool operator()(std::unique_ptr<T> const& up) const  
        { return raw == up.get(); }

  private:
    T const* raw;
};


using namespace std;
int main()
{
    std::unordered_set <std::unique_ptr <MyClass>> my_set;

    my_set.insert(std::unique_ptr<MyClass>(new MyClass));
    my_set.insert(std::unique_ptr<MyClass>(new MyClass));

    auto raw = my_set.begin()->get();

    bool found = end(my_set) != std::find_if(begin(my_set), end(my_set), RawEqualTo<MyClass>(raw));
    assert(found);

    raw = new MyClass;

    found = end(my_set) != std::find_if(begin(my_set), end(my_set), RawEqualTo<MyClass>(raw));
    assert(!found);

    delete raw;
}

警告 当然，这也非常低效。

- sehe

---

@ChristianRau 但显然它是共享的，因为容器外部明显有指向对象的指针。 - James Kanze

@fr33domlover 我假设你不需要/不想要帮助实现你在问题中已经描述的解决方法 :/ 异构容器接口很酷，但也充满了陷阱。我希望我们能够理解它，但前提是他们必须_正确地_理解它。您可以在 iso-cpp.org 上关注一些讨论。 - sehe

@fr33domlover find 不应该抛出异常（除非哈希函数或比较函数抛出异常）。但是拥有两个指向同一对象的 unique_ptr 看起来像是一场灾难的配方，也是维护噩梦，因为它违反了 unique_ptr 的不变量。 - James Kanze

@JamesKanze 是的，但我在本地创建和释放指针。这并不比使用new和delete更危险，而且有时会意外删除对象。我在函数内部处理额外的指针，安全地，在创建和释放之间只需一次调用find()函数即可。 - cfa45ca55111016ee9269f0a52e771

@JamesKanze 只有在这些其他指针负责管理对象的生命周期(因此拥有它)时才需要使用。谁知道查找参数来自哪里，它不需要是一个持久存储的生命周期管理引用。我并不是说他可能不需要一个 std::shared_ptr，但仅仅是一个查找参数并不足以成为使用它的充分理由。 - Christian Rau

Answer 3

您可以使用 std::map<MyClass*， std::unique_ptr<MyClass>> 代替 set。这样您就可以像这样添加元素：

 std::unique_ptr<MyClass> instance(new MyClass);
 map.emplace(instance.get(), std::move(instance));

- petersohn

---

std::set有什么问题？在这种情况下，std::map不好用。关键字和值本质上是相同的对象！ - Nawaz

@Nawaz，unique_ptr拥有内存，而原始指针用于find()和所有其他按键搜索的方法。 - cfa45ca55111016ee9269f0a52e771

那么，您将如何解决“我只有原始指针时需要找到一个unique_ptr”的问题？该答案通过引入显式映射来解决这个问题。请注意，std :: [unrodered_] set是OP当前拥有的，并且正在询问如何进行搜索。 - Angew is no longer proud of SO

std::unordered_set::find 的时间复杂度是 O(1)，而 std::find_if 的时间复杂度是 O(n)。这可能会很快地产生差异。 - James Kanze

@petersohn 如果你需要修改代码或进行任何形式的维护，使用release()方法是不安全的。无论是否有异常发生，这都是在对编译器和任何阅读代码的人撒谎。 - James Kanze

Answer 4

如果目标是实现常数时间的查找，我认为这是不可能的。std::unordered_set>::find需要一个std::unique_ptr类型的参数。你将不得不更改容器或更改包含的类型。 一种可能是用std::shared_ptr替换std::unique_ptr，并改变其余代码，以便所有MyClass在创建时都放入shared_ptr中，并且仅通过共享指针进行操作。从逻辑上讲，这可能更加一致：unique_ptr几乎意味着（通过其名称和语义）没有其他指向对象的指针。另一方面，如果MyClass有指向其他MyClass的指针（可能会构成循环），则可能无法使用shared_ptr。 否则，如果您可以接受O(lg n)的访问而非常数访问（差异通常不会显著，直到表变得相当大），则可以使用std::vector来保持其排序，使用std::lower_bound进行访问。与std::unordered_set<>::find不同，std::lower_bound不需要目标值具有与序列的value_type相同的类型；您需要做的就是确保它们是可比较的，例如通过提供类似以下内容的Compare对象：

class MyClassPtrCompare
{
    std::less<MyClass const*> cmp;
public:
    bool operator()( std::unique_ptr<MyClass> const& lhs,
                     std::unique_ptr<MyClass> const& rhs ) const
    {
        return cmp( lhs.get(), rhs.get() );
    }
    bool operator()( MyClass const* lhs,
                     std::unique_ptr<MyClass> const& rhs ) const
    {
        return cmp( lhs, rhs.get() );
    }
    bool operator()( std::unique_ptr<MyClass> const& lhs,
                     MyClass const* rhs ) const
    {
        return cmp( lhs.get(), rhs );
    }
    bool operator()( MyClass const* lhs,
                     MyClass const* rhs ) const
    {
        return cmp( lhs, rhs );
    }
};

插入可能涉及多次移动，但移动std::unique_ptr应该相当便宜，而此解决方案的改进局部性可能抵消了它否则会施加的额外运行时成本。

- James Kanze

---

+1 看起来是一个不错的妥协。奇怪的是，没有一个“find_if”的支持者考虑过这一点（但好吧，我自己也没想到）。 - Christian Rau

@fr33domlover，不过实际上那个排序好的向量表现得很好，你可能会感到惊讶。 - Christian Rau

使用std::vector是一个很好的替代方案。它比std::set使用更少的内存。这让我想起了这篇文章：为什么你不应该使用set（以及你应该使用什么）。 - Nawaz

根据经验，你可能会发现已排序向量的O(lg n)时间复杂度优于无序集合的O(1)时间复杂度，这是因为已排序向量具有更好的局部性。 - James Kanze

@ChristianRau 哦，我想到了。但是，显然这不是问题的关键。此外，我建议使用“平存储集”，但前提是您重用现有的实现。http://www.boost.org/doc/libs/1_54_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx - sehe

Answer 5

如果你可以使用Abseil，就这样做：

absl::flat_hash_set<std::unique_ptr<MyClass>> my_set;

只是工作了 :)

- Mikhail

Answer 6

以下是使用C++20中可用的“无序容器的异构查找”正确的方法：

struct Hash {
  using is_transparent = void;
  template <class P>
  size_t operator()(const P& p) const {
    return std::hash<P>{}(p);
  }
};
struct KeyEqual {
  using is_transparent = void;
  template <class P, class Q>
  bool operator()(const P& lhs, const Q& rhs) const {
    return std::to_address(lhs) == std::to_address(rhs);
  }
};

std::unordered_set<std::unique_ptr<MyClass>, Hash, KeyEqual> my_set;

更多关于该主题的内容（俄语）：https://www.coursera.org/learn/c-plus-plus-brown/supplement/TtrLN/unordered-set-unique-ptr

- Mikhail