Wrapper class template for std::map + std::list to provide a SequencedMap which retains insertion order

Question

Review on this draft please: clang-8 -std=c++17

Simple wrapper class template for std::map & std::list (or alternatively std:unordered_map & std::vector) for the purpose of "retaining insertion order". This is quite a frequently asked question, eg

https://stackoverflow.com/questions/2266179/c-stl-map-i-dont-want-it-to-sort/2267198

https://stackoverflow.com/questions/35053544/keep-the-order-of-unordered-map-as-we-insert-a-new-key/59100306#59100306

And the only answers are "Boost::multi_index" or "roll your own with (unordered_)map + list|vector". The very slimline class template below attempts to put some structure to the latter for those who don't want to or can't include a huge sledgehammer.

A couple of utility print function templates and some simple use cases are included for illustration only. There are a couple of questions in the comments regarding a clean way to expose the iterators. And, more generally, how to expose the API of the private list/map containers to the public interface in a controlled way without writing wrappers for every function overload:

Same code as below on goldbolt:

#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <random>
#include <string>
#include <vector>

template <class KeyT, class ValueT>
class SequencedMap {
  using MapT   = std::map<KeyT, ValueT>;
  using MapItT = typename MapT::iterator;

  using OrderValT = typename MapT::value_type*;
  using OrderT    = std::list<OrderValT>;
  using OrderItT  = typename OrderT::iterator;

public:
  std::pair<MapItT, bool> insert_or_assign(const KeyT& key, const ValueT& value) {
    auto ins_res            = map.insert_or_assign(key, value);
    auto [elem_it, was_new] = ins_res;
    if (was_new) order.push_back(&*elem_it);
    return ins_res;
  }

  MapItT find(const KeyT& key) const { return map.find(key); }

  ValueT& operator[](const KeyT& key) {
    // keep it simple. read or modify only. Not create!
    auto map_it = map.find(key);
    if (map_it == map.end())
      throw std::logic_error(
          "Warning! You are trying to create a SequencedMap entry using [] operator. Use "
          "insert_or_assign for safety!");
    return map_it->second;
  }

  OrderItT erase(const KeyT& key) {
    auto map_it = map.find(key);
    if (map_it == map.end()) return order.end();
    auto order_erased_it = order.erase(std::find(order.begin(), order.end(), &*map_it));
    map.erase(map_it);
    return order_erased_it;
  }

  // exposing the internal containers is not great, but need a clean way to expose their iterators
  // without too much code bloat. Preferable transparently change the MapT::value_type* to
  // MapT::value_type
  const MapT& getMap() const { return map; }
  const OrderT& getOrder() const { return order; }

private:
  MapT map;
  OrderT order;
};

// EOF class: Rest is demo usage code

template <class KeyT, class ValueT>
void print_in_insertion_order(const SequencedMap<KeyT, ValueT>& smap) {
  for (auto& pair_ptr: smap.getOrder()) {
    std::cout << pair_ptr->first << " -> " << pair_ptr->second << "\n";
  }
}

template <class KeyT, class ValueT>
void print_in_map_order(const SequencedMap<KeyT, ValueT>& smap) {
  for (auto& pair: smap.getMap()) {
    std::cout << pair.first << " -> " << pair.second << "\n";
  }
}

int main() {

  using Key   = std::string;
  using Value = int;

  SequencedMap<Key, Value> smap;

  // arbitrary ad-hoc temporary structure for the data (for demo purposes only)
  std::cout << "insert data...\n";
  for (auto p: std::vector<std::pair<Key, Value>>{
           {"Mary", 10}, {"Alex", 20}, {"Johnny", 30}, {"Roman", 40}, {"Johnny", 50}}) {
    smap.insert_or_assign(p.first, p.second);
  }
  print_in_insertion_order(smap);
  std::cout << "\nsorted by key\n";
  print_in_map_order(smap);

  std::cout << "\nretrieve by known key\n";
  auto key = "Alex";
  std::cout << key << " -> " << smap["Alex"] << "\n";

  std::cout << "\nchange value by known key: Johnny++\n";
  ++smap["Johnny"];
  print_in_insertion_order(smap);

  std::cout << "\ndelete by known key: Johnny\n";
  smap.erase("Johnny");
  print_in_insertion_order(smap);
}

Done a really simple benchmark:

Bench
SequencedMap: insert 100,000=252.06ms
SequencedMap: iterate in insertion order=1.47723ms
SequencedMap: modify 100,000 in insertion order=103.497ms
SequencedMap: delete 10,000=7513.77ms
Map: insert 100,000=227.629ms
Map: iterate in map order=6.91042ms
Map: modify 100,000 in map order=90.8201ms
Map: delete 10,000=16.7736ms

All looks very reasonable, but we have a problem on delete, as I expected. Finding the pointer is a linear operation each time. So O(n^2) for the 10,000 deletions. Not sure how to solve that, except to make the datastructure more complicated. Eg a reverse pointer from the map entry back to the list. Feels like pointer spaghetti then.

So, maybe a different idea: Ditch the std::list altogether, and instead of std::map<KeyT,ValueT> we use a std::map<KeyT,ValuePkgT> where:

struct ValuePkgT
{
  ValueT value;
  next MapT::value_type*; // recursive type reference here?
}

In other words the map value contains a struct which makes a "simple linked list" out of the map elements. Then we could have SeqeuencedMap actually inherit from std::map (is that bad?) publish a second set of iterators...eg SequencedMap::ibegin()/iend() (i=insertion_order) which use the internal linked list to iterate?

Opinions? Problems? Wise to extend std::map?

EDIT: I have pursued these new ideas in another question, here:

SequencedMap which retains insertion order - MKII

Answer 1

Reduce Lookups

ValueT& operator[](KeyT key) does 2 lookups, one in map.count(key) and one in map[key]. Using map.find(key) and then comparing the iterator against std::end(map) and then dereferencing it to return the value avoids that.

Consistent Parameter Types

ValueT& operator[](KeyT key) takes KeyT by value while other functions use const KeyT &. There doesn't seem to be a reason for that and you should be consistent.

Support Move-Only Types

Take inspiration from the standard. All versions of std::map::insert_or_assign take a ValueT && while you take a const ValueT &. That means unlike the standard containers you do not support std::unique_ptr for example. I don't see anything else that is holding it back, so it's an easy improvement for minimal effort.

Bonus: Use All The New Cool Features

(this one is not entirely serious)
In insert_or_assign

    auto [elem_it, was_new] = ins_res;
    if (was_new) order.push_back(&*elem_it);

can be written as

    if (auto [elem_it, was_new] = ins_res; was_new) {
        order.push_back(&*elem_it);
    }

I'm not sure it's better, but it's fancier. In theory it's better because it limits the scope of elem_it and was_new, but in practice in this case it just doesn't matter.

Nitpicking

Some of your variables can be const such as ins_res and map_it.

Extensions

You seem to want to keep it simple, so take these as suggestions of what could be done, not necessarily as part of the code review.

Transparent Comparators

It would be cool if you supported lookups that don't require to create a KeyT. For example ++smap["Johnny"]; unnecessarily creates a temporary std::string. std::string can compare to const char * already. See transparent comparators and std::map::find for inspiration.

A Real Container

Maybe you could make SequencedMap a real container which then allows its use in all the standard algorithms.

When In Doubt Use std::vector

It's a good default container unless benchmarks show you need something else. std::list is legendary for its terrible performance in almost all circumstances, even the ones that sound like they should be faster such as removing an element from the middle.