如何實現排序的指針向量？

我想實現一個排序的指針矢量，像下面如何實現排序的指針向量？

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

如何實現添加功能？非常感謝。

來源

2012-12-29 user1899020

除了智能指針實現比較的問題之外，如果元素必須被排序，爲什麼不使用map/multimap而不是vector呢？作爲比較，std :: less的包裝器不會比較對象指針指向使用std :: less工作的更少？ –

我想隨機訪問元素。它們作爲樹項目放在樹節點下，如文件夾結構。當添加一個新文件時，我首先在樹節點下找到它的位置（行索引），然後將它添加到該位置。謝謝！ – user1899020

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插入到載體中。

我建議你把參數作爲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不是可複製，但它是可移動。

來源

2012-12-29 18:40:35 Nawaz

任何特殊的使用添加（std :: unique_ptr 元素）函數？似乎沒有unique_ptr的公共複製構造函數。 – user1899020

@ user1899020：是的，你有這樣稱呼它：'v.Add（標準::的unique_ptr （新T（））;'如果你寫這樣它不會工作：'標準::的unique_ptr 項目（新。 T（））; v.Add（項目）;'但它會，如果你寫這方面的工作：'v.Add（STD ::移動（項目））;'這都是因爲'的std :: unique_ptr'是。*不*可複製，但它是* *移動是 – Nawaz

它太麻煩也許我只是叫v.Add（新T（）） – user1899020

而不是使用std::less，你可以實現自己的ptr_less這樣的：

template< typename T > 
class ptr_less 
{ 
    typedef bool result_type; 

    bool operator()(T const& left, T const& right) const 
    { 
     return *left < *right; 
    } 
};

一般實現必須檢查空指針爲好。

另一種方法是使用boost::ptr_vector而不是std::vector。

來源

2012-12-29 18:37:04

如何實現排序的指針向量？

回答

相關問題