针对unique_ptr集合的原始指针查找

Question

我经常发现自己想要编写这样的代码：

class MyClass
{
public:
  void addObject(std::unique_ptr<Object>&& newObject);

  void removeObject(const Object* target);

private:
  std::set<std::unique_ptr<Object>> objects;
};

然而，对于使用std::unique_ptrs的情况，std::set接口的大部分功能都有些无用，因为查找函数需要std::unique_ptr参数（我显然没有它们，因为它们由集合本身拥有）。

我可以想到两种主要解决方案。

1. 为查找创建一个临时的unique_ptr。例如，上面的removeObject()可以这样实现：

void MyClass::removeObject(const Object* target)
{
  std::unique_ptr<Object> targetSmartPtr(target);
  objects.erase(targetSmartPtr);
  targetSmartPtr.release();
}

用指向unique_ptrs的原始指针的map替换集合。

  // ...
  std::map<const Object*, std::unique_ptr<Object>> objects;
};

然而，对我来说两种解决方案都有些愚蠢。在第一种解决方案中，erase（）不是noexcept的，因此临时unique_ptr可能会删除它实际上并未拥有的对象，2需要不必要地为容器提供双倍的存储空间。

我知道Boost的指针容器，但它们当前的功能与现代C++11标准库容器相比有限。

最近我在阅读C++14，发现了“向关联容器添加异构比较查找”。但从我的理解上看，查找类型必须可以与键类型进行比较，但裸指针不能与unique_ptrs进行比较。

是否有人知道更优雅的解决方案或即将添加到C++的解决此问题的新功能？

- jbatez

---

有趣的是，这似乎是容器类中的设计疏忽 - 应该有一种简单的方法来实现这个。 - Konrad Rudolph

同意。或许应该有一些类似于Yakk的pointer_comp的东西，如std::ptr_less、std::ptr_equal_to、std::ptr_hash等，来简化指针比较和查找。它们将与C++1y的异构比较查找相结合，使关联容器更加方便。 - jbatez

题外话：你不应该通过 rvalue 引用来获取 unique pointer；直接通过值传递就足够了。 - Kerrek SB

使用自定义的std::set比较器。相关链接：https://dev59.com/c3E85IYBdhLWcg3wwWet。 - Ciro Santilli OurBigBook.com

Answer 1

在C++14中，如果存在Compare::is_transparent，std::set<Key>::find是一个template函数。您传入的类型不需要是Key，只需在比较器下等效即可。

因此，编写一个比较器：

template<class T>
struct pointer_comp {
  typedef std::true_type is_transparent;
  // helper does some magic in order to reduce the number of
  // pairs of types we need to know how to compare: it turns
  // everything into a pointer, and then uses `std::less<T*>`
  // to do the comparison:
  struct helper {
    T* ptr;
    helper():ptr(nullptr) {}
    helper(helper const&) = default;
    helper(T* p):ptr(p) {}
    template<class U, class...Ts>
    helper( std::shared_ptr<U,Ts...> const& sp ):ptr(sp.get()) {}
    template<class U, class...Ts>
    helper( std::unique_ptr<U, Ts...> const& up ):ptr(up.get()) {}
    // && optional: enforces rvalue use only
    bool operator<( helper o ) const {
      return std::less<T*>()( ptr, o.ptr );
    }
  };
  // without helper, we would need 2^n different overloads, where
  // n is the number of types we want to support (so, 8 with
  // raw pointers, unique pointers, and shared pointers).  That
  // seems silly:
  // && helps enforce rvalue use only
  bool operator()( helper const&& lhs, helper const&& rhs ) const {
    return lhs < rhs;
  }
};

然后使用它：

typedef std::set< std::unique_ptr<Foo>, pointer_comp<Foo> > owning_foo_set;

现在，owning_foo_set::find将接受unique_ptr<Foo>或Foo*或shared_ptr<Foo>（或任何Foo的派生类）并找到正确的元素。

