template<typename Next>
struct interface_add_sorted_insert : public Next {
    void insert(typename Next::value_type const& value) {
		typename Next::iterator pos = std::lower_bound(get_impl().begin(), get_impl().end(), value);
		get_impl().insert(pos, value);
	}
};

template<typename Next>
struct interface_add_iterators : public Next {
	typename Next::iterator begin() {
		return get_impl().begin();
	}

	typename Next::const_iterator begin() const {
		return get_impl().begin();
	}

	typename Next::reverse_iterator rbegin() {
		return get_impl().rbegin();
	}

	typename Next::const_reverse_iterator rbegin() const {
		return get_impl().rbegin();
	}

	typename Next::iterator end() {
		return get_impl().end();
	}

	typename Next::const_iterator end() const {
		return get_impl().end();
	}

	typename Next::iterator rend() {
		return get_impl().rend();
	}

	typename Next::const_reverse_iterator rend() const {
		return get_impl().rend();
	}
};

template<typename Next>
struct interface_add_const_iterators : public Next {
	typename Next::const_iterator begin() const {
		return get_impl().begin();
	}

	typename Next::const_reverse_iterator rbegin() const {
		return get_impl().rbegin();
	}

	typename Next::const_iterator end() const {
		return get_impl().end();
	}

	typename Next::const_reverse_iterator rend() const {
		return get_impl().rend();
	}
};

template<typename Next>
struct interface_add_const_metafuncs : public Next {
	typename Next::size_type size() const {
		return get_impl().size();
	}
	typename Next::size_type capacity() const {
		return get_impl().capacity();
	}
	typename Next::size_type length() const {
		return get_impl().length();
	}
	bool empty() const {
		return get_impl().empty();
	}
};

template<typename Next>
struct interface_add_back_front : public Next {
	typename Next::value_type& front() {
		return get_impl().front();
	}

	typename Next::value_type const& front() const {
		return get_impl().front();
	}

	typename Next::value_type& back() {
		return get_impl().back();
	}

	typename Next::value_type const& back() const {
		return get_impl().back();
	}
};

template<typename Next>
struct interface_add_const_back_front : public Next {
	typename Next::value_type const& front() const {
		return get_impl().front();
	}

	typename Next::value_type const& back() const {
		return get_impl().back();
	}
};

template<typename Next>
struct interface_add_random_access : public Next {
	typename Next::value_type& operator[](typename Next::size_type index) {
		return get_impl()[index];
	}

	typename Next::value_type const& operator[](typename Next::size_type index) const {
		return get_impl()[index];
	}
};

template<typename Next>
struct interface_add_const_random_access : public Next {
	typename Next::value_type const& operator[](typename Next::size_type index) const {
		return get_impl()[index];
	}
};

template<typename Next>
struct interface_add_sequence_access :
	public interface_add_iterators<
		interface_add_back_front<
			interface_add_random_access<
				Next
			>
		>
	> {
};

template<typename Next>
struct interface_add_const_sequence_access :
	public interface_add_const_iterators<
		interface_add_const_back_front<
			interface_add_const_random_access<
				Next
			>
		>
	> {
};

template<typename Impl>
class interface_base {
public:
	typedef typename Impl::value_type value_type;
	typedef typename Impl::reference reference;
	typedef typename Impl::const_reference const_reference;
	typedef typename Impl::pointer pointer;
	typedef typename Impl::const_pointer const_pointer;
	typedef typename Impl::iterator iterator;
	typedef typename Impl::const_iterator const_iterator;
	typedef typename Impl::reverse_iterator reverse_iterator;
	typedef typename Impl::const_reverse_iterator const_reverse_iterator;
	typedef typename Impl::size_type size_type;
	typedef typename Impl::difference_type difference_type;
	typedef typename Impl::allocator_type allocator_type;
	typedef Impl container_type;

private:
	Impl impl;

protected:
	Impl& get_impl() {
		return impl;
	}

	Impl const& get_impl() const {
		return impl;
	}

public:
	interface_base()
	: impl() {
	}

	explicit interface_base(allocator_type const& allocator)
	: impl(allocator) {
	}

	explicit interface_base(size_type n)
	: impl(n) {
	}

	interface_base(size_type n, value_type const& value)
	: impl(n, value) {
	}

	interface_base(size_type n, value_type const& value, allocator_type const& allocator)
	: impl(n, value, allocator) {
	}

	interface_base(container_type const& other)
	: impl(other) {
	}

	interface_base(interface_base const& other)
	: impl(other.impl) {
	}

	template<typename InputIter>
	interface_base(InputIter first, InputIter last)
	: impl(first, last) {
	}

	template<typename InputIter>
	interface_base(InputIter first, InputIter last, allocator_type const& allocator)
	: impl(first, last, allocator) {
	}
};