patterncppMinor

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

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

objectswithflat_setembeddedfunctorusedcustomakaforpointers

Problem

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)  users;
//  few tests
    users.add("firda");
    for (auto p : users) cout name() name() name()  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:

```
//#################

Solution

General Points

No vertical space makes it extremely hard to read (thus maintain).

None standard bracing style is also really horrible give it up.

The standard containers are not designed to be inherited from.

Prefer composition over inheritance

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 GetKey = get_key>  // Never really need this.

Lazy Design.

The comparison operator is overloaded out the wazoo.

template , class GetKey = get_key>
  class comparator: protected GetKey, protected Less {
public:
    const GetKey& get_key() const {
        return static_cast(*this); }
    const Less& less() const {
        return static_cast(*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

operatorname(); }};};

// 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 exc

Code Snippets

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

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

class comparator: protected GetKey, protected Less

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.

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.

Context

StackExchange Code Review Q#62294, answer score: 5

Revisions (0)

No revisions yet.