vector_map.cpp

#include <algorithm>
#include <vector>
#include <map>

template<
    class Key,
    class Mapped,
    class Compare = std::less<Key>,
    class Alloc = std::allocator<std::pair<Key, Mapped>>
> class vector_map{
public:
    using key_type = Key;
    using mapped_type = Mapped;
    using key_compare = Compare;
    using value_type = std::pair<key_type, mapped_type>;
    using container_type = std::vector<std::pair<key_type, mapped_type>>;
    using allocator_type = Alloc;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = typename std::allocator_traits<allocator_type>::pointer;
    using const_pointer = typename std::allocator_traits<allocator_type>::const_pointer;
    using iterator = typename container_type::iterator;
    using const_iterator = typename container_type::const_iterator;
    using reverse_iterator = typename container_type::reverse_iterator;
    using const_reverse_iterator = typename container_type::const_reverse_iterator;
    using difference_type = typename container_type::difference_type;
    using size_type = typename container_type::size_type;

    class value_compare{
        friend class vector_map;
    public:
        Compare comp;
        value_compare(Compare comp) : comp(comp){}
        using result_type = bool;
        using first_argument_type = value_type;
        using second_argument_type = value_type;
        bool operator ()(const value_type& x, const value_type& y) const{
            return comp(x.first, y.first);
        }
    };

    explicit vector_map(
        const key_compare &comp = key_compare(),
        const allocator_type &alloc = allocator_type()
    ) : comp(comp), vec(alloc){}

    explicit vector_map(const allocator_type &alloc) : comp(), vec(alloc){}

    template<class InputIterator>
    vector_map(
        InputIterator first, InputIterator last,
        const key_compare &comp = key_compare(),
        const allocator_type &alloc = allocator_type()
    ) : comp(comp), vec(first, last, alloc)
    { std::sort(vec.begin(), vec.end(), comp); }

    vector_map(const vector_map &other)
        : comp(other.comp), vec(other.vec)
    {}

    vector_map(vector_map &&other)
        : comp(std::move(other.comp)), vec(std::move(other.vec))
    {}

    vector_map(vector_map &&other, const allocator_type &alloc)
        : comp(std::move(otehr.comp)), vec(std::move(otehr.vec), alloc)
    {}

    vector_map(
        std::initializer_list<value_type> list,
        const key_compare &comp = key_compare(),
        const allocator_type &alloc = allocator_type()
    ) : comp(comp), vec(list, alloc)
    { std::sort(vec.begin(), vec.end(), [&](const value_type &a, const value_type &b){ return comp(a.first, b.first); }); }

    vector_map &operator =(const vector_map &other){
        comp = other.comp;
        vec = other.vec;
        return *this;
    }

    vector_map &operator =(vector_map &&other){
        comp = std::move(other.comp);
        vec = std::move(other.vec);
        return *this;
    }

    vector_map &operator =(std::initializer_list<value_type> list){
        vec = list;
        return *this;
    }

    iterator begin(){
        return vec.begin();
    }

    iterator end(){
        return vec.end();
    }

    const_iterator begin() const{
        return vec.begin();
    }

    const_iterator end() const{
        return vec.end();
    }

    iterator rbegin(){
        return vec.rbegin();
    }

    iterator rend(){
        return vec.rend();
    }

    const_iterator rbegin() const{
        return vec.rbegin();
    }

    const_iterator rend() const{
        return vec.rend();
    }

    const_iterator cbegin() const{
        return vec.cbegin();
    }

    const_iterator cend() const{
        return vec.cend();
    }

    const_iterator crbegin() const{
        return vec.crbegin();
    }

    const_iterator crend() const{
        return vec.crend();
    }

    bool empty() const{
        return vec.empty();
    }

    size_type size() const{
        return vec.size();
    }

    bool max_size() const{
        return vec.max_size();
    }

    value_type &operator [](const key_type &key){
        std::pair<key_type, mapped_type> v;
        v.first = key;
        auto iter = std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == key){
            return *iter;
        }else{
            return vec.end();
        }
    }

    const value_type &operator [](const key_type &key) const{
        std::pair<key_type, mapped_type> v;
        v.first = key;
        auto iter = std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == key){
            return *iter;
        }else{
            return vec.end();
        }
    }

    value_type &at(const key_type &key){
        std::pair<key_type, mapped_type> v;
        v.first = key;
        auto iter = std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == key){
            return *iter;
        }else{
            throw std::out_of_range("vector_map: throw out_of_range;");
        }
    }

    const value_type &at(const key_type &key) const{
        std::pair<key_type, mapped_type> v;
        v.first = key;
        auto iter = std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == key){
            return *iter;
        }else{
            throw std::out_of_range("vector_map: throw out_of_range;");
        }
    }

    std::pair<iterator, bool> insert(const value_type &value){
        iterator iter = std::lower_bound(
            vec.begin(), vec.end(), value,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == key){
            return std::make_pair(iter, false);
        }else{
            iter = vec.insert(iter, std::make_pair<key_type, mapped_type>(value.first, value.second));
            return std::make_pair(iter, true);
        }
    }

    std::pair<iterator, bool> insert(value_type &&value){
        iterator iter = std::lower_bound(
            vec.begin(), vec.end(), value,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == value.first){
            return std::make_pair(iter, false);
        }else{
            iter = vec.insert(iter, std::make_pair(std::move(value.first), std::move(value.second)));
            return std::make_pair(iter, true);
        }
    }

    iterator insert(const_iterator position, const value_type &value){
        return vec.insert(position, value);
    }

    iterator insert(const_iterator position, value_type &&value){
        return vec.insert(position, value);
    }

    template<class InputIter>
    void insert(InputIter first, InputIter last){
        vec.insert(vec.end(), first, last);
        std::sort(
            vec.begin(), vec.end(),
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
    }

    void insert(std::initializer_list<value_type> list){
        vec.insert(list);
        std::sort(
            vec.begin(), vec.end(),
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
    }

    iterator erase(const_iterator position){
        return vec.erase(position);
    }

    iterator erase(const_iterator first, const_iterator last){
        return vec.erase(first, last);
    }

    size_type erase(const key_type &key){
        std::pair<key_type, mapped_type> v;
        v.first = key;
        iterator iter = std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == key){
            vec.erase(iter);
            return 1;
        }else{
            return 0;
        }
    }

    void swap(vector_map &other){
        std::swap(comp, other.comp);
        vec.swap(other.vec);
    }

    void clear() noexcept{
        vec.clear();
    }

    std::pair<iterator, bool> emplace(key_type &&key, mapped_type &&mapped){
        std::pair<key_type, mapped_type> v = { key, mapped };
        iterator iter = std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == value.first){
            return std::make_pair(iter, false);
        }else{
            iter = vec.insert(iter, v);
            return std::make_pair(iter, true);
        }
    }

    std::pair<iterator, bool> emplace(const_iterator hint, key_type &&key, mapped_type &&mapped){
        std::pair<key_type, mapped_type> v = { key, mapped };
        if(hint == end()){
            --hint;
        }
        if(comp(*hint, v)){
            return insert(v);
        }else if(!comp(v, *hint)){
            return std::make_pair(hint, false);
        }else{
            iterator iter = vec.insert(hint, v);
            return std::make_pair(iter, true);
        }
    }

    key_compare key_comp() const{
        return key_compare();
    }

    value_compare value_comp() const{
        return value_compare(comp);
    }

    iterator find(const key_type &key){
        std::pair<key_type, mapped_type> v;
        v.first = key;
        iterator iter = std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == key){
            return iter;
        }else{
            return vec.end();
        }
    }

    const_iterator find(const key_type &key) const{
        std::pair<key_type, mapped_type> v;
        v.first = key;
        const_iterator iter = std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == key){
            return iter;
        }else{
            return vec.end();
        }
    }

    size_type count(const key_type &key) const{
        if(find(key) != end()){
            return 1;
        }else{
            return 0;
        }
    }

    iterator lower_bound(const key_type &key){
        std::pair<key_type, mapped_type> v;
        v.first = key;
        return std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
    }

    const_iterator lower_bound(const key_type &key) const{
        std::pair<key_type, mapped_type> v;
        v.first = key;
        return std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
    }

    iterator upper_bound(const key_type &key){
        std::pair<key_type, mapped_type> v;
        v.first = key;
        return std::upper_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
    }

    const_iterator upper_bound(const key_type &key) const{
        std::pair<key_type, mapped_type> v;
        v.first = key;
        return std::upper_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
    }

    std::pair<iterator, iterator> equal_range(const key_type &key){
        std::pair<key_type, mapped_type> v;
        v.first = key;
        iterator iter = std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == key){
            std::make_pair(iter, iter);
        }
    }

    std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const{
        std::pair<key_type, mapped_type> v;
        v.first = key;
        const_iterator iter = std::lower_bound(
            vec.begin(), vec.end(), v,
            [&](const value_type &a, const value_type &b){
                return comp(a.first, b.first);
            }
        );
        if(iter != vec.end() && iter->first == key){
            std::make_pair(iter, iter);
        }
    }

private:
    key_compare comp;
    std::vector<std::pair<key_type, mapped_type>> vec;
};