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

• K-ballo: This looks a lot like an associative ordered container, but fails to expose the interface we expect from associative ordered containers in C++.
• Corbin: It seems like there would be a weirdly specific use-case for this class? But interesting, nonetheless.
• David Harkness: What's with the C# (TitleCase) method naming?
• David Harkness: Can you add a 10-20 line example using it? Nothing fancy.

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

• David Harkness: Find sets index to the result of LowerBound which for an empty list is the first position, 0, where the missing item would be inserted. I agree Find should return the found item's index and -1 when not found and drop the index reference, but the code is internally consistent.
• Jamal: @DavidHarkness: So, you're saying that Find() is (generally) okay, with the exception of the -1?
• David Harkness: No, I'm saying given the current implementation, setting index to 0 is consistent. Changing it to use -1 and nothing else would break Add. But I wholeheartedly agree with your suggestion of rewriting And and Find completely. Yes, that pretty much makes my comment moot. :)
• Jamal: @DavidHarkness: Ah, okay. To me, it does make sense to change Find() as mentioned, at least if this is supposed to closely resemble an associative container.