47

I often find myself wanting to write code like this:

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

  void removeObject(const Object* target);

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

However, much of the std::set interface is kind of useless with std::unique_ptrs since the lookup functions require std::unique_ptr parameters (which I obviously don't have because they're owned by the set itself).

I can think of two main solutions to this.

  1. Create a temporary unique_ptr for lookup. For example, the above removeObject() could be implemented like:

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

  2. Replace the set with a map of raw pointers to unique_ptrs.

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

However, both seem slightly stupid to me. In solution 1, erase() isn't noexcept, so the temporary unique_ptr might delete the object it doesn't really own, and 2 requires double the storage for the container unnecessarily.

I know about Boost's pointer containers, but their current features are limited compared to modern C++11 standard library containers.

I was recently reading about C++14 and came across "Adding heterogeneous comparison lookup to associative containers". But form my understanding of it, the lookup types must be comparable to the key types, but raw pointers aren't comparable to unique_ptrs.

Anyone know of a more elegant solution or an upcoming addition to C++ that solves this problem?

4

6 回答 6

38

在C++14中，如果存在，std::set<Key>::find则为template函数。Compare::is_transparent您传入的类型不需要是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 之外，您不得不使用maptounique_ptr方法或等效方法，因为 of 的签名find过于严格。或者写你自己的set等价物。

于 2013-09-22T05:18:49.013 回答
3

另一种可能性，接近公认的答案，但有点不同和简化。

我们可以利用标准比较器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
};
于 2018-09-09T12:34:32.887 回答
2

您可以尝试将 boost::multi_index_container 与 Object* 的附加索引一起使用。像这样的东西：

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 存储其他对象。在这种情况下，在使用之前，您根本不需要通过原始指针查找。

于 2013-09-22T04:13:41.827 回答
2

虽然绝对是一个 hack，但我刚刚意识到可以构建一个临时的“哑”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)));
}

该解决方案也适用于std::unordered_set、std::mapkeys 和std::unordered_mapkeys ，它们都只使用标准 C++11，几乎没有不必要的开销。

于 2014-03-13T02:33:29.807 回答
1

更新 2： Yakk 是正确的，没有办法使用标准 C++11 容器做到这一点而没有重大妥协。在最坏的情况下，某些东西会在线性时间内运行，或者您在问题中编写了那些解决方法。

我会考虑两种解决方法。

我会尝试 sorted std::vector，类似于boost::container::flat_set。是的，在最坏的情况下，插入/擦除将是线性时间。尽管如此，它可能比您想象的要快得多：与基于节点的容器（例如std::set. 请阅读他们在boost::container::flat_set上写的内容。这种妥协对你来说是否可以接受，我无法判断/衡量。

其他人也提到了std::share_ptr。我个人尽量避免使用它们，主要是因为“共享指针与全局变量一样好”（Sean Parent）。我不使用它们的另一个原因是它们很重，部分原因是我通常不需要的所有多线程东西。但是，boost::shared_ptr在BOOST_SP_DISABLE_THREADS定义时，会消除与多线程相关的所有开销。我相信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();
}
于 2013-09-22T10:29:37.910 回答
-1

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

但在我看来，情况并非如此。我想在这种情况下你最好使用共享指针。只需存储共享指针并传递它们，因为这个集合旁边的人清楚地存储了它们。

于 2013-09-22T04:23:53.173 回答