Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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(); }
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.