Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
};
share|improve this question
1  
This looks a lot like an associative ordered container, but fails to expose the interface we expect from associative ordered containers in C++. –  K-ballo Jan 2 '13 at 4:31
    
It seems like there would be a weirdly specific use-case for this class? But interesting, nonetheless. –  Corbin Jan 2 '13 at 4:50
1  
What's with the C# (TitleCase) method naming? –  David Harkness May 26 at 23:31
2  
Can you add a 10-20 line example using it? Nothing fancy. –  David Harkness May 27 at 0:02
add comment

1 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 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 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 something unintended).

  • Size() should be const as it's not modifying any data members.

    Also, unsigned is not the 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++11: the type deduced by auto.

    auto Size() const { return m_vector.size(); }
    
share|improve this answer
    
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. –  David Harkness May 26 at 23:35
    
@DavidHarkness: So, you're saying that Find() is (generally) okay, with the exception of the -1? –  Jamal May 26 at 23:37
    
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. :) –  David Harkness May 26 at 23:51
    
@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. –  Jamal May 26 at 23:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.