SortedListMap.hxx

Go to the documentation of this file.

 
#ifndef _UTILS_SORTEDLISTMAP_HXX_
#define _UTILS_SORTEDLISTMAP_HXX_
 
#include <vector>
#include <algorithm>
 
#include "utils/macros.h"
 
template <class D, class CMP> class SortedListSet
{
public:
    typedef D data_type;
 
private:
    typedef std::vector<data_type> container_type;
 
public:
    typedef typename container_type::iterator iterator;
    typedef typename container_type::const_iterator const_iterator;
 
    template <typename... Args>
    SortedListSet(Args &&...args)
        : cmp_(std::forward<Args>(args)...)
    {
    }
 
    void reserve(size_t sz)
    {
        container_.reserve(sz);
    }
 
    iterator begin()
    {
        lazy_init();
        return container_.begin();
    }
 
    iterator end()
    {
        return container_.begin() + sortedCount_;
    }
 
    size_t size() {
        return container_.size();
    }
    
    template<class key_type>
    iterator lower_bound(key_type key)
    {
        lazy_init();
        return std::lower_bound(
            container_.begin(), container_.end(), key, cmp_);
    }
 
    template<class key_type>
    iterator upper_bound(key_type key)
    {
        lazy_init();
        return std::upper_bound(
            container_.begin(), container_.end(), key, cmp_);
    }
    
    template<class key_type>
    iterator find(key_type key)
    {
        lazy_init();
        auto lb = lower_bound(key);
        auto ub = upper_bound(key);
        if (ub == lb) return end();
        return lb;
    }
    
    template<class key_type>
    std::pair<iterator, iterator> equal_range(key_type key)
    {
        lazy_init();
        return std::equal_range(
            container_.begin(), container_.end(), key, cmp_);
    }
 
    void insert(data_type &&d)
    {
        container_.push_back(d);
    }
 
    void erase(const iterator &it)
    {
        HASSERT(sortedCount_ > 0);
        container_.erase(it);
        --sortedCount_;
    }
 
    void erase(const iterator &it_b, const iterator& it_e)
    {
        container_.erase(it_b, it_e);
        lazy_init(); // will set sortedCount_.
    }
 
    void clear()
    {
        container_.clear();
        sortedCount_ = 0;
    }
 
private:
    void lazy_init()
    {
        if (sortedCount_ != container_.size())
        {
            sort(container_.begin(), container_.end(), cmp_);
            sortedCount_ = container_.size();
        }
    }
 
    container_type container_;
 
    CMP cmp_;
 
    size_t sortedCount_{0};
};
 
#endif // _UTILS_SORTEDLISTMAP_HXX_