C++ multi-index map implementation

Question

I'm implementing a multi-index map in C++11, which I want to be optimized for specific features. The problem I'm currently trying to solve, is to not store key elements more then once. But let me explain.

The problem arose from sorting histograms to overlay them in different combinations. The histograms had names, which could be split into tokens (properties).

Here are the features I want my property map to have:

1. Be able to loop over properties in any order;
2. Be able to return container with unique values for each property;
3. Accumulate properties' values in the order they arrive, but to be able to sort properties using a custom comparison operator after the map is filled;

I have a working implementation in C++11 using std::unordered_map with std::tuple as key_type. I'm accumulating property values as they arrive into a tuple of forward_lists. The intended use, is to iterate over the lists to compose keys.

The optimization I would like to introduce, is to only store properties' value in the lists, and not store them in tuples used as keys in the map. I'd like to maintain ability to have functions returning const references to lists of property values, instead of lists of some wrappers.

I know that boost::multi_index has similar functionality, but I don't need the overhead of sorting as the keys arrive. I'd like to have new property values stored sequentially, and only be sortable postfactum. I've also looked at boost::flyweight, but in the simplest approach, the lists will then be of flyweight<T> instead of T, and I'd like to not do that. (If that IS the best solution, I could definitely live with it.)

I know that lists are stable, i.e. once an element is created, its pointer and iterator remain valid, even after invoking list::sort(). Knowing that, can something be done to the map, to eliminate redundant copies of tuple elements? Could a custom map allocator help here?

Thanks for suggestions.

Answer 1

Have your map be from tuples of iterators to your prop containers.

Write a hash the dereferences the iterators and combines the result.

Replace the forward list prop containers with sets that first order on hash, then contents.

Do lookup by first finding in set, then doing lookup in hash.

If you need a different order for props, have another container of set iterators.