在C++14之外，您被迫使用map到unique_ptr的方法，或者类似的方法，因为find的签名过于严格。或编写自己的set等效物。

- Yakk - Adam Nevraumont

---

@ali std::lower_bound 在 set 迭代器上是线性的，没有随机访问。 - Yakk - Adam Nevraumont

+1。显然，如果不做出重大妥协，标准C++11容器无法实现这一点。要么某些东西在最坏情况下以线性时间运行，要么就需要使用OP中提到的解决方法。 - Ali

@JoBates 一个“透明”的哈希函数可能比一个“透明”的比较器要棘手一点，但在某些情况下非常有用：一个能够处理const char*缓冲区或std::string_view的std::string哈希函数可以在查找时节省分配。而且，“只有部分键实际上是键”这个概念也同样适用。 - Yakk - Adam Nevraumont

很棒的答案！我还在努力理解C++11，但似乎已经有了一个令人信服的理由来过渡到C++14。奇怪的是，unique_ptr + stl容器被各处赞誉为一种伟大的东西；我没有找到任何关于这个问题的提及，而我认为这是一个重大缺点。 - pauluss86

@Yakk: true; 我的意图是（为了讨论而称之为“Register”）作为一个“汇”，通过完全拥有传递给它的实例指针来实现。我的问题是：调用者（在他的初始指针超出范围后）如何在以后“注销”项目？如果Register使用一组unique_ptr，那么调用者必须有一个unique_ptr传递给Register以从集合中删除它。显然，这破坏了整个方案。因此，我选择了一个unordered_map：调用者可以按键删除项目。 - pauluss86

Answer 2

另一种可能性接近于被接受的答案，但有些不同并且更简化。

我们可以利用标准比较器std::less<>（没有模板参数）是透明的这个事实。然后，我们可以在全局命名空间中提供自己的比较函数：

// These two are enough to be able to call objects.find(raw_ptr)
bool operator<(const unique_ptr<Object>& lhs, const Object* rhs) {
  return std::less<const Object*>()(lhs.get(), rhs);
}
bool operator<(const Object* lhs, const unique_ptr<Object>& rhs) {
  return std::less<const Object*>()(lhs, rhs.get());
}

class MyClass
{
  // ...

private:
  std::set<std::unique_ptr<Object>, std::less<>> objects;  // Note std::less<> here
};

- Mikhail

Answer 3

您可以尝试使用带有Object*的额外索引的boost::multi_index_container。类似于这样：

typedef std::unique_ptr<Object> Ptr;
typedef multi_index_container<
  Ptr,
  indexed_by<
    hashed_unique<Ptr>,
    ordered_unique<const_mem_fun<Ptr,Object*,&Ptr::get> >
  >
> Objects;

更多信息请参见Boost Multi-index Containers文档

或者您可以在所有地方使用std::shared_ptr，或者在set中使用原始指针？

为什么需要通过原始指针查找？如果您在任何地方存储它并检查具有该指针的对象是否有效，则最好使用std::shared_ptr进行容器存储，使用std::weak_ptr进行其他对象。在这种情况下，在使用之前根本不需要通过原始指针查找。

- PSyton

---

我曾经认为你不能拥有一个unique_ptr的multi_index_container，因为它们会被复制。 - Jean-Simon Brochu

Answer 4

虽然这种方法有点取巧，但我刚意识到可以使用placement new构造一个临时的“愚蠢”的unique_ptr，而不会冒着被释放的风险。removeObject()可以像这样编写：

void MyClass::removeObject(const Object* target)
{
  alignas(std::unique_ptr<Object>)
  char dumbPtrData[sizeof(std::unique_ptr<Object>)];

  objects.erase(
      *::new (dumbPtrData) std::unique_ptr<Object>(const_cast<Object *>(target)));
}

这个解决方案适用于使用标准C++11的std::unordered_set、std::map键和std::unordered_map键，几乎没有不必要的开销。请注意保留HTML标签。

