Sorted vector (aka flat_set) for objects (pointers) with custom embedded key (functor used)

Question

BEFORE YOU READ: this link should be included when you just don't like the format of the question and for those that read this question for the first time, the link may give you the idea what happened here. The rest after the line is untouched.

---

I was asking for such structure on SO, but got only link to boost::multi_index as an answer. So, I decided to write it myself (and plan to include the final version there as self-answer, while probably rewriting/rewording the question as well - it definitely needs it).

I wanted both fast and memory-efficient set for objects (stored by pointer, allocation managed outside of the container for various reasons, e.g. deleting user with connected clients - disposing needs to be done later by last closed client) with functor to get the key from the value/object (as well as searching by both the pointer and the key). My test code showing the usage:
(class User containing string name, which is used as key for the set)

Usage

class User {
    string name_;
public:
    User(string name): name_(std::move(name)) {
        return; }
    const char * name() const {
        return name_.c_str(); }
//  the functor to be passed to the container
    struct get_key {
        const char * operator() (User* u) const {
            return u->name(); }};};
//  comparator for user names
struct str_less {
    bool operator() (const char *lhs, const char *rhs) const {
        return std::strcmp(lhs, rhs) < 0; }};
int main() {
//  the example set
    vset<User,const char*,str_less,User::get_key> users;
//  few tests
    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;
//  few more tests when the pointer is the key as well:
    vset<int,int*> ints;
    int* i = ints.add(new int(1));
    auto j = ints.find(i);
    cout << **j << endl; }

You have for sure already noticed that there is something strange about my code-styling. I have created my own preprocessor, not to get bothered by missing ; especially at the end of a header, when I switch from C# project (I am the only programmer managing many C++ and C# projects). The real source code looks like this:

//############################################################### testing
#include <iostream> <cstring>
using std: cout, endl, 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

Vector of Pointers

While writing the set-container, I have also created a helper vector for pointers, with altered iterators (for easier work with pointers, condpair is e.g. for emplace in the final set-container) and few other methods (add, remove, release, ...):

/// 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(); }};

And again the real unprocessed source code:

#include <vector> <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()

The Core

Here is the core of the final container. I am still not that good in SFINAE when it comes to conditionally-added methods (those methods that are there only when some condition on template parameters is met). So, I have decided to create few classes on the way, that help me with the specialization of the container for key=pointer.

//###################################################### 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(); }};
}}

The Final Class

//================================================================== 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> {};

Full Life Demo on IdeOne.com

And the complete unprocessed source file:

#include <vector> <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.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
namespace
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, end, remove, find
    using base: lower_bound, upper_bound, 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> <cstring>
using std: cout, endl, 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

Answer 1

General Points

1. No vertical space makes it extremely hard to read (thus maintain).
2. None standard bracing style is also really horrible give it up.
3. The standard containers are not designed to be inherited from.
4. Prefer composition over inheritance
5. Your interface leaks pointers.
   Modern C++ prefers you define ownership semantics of objects rather than use pointers.

Dis-beliefs.

Your structure does not allow multiple index (as you claim in the comments) as each object only contains one index. Now maybe you mean you can use multiple of your structures to achieve multi-indexing because all the members are stored as pointers and thus can easily be put into multiple versions of your container each with a different sorting arrangement (and that is true). But this exposes one of the main problems with your structure (ownership semantics).

Ownership semantics.

The class pvect takes pointers (or builds them dynamically) but does not seem to take ownership (they are not destroyed on destruction or when they are removed from the container (which means you have a leaky container). Not a good start. Maybe that is handled in some wrapper class that I have not spotted. But in that case this should be a private member class so it can not be accidentally used.

This leaking of ownership is pervasive about all your classes. As such it becomes unusable as a container in real world situations (as nobody can tell who is supposed to delete the object).

Overdesign

The requirement for a GeyKey is not required. It adds an extra layer of indirection on top of the Less type.

template <class T, class K=T,
    class Less = std::less<K>,
    class GetKey = get_key<T,K>>  // Never really need this.

Lazy Design.

The comparison operator is overloaded out the wazoo.

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)); }};

There is no need for this. The comparator operator should compare two objects. This seems to suggest that you're underlying class that you are using them is designed in such a way that you were lazy in deciding which type of value you were using and you overload every single combination to get rid of the compiler errors.

While we have this class:

class comparator: protected GetKey, protected Less

Why are we inheriting from GetKey or Less? Neither of these classes have virtual interfaces where inheritance would make it sensible to inherit from them.

It is much easier to use composition in this case.

