Container with sorted by multiple keys

From this question:

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

This is an example of a multi-index container. Note: this is not a container as defined by the standard (a lot of methods and types required for that are still missing). It is a container in that you can add objects and you can get iterators to iterate over the container in particular orders. But adding the required methods and types should not be that hard.

The interface to this class is:

MI

For each type in it creates a separate index into the container. This allows you to iterate through container in different orders.

See example at the end for usage info.

```
template
class MI
{
typedef std::vector Storage;
typedef std::pair IndexItem;
template
struct StorageOrder
{
bool operator()(IndexItem const& lhs, IndexItem const& rhs) const
{
Order order;
return order(lhs.first->operator[](lhs.second), rhs.first->operator[](rhs.second));
}
};
template
class Index: public std::set>
{};
template
struct Ordering
{
Index& index;
Storage& storage;
Ordering(Index& index, Storage& storage): index(index), storage(storage) {}

struct iterator: public std::iterator
{
typedef typename Index::iterator ExtIterator;;
Storage& store;
ExtIterator i;
iterator(Storage& store, ExtIterator i): store(store), i(i) {}
T& operator*() {return store[i->second];}
T* operator->() {return &store[i->second];}
iterator& operator++ () {++i;return *this;}
iterator operator++ (int) {iterator result(*this);++i;return result;}
bool operator!=(iterator const& rhs) const {return i != rhs.i;}
}

Note: None of the following is tested.

But some thoughts that came to mind while I lay in bed.

Using too much Storage

Since writing this the main issue that has kept my tossing and turning is the need to store a pointer and an integer in the sorted containers.

typedef std::pair    IndexItem;

This was required because the underlying storage container was std::vector and thus when we insert into this container there is the possibility of the storage being re-allocated and thus invalidating all pointers and iterators into the storage.

But If we use an alternative form of storage: std::deque then insertion does not invalidate pointers into the storage and we can simplify the code in a couple of places:

typedef std::deque                       Storage;
typedef T*                                  IndexItem;
template
struct StorageOrder
{
    bool operator()(IndexItem const& lhs, IndexItem const& rhs) const
    {
        Order   order;
        return order(*lhs, *rhs);
    }
};
...
template
struct Ordering
{
    Index&   index;
    Ordering(Index& index):   index(index) {}

    struct iterator: public std::iterator
    {
        typedef typename Index::iterator  ExtIterator;;
        ExtIterator     i;
        iterator(ExtIterator i): i(i) {}
        ...
        T& operator*()                              {return **i;}
        T* operator->()                             {return *i;}
        ...
    };
};
...
    auto  item    = IndexItem(&storage.back());
...
    auto  item    = IndexItem(&storage.back());
...

Recreating the Ordering Object

The other issue that is bothering me a bit is creating the Ordering object each time a call is made to order().

return Ordering(x, storage);

Its not a huge object but it may impose some overhead. Rather than keep a tupple of Index std::tuple...> indexe; which just store the ordering, let us combine these two classes into a single new class that is stored in the tupple. The order() method then just returns a reference to this already existing object.

template
    struct Ordering
    {
        Index   index;  // Was a reference (now the object).
        Ordering()     {}
        ...
    };
    ...
    typedef std::tuple...>             Indexes;
    ...
        auto& anIndex std::get>(index);
    ...
        auto& x = std::get>(index);

Building a more compliant container object.

Making MI a container now seems a bit harder but it could be done (by using the first ordering as the default) but personally I would leave that and make it implement an interface for inserting/erasing new/old items into/from the container only.

Each of the indexes in the container could be made to support indexing/iterating and other search operations into the container. This could be done simply by adding the required functionality to the Ordering class.

StackExchange Code Review Q#62372, answer score: 3