- jbatez

---

为了更准确，您需要使用 alignas 确保数组适合于 unique_ptr 对象。另一个选项是只使用 unique_ptr<Object> key(target); objects.erase(key); key.release(); ... 但是如果 Object 析构函数可能会抛出异常（无论如何都不好），则会出现双重删除，因此需要处理来自 erase 调用的异常。 - Jonathan Wakely

Answer 5

更新2:Yakk是正确的,在不做重大妥协的情况下，使用标准C++11容器没有办法做到这一点。要么某些东西会在最坏情况下以线性时间运行，要么就有那些你在问题中写的变通方法。

我考虑了两个解决方法。

我会尝试使用排序的std::vector，类似于boost::container::flat_set。 是的，在最坏情况下插入/删除将是线性时间。 仍然可能比你想象的要快得多：与基于节点的容器（例如std::set）相比，连续容器非常缓存友好。 请阅读boost::container::flat_set上写的内容。 是否接受此折衷方案，我无法判断/测量。

其他人也提到了std::share_ptr。我个人尽量避免使用它们，主要是因为“共享指针和全局变量一样好”（Sean Parent）。我不使用它们的另一个原因是它们很重，部分原因是由于所有多线程处理所带来的开销，而我通常不需要这些。然而，在定义了BOOST_SP_DISABLE_THREADS时，boost::shared_ptr会消除与多线程相关的所有开销。我相信在您的情况下使用boost::shared_ptr将是最简单的解决方案。

---

更新：正如Yakk友好地指出，我的方法具有线性时间复杂度... :(

---

---

（第一个版本。）

您可以通过向std::lower_bound()传递自定义比较器来实现。以下是一个简单的实现方式：

#include <algorithm>
#include <cassert>
#include <iostream>
#include <memory>
#include <set>
#include <string>

using namespace std;

template <typename T>
class Set {

private:

    struct custom_comparator {
        bool operator()(const unique_ptr<T>& a, const T* const & b){
            return a.get() < b;
        }
    } cmp;

    set<unique_ptr<T>> objects; // decltype at begin() and end()
                                // needs objects to be declared here
public:

    auto begin() const -> decltype(objects.begin()) { return objects.begin(); }

    auto   end() const -> decltype(objects.end()  ) { return objects.end();   }

    void addObject(unique_ptr<T>&& newObject) {

        objects.insert(move(newObject));
    }

    void removeObject(const T* target) {

        auto pos = lower_bound(objects.begin(), objects.end(), target, cmp);

        assert (pos!=objects.end()); // What to do if not found?

        objects.erase(pos);
    }
};

void test() {

    typedef string T;

    Set<T> mySet;

    unique_ptr<T> a{new T("a")};
    unique_ptr<T> b{new T("b")};
    unique_ptr<T> c{new T("c")};

    T* b_ptr = b.get();

    mySet.addObject(move(a));
    mySet.addObject(move(b));
    mySet.addObject(move(c));

    cout << "The set now contains: " << endl;

    for (const auto& s_ptr : mySet) {

        cout << *s_ptr << endl;
    }

    mySet.removeObject(b_ptr);

    cout << "After erasing b by the pointer to it:" << endl;

    for (const auto& s_ptr : mySet) {

        cout << *s_ptr << endl;
    }
}

int main() {

    test();
}

- Ali

Answer 6

你在这里使用了独特的指针。这意味着你的集合对对象具有唯一的所有权。现在，这应该意味着如果对象存在，它要么在集合中，要么你拥有它的唯一指针。在这种情况下，你甚至不需要查找集合。

但是在我看来，情况并非如此。我认为在这种情况下，你最好使用共享指针。只需存储共享指针并传递它们，因为除了这个集合之外，显然还有其他人存储它们。

- Artem Tokmakov

---

不，完全不是。unique_ptr 关注的是“所有权”。这并不意味着没有其他指向该对象的指针，只是没有其他所有者。 - Konrad Rudolph