A pointer vector sorted by its member function

Question

I'm asking for suggestions on a random accessed vector with allocated elements sorted by its key obtained from its member function.

I use it with Qt tree view where the access, add and deletion of tree items is implemented via its index or row number. And I want all the tree items are automatically sorted under a tree node.

If I use std::set, I need to calculate the index first (such as using distance function) when adding an item under a tree node and need a binary search when deleting and accessing an item.

Sorted pointer vectors can access items quickly but require moving pointers when adding and deleting an item. Compare all the advantages and disadvantages, I think this can give better performance

Am I right? Does anyone have experience on it or better suggestions?

#pragma once

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

//! A random accessed vector with allocated elements sorted by 
//! its key obtained from its member function.
//! - Duplicate elements are not allowed. 
template<class T, class K, K (T::*MemFun)() const>
class SortedPtrVector
{
public:
    SortedPtrVector()   {}

    //! Add an element, return its index.
    bool Add(std::unique_ptr<T> element, int& index)
    {
        if (!Find((element.get()->*MemFun)(), index))
        {
            m_vector.insert(m_vector.begin() + index, std::move(element));
            return true;
        }
        return false;        
    }

    //! Find the element with a key.
    //! - Return true when found and record its index; 
    //! - Return false when not found and record its lower bound.
    bool Find(const K& key, int& index) const
    {
        if (m_vector.empty())
        {
            index = 0;
            return false;
        }
        index = LowerBound(key);
        if (index >= m_vector.size())
            return false;
        if ((m_vector[index].get()->*MemFun)() == key)
            return true;
        return false;
    }

    //! Return an index to the first element which does not compare less than the key.
    int LowerBound(const K& key) const
    {
        int first = 0;
        int count = m_vector.size();
        while (count > 0)
        {
            int i = first;
            int step = count / 2;
            i += step;
            if ((m_vector[i].get()->*MemFun)() < key)
            {
                first = ++i;
                count -= step + 1;
            }
            else
            {
                count = step;
            }
        }
        return first;
    }

    //! Delete an element at an index.
    void DeleteAt(int index)
    {
        m_vector.erase(m_vector.begin() + index);
    }

    //! Delete an element with a key.
    void Delete(const K& key)
    {
        int index;
        if (Find(key, index))
            DeletaAt(index);
    }

    //! Clear.
    void Clear()
    {
        m_vector.clear();
    }

    unsigned Size()                                 {return m_vector.size();}
    const T& operator [](unsigned i) const          {return *m_vector[i];}

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

Answer 1

There's probably much that can be done here, but I'll point out some things I've noticed:

• As @David Harkness has mentioned in the comments, the method-naming looks like C# naming (uppercase, or PascalCase). While this isn't necessarily a bad thing as C++ is more flexible with naming, one problem here is that your types (particularly the class) and functions use the same naming convention, which may cause confusion for others.

  I would use separate naming for both of them, such as by changing the functions to camelCase or snake_case, while keeping the types as is.

• Since you're not overloading the default constructor, you don't have to include it. The compiler will make a default one for you.

  However, with C++11, you can now use default constructors:

  SortedPtrVector() = default;
  

• It looks like Add() is doing too many things:

  1. the actual adding
  2. updating a reference
  3. returning a bool

  Based on the name, it should just attempt to add something. But if it's still necessary to update the index, then it should just return that. You could instead return an std::pair<iterator, bool> as done with std::map::insert, but that may not be what you want here.

• Find() shouldn't set index to 0 if the vector is empty. An index of 0 is a valid position for a non-empty container (the first position). Instead, it could return -1, which is an out-of-bounds value commonly used with not found (this is also the same value as the constant std::string::npos).

  It may also be better to have Find() return an index instead of a bool. Assuming this is to somewhat resemble std::map::find, it can return a past-the-end value (an iterator) if the key isn't found.

• DeleteAt() may do something problematic if the argument isn't checked prior to calling erase() (an invalid index can cause erase() to attempt access to some other location, leading to undefined behavior).

• Size() should be const as it's not modifying any data members. You could also make it noexcept (also C++11) since it's guaranteed not to throw.

  Also, unsigned is not quite the specific return type of std::size(). It should either return an std::size_t (usually assumed), std::vector<std::unique_ptr<T>>::size_type (very lengthy), or even better and shorter with C++14 (if your compiler also supports it): the type deduced by auto.

  auto Size() const noexcept { return m_vector.size(); }