An example of a class that enforces sorting on a vector.

sorted_vector.cpp

#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>

template<typename T>
struct comparator
{
        bool operator()(const T & a, const T & b)
        {
                return a < b;
        }
};

template <typename T>
class sorted_vector : public std::vector<T>
{
        private: 
                static const int default_size=16;
                comparator<T> cmp;
        public: 
                sorted_vector(comparator<T> & mycmp, int size=default_size)
                :       std::vector<T>(size), cmp(mycmp)
                {

                }

                void push_back(const T& t)
                {
                        std::vector<T>::push_back(t);
                        std::sort(this->begin(), this->end(), cmp);
                }
};

int main(void)
{
        comparator<int> int_compare;
        sorted_vector<int> ints(int_compare);
        ints.push_back(3);
        ints.push_back(1);
        ints.push_back(5);
        for(int i:ints)
        {
                std::cout << i << std::endl;
        }
        return EXIT_SUCCESS;
}