使用std :: unordered_set的std :: unique_ptr

Question

假设我有一组unique_ptr:

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

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

我从外面得到的只是一个原始指针.所以我必须从指针创建另一个unique_ptr,将它传递给find()然后release()指针,否则对象将被破坏(两次).当然,这个过程可以在一个函数中完成,因此调用者可以传递原始指针并进行转换.

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

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

实例.

Answer 2

请注意,在标准容器上执行异构查找的能力是一些提议的主题.

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

• N3465为TR2(Rev 2)的关联容器添加异构比较查找[使用N3573处理]
• N2882 id.
• N3573无序容器的异质扩展[N3465处理]

特别是后者看起来会覆盖你的用例.

目前,这里有一个IMO不是很漂亮,但工作替代解决方法(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;
}

警告当然,这也是非常低效的.

Answer 3

您可以使用std::map<MyClass*, std::unique_ptr<MyClass>>而不是集合.然后你可以添加这样的元素:

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

Answer 4

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

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

否则,如果您可以接受O(lg n)访问,而不是持续访问(差异通常在表格相当大之前不会变得明显),您可以使用a std::vector<MyClass>,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 );
    }
};

插入可能涉及许多移动,但移动a std::unique_ptr应该相当便宜,并且此解决方案的改进的局部性可能抵消其另外施加的额外运行时成本.