33

假设我有一组 unique_ptr：

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

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

我从外面得到的只是一个原始指针。find()所以我必须从指针创建另一个 unique_ptr ，然后将其传递给release()该指针，否则对象将被破坏（两次）。当然，这个过程可以在一个函数中完成，所以调用者可以传递原始指针，我来做转换。

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

4

6 回答 6

28

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

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));

活生生的例子。

于 2013-07-25T09:14:25.657 回答
13

请注意，对标准容器进行异构查找的能力是一些提议的主题。

http://cplusplus.github.io/LWG/lwg-proposal-status.html列表

  • N3465将异构比较查找添加到 TR2 的关联容器（修订版 2）[使用 N3573 处理]
  • N2882编号。
  • N3573对无序容器的异构扩展 [使用 N3465 处理]

特别是后者看起来会涵盖您的用例。

现在，这是一个不太漂亮但可行的替代解决方法 (O(n)) 的 IMO：

#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;
}

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

于 2013-07-25T08:01:47.633 回答
10

您可以使用 astd::map<MyClass*, std::unique_ptr<MyClass>>而不是 set。然后你可以添加这样的元素：

 std::unique_ptr<MyClass> instance(new MyClass);
 map.emplace(instance.get(), std::move(instance));
于 2013-07-25T07:04:30.983 回答
7

如果目标是查找的恒定时间，我认为没有解决方案。 std::unordered_set<std::unique_ptr<MyClass>>::find需要一个 std::unique_ptr<MyClass>as 参数。您将不得不更改容器或更改包含的类型。

一种可能性可能是替换std::unique_ptr为 std::shared_ptr，并更改其余代码，以便 MyClass在创建后立即将所有代码放入 shared_ptr 中，并且仅通过共享指针进行操作。从逻辑上讲，无论如何这可能更加连贯：unique_ptr几乎暗示（通过它的名称以及它的语义）没有其他指向该对象的指针。另一方面，您可能无法使用 shared_ptr，如果例如MyClass有指向 other的指针MyClass，这可能会建立一个循环。

否则，如果您可以接受 O(lg n) 访问，而不是恒定访问（在表相当大之前差异通常不会变得明显），您可以使用 std::vector<MyClass>, usingstd::lower_bound来保持排序。与 不同，std::unordered_set<>::find不std::lower_bound 要求目标值 与序列的类型相同；您所要做的就是确保它们具有可比性，例如通过提供以下内容的对象：value_typeCompare

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 );
    }
};

插入可能涉及许多移动，但移动 astd::unique_ptr应该相当便宜，并且该解决方案改进的局部性可能会抵消它所带来的额外运行时成本。

于 2013-07-25T08:42:03.150 回答
1

如果您可以使用Abseil，请执行以下操作：

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

只是工作:)

于 2021-10-08T13:00:55.870 回答
0

这是在 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

于 2021-10-08T13:09:51.247 回答