Sorted Vector aka Flat Set

#include <vector>
#include <algorithm>
//############################################################### ptrvect
/// Vector of Pointers
template <class T, class base = std::vector<T*> >
  class ptrvect: public base {
public:
    class iterator: public base::iterator {
        friend class ptrvect;
        iterator(const typename base::const_iterator& it):
          base::iterator(const_cast<T**>(&*it)) {
            return;
        }
    public:
        iterator(const typename base::iterator& it):
          base::iterator(it) {
            return;
        }
        T* operator->() const {
            return **this;
        }
    };
    class const_iterator: public base::const_iterator {
    public:
        const_iterator(const typename base::const_iterator& it):
          base::const_iterator(it) {
            return;
        }
        const_iterator(const typename base::iterator& it):
          base::const_iterator(it) {
            return;
        }
        T* operator->() const {
            return **this;
        }
    };
    template <class It = iterator>
      class condpair: public std::pair<It,bool> {
    public:
        condpair(It it, bool second):
          std::pair<It,bool>(it, second) {
            return;
        }
        T* operator->() const {
            return *std::pair<It,bool>::first;
        }
    };
public:
    iterator begin() {
        return iterator(base::begin());
    }
    iterator end() {
        return iterator(base::end());
    }
    const_iterator begin() const {
        return const_iterator(base::begin());
    }
    const_iterator end() const {
        return const_iterator(base::end());
    }
public: // workarounds for pre-C++11 / bad C++11 implementation (should allow const_iterator)
    iterator insert(const_iterator pos, T* value) {
        return base::insert(iterator(pos), value);
    }
    iterator erase(const_iterator pos) {
        return base::erase(iterator(pos));
    }
public: // addons
    iterator find (T* key) {
        return std::find(begin(), end(), key);
    }
    const_iterator find (T* key) const {
        return std::find(begin(), end(), key);
    }
    bool contains (T* key) const {
        return find(key) != end();
    }
    T* remove(T* key) {
        auto it = find(key);
        if (it == end()) return nullptr;
        T* val = *it;
        base::erase(it);
        return val;
    }
    T* add(T* val) {
        base::push_back(val);
        return val;
    }
    void release() {
        for (T* it : *this) delete it;
        base::clear();
    }
};
//###################################################### vset: comparator
namespace detail { namespace vset {
/// Get Key Functor for Vector-Set
template <class T, class K>
  struct get_key {
    K operator() (T* it) const {
        return (K)(*it);
    }
};
template <class T>
  struct get_key<T,T*> {
    T* operator() (T* it) const {
        return it;
    }
};
/// Comparator Functor for Vector-Set
template <class T, class K=T,
  class Less = std::less<K>, class GetKey = get_key<T,K>>
  class comparator: protected GetKey, protected Less {
public:
    const GetKey& get_key() const {
        return static_cast<const GetKey&>(*this);
    }
    const Less& less() const {
        return static_cast<const Less&>(*this);
    }
    K operator() (T* it) const {
        return get_key()(it);
    }
    bool operator() (K x, K y) const {
        return less()(x, y);
    }
    bool operator() (T* x, K y) const {
        return less()(get_key()(x), y);
    }
    bool operator() (K x, T* y) const {
        return less()(x, get_key()(y));
    }
    bool operator() (T* x, T* y) const {
        return less()(get_key()(x), get_key()(y));
    }
};
template <class T, class Less, class GetKey>
  class comparator<T,T*,Less,GetKey>:
  protected GetKey, protected Less {
public:
    const GetKey& get_key() const {
        return static_cast<const GetKey&>(*this);
    }
    const Less& less() const {
        return static_cast<const Less&>(*this);
    }
    T* operator() (T* it) const {
        return get_key()(it);
    }
    bool operator() (T* x, T* y) const {
        return less()(x, y);
    }
};
//============================================================ vset: base
/// Vector-Set Basic Implementation
template <class T, class K=T,
  class Less = std::less<K>,
  class GetKey = get_key<T,K>>
  class base: protected comparator<T,K,Less,GetKey>, protected ptrvect<T> {
    typedef ptrvect<T> core;
protected:
//    disable polymorphic destruction by hiding non-virtual destructor
    ~base() {
        return;
    }
    const comparator<T,K,Less,GetKey>& comp() const {
        return static_cast<const comparator<T,K,Less,GetKey>&>(*this);
    }
public:
//    pointers cannot be changed -> iterator = const_iterator
    typedef typename core::const_iterator iterator, const_iterator;
    typedef typename core::template condpair<iterator> condpair;
    typedef T *value_type;
    typedef K key_type;
    using core::size_type;
    using core::size;
    using core::empty;
    iterator begin() const {
        return core::begin();
    }
    iterator end() const {
        return core::end();
    }
public:
    iterator lower_bound(K key) const {
        return std::lower_bound(begin(), end(), key, comp());
    }
    iterator upper_bound(K key) const {
        return std::upper_bound(begin(), end(), key, comp());
    }
    std::pair<iterator, iterator> equal_range(K key) const {
        return std::equal_range(begin(), end(), key, comp());
    }
    iterator find(K key) const {
        iterator it = lower_bound(key);
        return it == end() || comp()(key, *it) ? end() : it;
    }
    bool contains(K key) const {
        iterator it = lower_bound(key);
        return it != end() && !comp()(key, *it);
    }
public:
    template<class... Args>
      condpair emplace(K key, Args&& ...args) {
          iterator it = lower_bound(key);
        if (it == end() || comp()(key, *it)) {
            return condpair(core::insert(it,
              new T(key, std::forward<Args>(args)...)), true);
        }
        return condpair(it, false);
    }
    iterator erase(iterator at) {
        return core::erase(at);
    }
public:
    T* add(T* value) {
        K key = comp()(value);
        iterator it = lower_bound(key);
        if (it == end() || comp()(key, *it)) {
            core::insert(it, value);
            return value;
        }
        return nullptr;
    }
    template<class... Args>
      T* add(K key, Args&& ...args) {
          iterator it = lower_bound(key);
        if (it == end() || comp()(key, *it)) {
            T* value = new T(key, std::forward<Args>(args)...);
            core::insert(it, value);
            return value;
        }
        return nullptr;
    }
    T* get(K key) const {
        iterator it = find(key);
        return it == end() ? nullptr : *it;
    }
    T* operator[](K key) const {
        return *emplace(key).first;
    }
    T* remove(K key) {
        iterator it = find(key);
        if (it == end()) return nullptr;
        T* value = *it;
        core::erase(it);
        return value;
    }
    void release() {
        for (T* it : *this) {
            delete it;
        }
        core::clear();
    }
    void clear() {
        core::clear();
    }
};
}}
//================================================================== vset
template <class T, class K=T,
  class Less = std::less<K>,
  class GetKey = detail::vset::get_key<T,K>>
  class vset: public detail::vset::base<T,K,Less,GetKey> {
    typedef detail::vset::base<T,K,Less,GetKey> base;
protected:
    using base::comp;
public:
    typedef typename base::iterator iterator;
    using base::begin; using base::end; using base::remove; using base::find;
    using base::lower_bound; using base::upper_bound; using base::equal_range;
    T* remove(T* value) {
        return remove(comp()(value));
    }
    iterator find(T* value) const {
        K key = comp()(value);
        iterator it = lower_bound(key);
        return it == end() || comp()(key, *it) ? end() : it;
    }
    iterator lower_bound(T* value) const {
        return std::lower_bound(begin(), end(), value, comp());
    }
    iterator upper_bound(T* value) const {
        return std::upper_bound(begin(), end(), value, comp());
    }
    std::pair<iterator, iterator> equal_range(T* value) const {
        return std::equal_range(begin(), end(), value, comp());
    }
};
//============================================================ vset: K=T*
template <class T, class Less, class GetKey>
  class vset<T,T*,Less,GetKey>:
  public detail::vset::base<T,T*,Less,GetKey> {};
//############################################################### testing
#include <iostream>
#include <cstring>
using std::cout; using std::endl; using std::string;
class User {
    string name_;
public:
    User(string name): name_(std::move(name)) {
        return;
    }
    const char * name() const {
        return name_.c_str();
    }
    struct get_key {
        const char * operator() (User* u) const {
            return u->name();
        }
    };
};
struct str_less {
    bool operator() (const char *lhs, const char *rhs) const {
        return std::strcmp(lhs, rhs) < 0;
    }
};
int main() {
    vset<User,const char*,str_less,User::get_key> users;
    users.add("firda");
    for (auto p : users) cout << p->name() << endl;
    auto it = users.find("firda");
    cout << it->name() << endl;
    it = users.find(*it);
    cout << it->name() << endl;

    vset<int,int*> ints;
    int* i = ints.add(new int(1));
    auto j = ints.find(i);
    cout << **j << endl;
}