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.

Ask for suggestion 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 a better performance. Am I right? Any one has experience on it or better suggestion?

#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
    
I add some of its uses in my post. Thanks. –  user1899020 Jan 2 '13 at 15:21
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.