CODEWITHSUNDEEP
c++containers
user1899020
user1899020

Reputation: 13575

How to implement sorted pointer vector?

I want to implement a sorted pointer vector, like the following

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

How to implement the Add function? Thanks a lot.

Upvotes: 1

Views: 454

Answers (2)

Sarfaraz Nawaz
Sarfaraz Nawaz

Reputation: 361412

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

This is obviously wrong. Compare is a type, not an object.

You could use lambda with an object of Compare. So I think this should work:

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

Note that you cannot pass element to std::lower_bound, as element is of type T*, when the std::lower_bound expects the value of type std::unique_ptr<T> and there is no implicit conversion from T* to std::unique_ptr<T>. Also, you cannot insert element to the vector for the same reason. Insert uniqElem to the vector.

I would suggest you to take the argument as unique_ptr instead of T*, because that indicates to the user that the added item will be deleted automatically when an object of SortedPtrVector goes out of scope:

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!

If you use std::unique_ptr<T> as parameter type, then note these points:

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

It is all because std::unique_ptr is NOT copyable, but it is moveable.

Upvotes: 1

K-ballo
K-ballo

Reputation: 81349

Instead of using std::less you can implement your own ptr_less like this:

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

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

A general implementation would have to check for null pointers as well.

Another approach would be to use boost::ptr_vector instead of std::vector.

Upvotes: 1

Related Questions