Container with sorted by multiple keys

Question

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<TypeToBeStored, ListOfIndexingTypes...>

For each type in <ListOfIndexingTypes...> 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<typename T, typename... O>
class MI
{
 typedef std::vector<T> Storage;
 typedef std::pair<Storage*, std::size_t> IndexItem;
 template<typename Order>
 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<typename Order>
 class Index: public std::set<IndexItem, StorageOrder<Order>>
 {};
 template<typename Order>
 struct Ordering
 {
 Index<Order>& index;
 Storage& storage;
 Ordering(Index<Order>& index, Storage& storage): index(index), storage(storage) {}
 struct iterator: public std::iterator<std::bidirectional_iterator_tag, T>
 {
 typedef typename Index<Order>::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;}
 };
 };
 typedef std::tuple<Index<O>...> Indexes;
 Storage storage;
 Indexes index;
 template<typename Order>
 bool addIndex(IndexItem const& item)
 {
 auto& anIndex = std::get<Index<Order>>(index);
 anIndex.insert(item);
 return true;
 }
 public:
 void add(T const& value)
 {
 std::size_t id = storage.size();
 storage.push_back(value);
 auto item = IndexItem(&storage, id);
 std::make_tuple(addIndex<O>(item)...);
 }
 template<typename... A>
 void emplace(A&&... param)
 {
 std::size_t id = storage.size();
 storage.emplace_back(std::forward<A>(param)...);
 auto item = IndexItem(&storage, id);
 std::make_tuple(addIndex<O>(item)...);
 }
 template<typename Order>
 Ordering<Order> order()
 {
 auto& x = std::get<Index<Order>>(index);
 return Ordering<Order>(x, storage);
 }
};

So if now look at usage examples:

int main()
{
 // Define a container for User.
 // It has two index into the container (one on Name the other on Age).
 MI<User, NameOrder, AgeOrder> index;
 // Add some items (could be better as 
 index.insert({"John", 52});
 index.insert({"June", 22});
 index.emplace("Steve", 76);
 // Loop over the container by Name order
 for(auto loop: index.order<NameOrder>())
 {
 std::cout << loop << "\n";
 }
 std::cout << "\n\n\n";
 // Loop over the container by Age order
 for(auto loop: index.order<AgeOrder>())
 {
 std::cout << loop << "\n";
 }
}

Then to implement User class and orderings on the user.

class User
{
 std::string name;
 int age;
 public:
 User(std::string const& name, int age) : name(name), age(age) {}
 friend std::ostream& operator<<(std::ostream& str, User const& data)
 {
 return str << data.name << " : " << data.age;
 }
 friend class NameOrder;
 friend class AgeOrder;
};
struct NameOrder
{
 bool operator()(User const& lhs, User const& rhs)
 {
 return lhs.name < rhs.name;
 }
};
struct AgeOrder
{
 bool operator()(User const& lhs, User const& rhs)
 {
 return lhs.age < rhs.age;
 }
};

• Ciro Santilli OurBigBook.com: related: stackoverflow.com/questions/1858306/…
• Toby Speight: I can't review this, as it doesn't compile (even after adding the obvious missing headers): index.insert({"John", 52}) is an undeclared member, and for(auto loop: index.order<NameOrder>()) can't find a suitable begin() or end().

Answer 1

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<Storage*, std::size_t> IndexItem;

This was required because the underlying storage container was std::vector<T> 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<T> Storage;
typedef T* IndexItem;
template<typename Order>
struct StorageOrder
{
 bool operator()(IndexItem const& lhs, IndexItem const& rhs) const
 {
 Order order;
 return order(*lhs, *rhs);
 }
};
...
template<typename Order>
struct Ordering
{
 Index<Order>& index;
 Ordering(Index<Order>& index): index(index) {}
 struct iterator: public std::iterator<std::bidirectional_iterator_tag, T>
 {
 typedef typename Index<Order>::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<T>().

 return Ordering<Order>(x, storage);

Its not a huge object but it may impose some overhead. Rather than keep a tupple of Index std::tuple<Index<O>...> 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<T>() method then just returns a reference to this already existing object.

 template<typename Order>
 struct Ordering
 {
 Index<Order> index; // Was a reference (now the object).
 Ordering() {}
 ...
 };
 ...
 typedef std::tuple<Ordering<O>...> Indexes;
 ...
 auto& anIndex std::get<Ordering<Order>>(index);
 ...
 auto& x = std::get<Ordering<Order>>(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.

• Thomas Russell: Just a minor point, but shouldn't std::dequeu be std::deque?
• Loki Astari: @Shaktal: Yep. :-(