class comparator
{
    protected:   // If you must make them protected sure.
                 // But that seems unnesacery. Just make the whole thing public.
        GetKey   getKey;
        Less     lessThanTest;

    public:
        bool operator() (Value const& x, Value const& y) const
        {
             return lessThanTest(getKey(x), getKey(y));
        }
 }; // Now its readable.

Finally analysis of User (from original comments).

I find some of your decisions odd.

class User {
    string name_;
public:
    // Pass by value always causing a copy then using the
    // semantics to move from the copy. I think this is a
    // bit odd as the using the more natural pass by const
    // reference to by more natural and shows your intent
    // more easily. Addionally if you want you can add a
    // normal move constructor so that you don't need to
    // copy more than once.
    User(string name): name_(std::move(name)) {
        return; }

    // Returning a pointer.
    // Are we trying a bit of premature optimization.
    // Return a const reference to the string. That is a
    // a much more natural way of passing strings.
    // Also see later (about the comparison).
    const char * name() const {
        return name_.c_str(); }

    // Sure. But that seems overkill when
    // You can define the comparison operator inline
    // with the container type. You should be using std::less
    // as the defeautlt comparison operator which be default
    // uses the `operator<(T const&, T const&)`    
    struct get_key {
        const char * operator() (User* u) const {
            return u->name(); }};};

// Why would you define something like this.
// Which is also trivially (and automatically implemented)
// by std::string?
struct str_less
    bool operator() (const char *lhs, const char *rhs) const
        return std::strcmp(lhs, rhs) < 0

// Also std::strcmp does a basic numeric comparison on the characters
// In the string. While std::string when doing a comparison is locale
// aware and will sort the users names aware of the current locale.
// which is an exceedingly good reason to use std::string over C-Strings.

I would re-write the above as:

class User
{
      string name_;
    public:
      User(std::string const& name): name_(name) {}
      User(std::string&& name):      name_(std::forward<std::string>(name)) {}

      std::string const& name() const {return name;}
};
bool operator<(User const& lhs, User const& rhs)
{
    return lhs.name() < rhs.name();
}
// The container knows it is storing pointers, so it should
// deference the objects before doing a comparison.

There is already a well tested container for storing pointers.
See boost::ptr_vector<T>, boost::ptr_map<Key, Value> etc...

template <class T, class K=T,
  class Less = std::less<K>,
  class GetKey = detail::vset::get_key<T,K>>

I don't see the need for a GetKey class when you already have a Less class. The default version of std::less uses operator< which should work in most situations. When it does not you should define a specialized version than knows how to query the underlying T to get the get the key you don't need an extra level of indirection.

PS. As a personal note I prefer to use typename in the template as it does not imply that it needs to be a class (but rather any type). Technically though it makes no difference.

template <typename T, typename K=T,
         typename Less = std::less<K>>

The rest is too dense. But I have the feeling I will find the same sort of issues.

Answer 2

Pointers

Original remove in ptrvect:

T* remove(T* key)
    auto it = find(key)
    if it == end(); return nullptr
    T* val = *it
    base::erase(it)
    return val

Accepted change:

unique_ptr<T> remove(T* key)
    auto it = find(key)
    T* val = nullptr
    if it != end()
        val = *it
        base::erase(it)
    return unique_ptr<T>(val)

And original release added to destructor, similar changes througout the interface. This way, the caller is made responsible for the pointer and the object gets disposed if the return value is not used. Other pointers (like on operator[]) are no problem.

No other proposal (except formatting options for the preprocessor) was accepted, see comments at the end, if you wish.

Vertical spacing

Given sample of the real source code:

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:

The no-option output is:

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:

First option: } on separate lines:

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:

Second option to place { on separate lines:

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:

Third option making even more room:

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:

Inheritance vs. Composition

Composition of the comparator is clearly wrong, because inheritance is taking advantage of Empty base optimization.

Protected (or private) inheritance of containers is no problem - public inheritance would be, because of possible polymorhic destruction. There is no big difference between having first protected/private member or inheriting it (except EBO).

The need for GetKey

Unfortunatelly, Loki just state something, which he refused to proof or even explain. I think that he just missed the find method and operator[]. We don't need to get key for sorting (if we know how to compare to objects), but need some of these for the searching:

1. GetKey + Less (the approach taken)
2. Transparent Less (able to compare the object to the key as well - that was composed in the solution form GetKey + Less producing the comparator)
3. Map Hack - wrapping pointer to the key inside the object and use it in std::map. No real advantage and some overhead added.

Usage example

That was not part of the code for review, just and imperfect example. The real objects are a bit different.