c++ - 如何实现排序指针 vector ？

Question

我想实现一个排序的指针 vector ，如下所示

#include <vector>
#include <memory>
#include <algorithm>

//! A random accessed vector with sorted allocated elements.
//! - Elements must be allocated on heap.
//! - The vector manages the memories of its elements.
template<class T, class Compare = std::less<T>>
class SortedPtrVector
{
public:
    SortedPtrVector()   {}

    //! Add an element, return its index.
    int Add(T* element)
    {
        auto position = std::lower_bound(m_vector.begin(), m_vector.end(), 
            element, Compare); // Wrong here due to compare smart pointers
        auto newPosition = m_vector.insert(position, element);
        return newPosition - m_vector.begin();
    }

private:
    std::vector<std::unique_ptr<T>> m_vector;
};

如何实现添加功能？非常感谢。

Answer 1

auto position = std::lower_bound(m_vector.begin(), m_vector.end(), 
        element, Compare);

这显然是错误的。 Compare是一种类型，而不是对象。

您可以将 lambda 与 Compare 的对象一起使用.所以我认为这应该可行:

Compare cmp; 
auto comparer = [&](std::unique_ptr<T> const & a, std::unique_ptr<T> const & b)
                {
                   return cmp(*a, *b); //use cmp here!
                };

std::unique_ptr<T> uniqElem(element); 

auto position = std::lower_bound( m_vector.begin(), 
                                  m_vector.end(), 
                                  uniqElem, //not element!!
                                  comparer);

请注意，您不能传递 element至 std::lower_bound , 作为 element类型为 T* , 当std::lower_bound期望类型的值 std::unique_ptr<T>并且没有来自 T* 的隐式转换至 std::unique_ptr<T> .此外，您不能插入 element出于同样的原因到 vector 。插入 uniqElem到 vector 。

我建议您将参数设为 unique_ptr而不是 T* , 因为这向用户表明当 SortedPtrVector 的对象时添加的项目将被自动删除超出范围:

int Add(T* element);                 //bad - doesn't say element will be deleted!
int Add(std::unique_ptr<T> element); //good - says element will be deleted!

如果您使用 std::unique_ptr<T>作为参数类型，然后注意以下几点:

v.Add(new T());                     //will not work
v.Add(std::unique_ptr<T>(new T());  //will work

std::unique_ptr<T> item(new T()); 
v.Add(item);                        //will not work
v.Add(std::move(item));             //will work

都是因为std::unique_ptr 不可复制，但可移动。