SortedVector.hpp

template<typename T, typename Container = std::vector<T> >
class SortedVector {
public:
    typedef T value_type, &reference;
    typedef const T &const_reference;
    typedef Container container_type;
    typedef typename container_type::iterator iterator;
    typedef typename container_type::const_iterator const_iterator;
    typedef typename container_type::size_type size_type;

    class insert_iterator {
    public:
        class assignable {
        private:
            SortedVector<T> &v_;
        public:
            assignable(SortedVector<T> &v) : v_(v) {}
            value_type operator=(const_reference x) { v_.insert(x); return x; }
        };
    private:
        assignable a_;
    public:
        insert_iterator(SortedVector<T> &v) : a_(v) {}
        assignable& operator *() { return a_; }
        insert_iterator operator++(int) { return *this; }
    };

private:
    container_type data_;

    iterator find_pos(const T& x) {
        size_type a = 0, b = data_.size();

        while (a < b) {
            size_type const m = (a + b) / 2;

            if (data_[m] < x) {
                a = m + 1;
            } else {
                b = m;
            }
        }
        return data_.begin() + a;
    }

public:
    void insert(const_reference x) { data_.insert(find_pos(x), x); }
    void remove(const_reference x) { data_.erase(find_pos(x)); }
    const_reference operator [](size_type i) const { return data_[i]; }
    size_type size() const { return data_.size(); }
    iterator begin() { return data_.begin(); }
    iterator end()   { return data_.end();   }
    const_iterator begin() const { return data_.begin(); }
    const_iterator end()   const { return data_.end();   }
};