SequencedMap a C++ container like std::map which retains insertion order

profile_tests.cpp

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)

  for (auto p: std::vector<std::pair<Key, Value>>{
           {"Mary", 10}, {"Alex", 20}, {"Johnny", 40}, {"Roman", 40}, {"Johnny", 50},
       }) {
    smap.insert_or_assign(p.first, p.second);
  }
  std::cout << "\nsorted by map\n";
  print_in_map_order(smap);

  std::cout << "\nsorted by insert\n";
  print_in_insertion_order(smap);

  std::cout << "\nretrieve by known key\n";
  auto key = "Alex";
  smap[key];
  ++smap[key];
  print_in_insertion_order(smap);

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

  std::cout << "\nchange value for new key: NewGuy++\n";
  ++smap["NewGuy"];
  print_in_insertion_order(smap);

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

  std::random_device rnd_device;
  std::uniform_int_distribution<char> letters_dist{0, 25};
  std::uniform_int_distribution<int> value_dist{0, 100};

  std::vector<std::string> keys;
  std::cout << "\nBench\n";
  {
    std::mt19937 engine{1}; // rnd_device()};
    SequencedMap<Key, Value> smap;
    {
      Timer t("SequencedMap: insert 100,000");

      for (int i = 0; i < 100'000; ++i) {
        std::string key = "";
        for (int c = 0; c < 10; ++c) {
          key += 'A' + letters_dist(engine);
        }
        int val = value_dist(engine);
        smap.insert_or_assign(key, val);
      }
    }
    int sum = 0;
    {
      Timer t("SequencedMap: iterate in insertion order");
      auto curr = smap.chead();
      while (true) {
        auto elem = smap.fromlink(*curr);
        sum += elem.second.value;
        if (curr == smap.ctail()) break;
        curr = curr->next;
      }
    }
    std::cout << "SequencedMap: Check sum=" << sum << "\n";
    {
      Timer t("SequencedMap: modify 100,000 in insertion order");
      auto curr = smap.chead();
      while (true) {
        auto& elem = smap.fromlink(*curr);
        ++elem.second.value;
        if (curr == smap.ctail()) break;
        curr = curr->next;
      }
    }
    sum = 0;
    {
      Timer t("SequencedMap: iterate in insertion order");
      auto curr = smap.chead();
      while (true) {
        auto elem = smap.fromlink(*curr);
        sum += elem.second.value;
        if (curr == smap.ctail()) break;
        curr = curr->next;
      }
    }
    std::cout << "SequencedMap: Check sum=" << sum << "\n";
    auto curr = smap.chead();
    while (true) {
      auto elem = smap.fromlink(*curr);
      keys.push_back(elem.first);
      if (curr == smap.ctail()) break;
      curr = curr->next;
    }
    std::shuffle(keys.begin(), keys.end(), engine);
    {
      Timer t("SequencedMap: delete 10,000");
      for (auto it = keys.begin(); it - keys.begin() < 10'000; ++it) {
        smap.erase(*it);
      }
    }
    sum = 0;
    {
      Timer t("SequencedMap: iterate in insertion order");
      auto curr = smap.chead();
      while (true) {
        auto elem = smap.fromlink(*curr);
        sum += elem.second.value;
        if (curr == smap.ctail()) break;
        curr = curr->next;
      }
    }
    std::cout << "SequencedMap: Check sum=" << sum << "\n";
  }
  {
    std::mt19937 engine{1}; // rnd_device()};
    std::map<Key, Value> map;
    {
      Timer t("Map: insert 100,000");

      for (int i = 0; i < 100'000; ++i) {
        std::string key = "";
        for (int c = 0; c < 10; ++c) {
          key += 'A' + letters_dist(engine);
        }
        int val = value_dist(engine);
        map.insert_or_assign(key, val);
      }
    }
    int sum = 0;
    {
      Timer t("Map: iterate in map order");
      for (auto& p: map) {
        sum += p.second;
      }
    }
    std::cout << "Map: Check sum=" << sum << "\n";
    {
      Timer t("Map: modify 100,000 in map order");
      for (auto& p: map) {
        ++map[p.first];
      }
    }
    sum = 0;
    {
      Timer t("Map: iterate in map order");
      for (auto& p: map) {
        sum += p.second;
      }
    }
    std::cout << "Map: Check sum=" << sum << "\n";
    {
      Timer t("Map: delete 10,000");
      for (auto it = keys.begin(); it - keys.begin() < 10000; ++it) {
        map.erase(*it);
      }
    }
    sum = 0;
    {
      Timer t("Map: iterate in map order");
      for (auto& p: map) {
        sum += p.second;
      }
    }
    std::cout << "Map: Check sum=" << sum << "\n";
  }
}

sequenced_map.cpp

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <type_traits>
#include <vector>

template <class KeyT, class ValueT>
class SequencedMap {
  // needed by std::map::operator[]
  static_assert(std::is_default_constructible_v<ValueT>, "ValueT must be DefaultConstructible");
  static_assert(std::is_default_constructible_v<KeyT>, "KeyT must be CopyConstructible");

  struct Links;
  struct Value;

public:
  using MapT    = std::map<KeyT, Value>;
  using MapItT  = typename MapT::iterator;
  using MapValT = typename MapT::value_type;

  MapValT& fromlink(Links& x) const noexcept {
    static_assert(std::is_standard_layout_v<MapValT>, "MapValT must have StandardLayout");
    return *reinterpret_cast<MapValT*>(
      reinterpret_cast<std::byte*>(&x) - offsetof(MapValT, second.links));
  }

  // TODO: Need a proper iterator solution
  Links* chead() const { return head; }
  Links* ctail() const { return tail; }

  template <class K, class V> // re-template to allow perfect forwarding
  std::pair<MapItT, bool> insert_or_assign(const K& key, V&& value) {
    auto insert_result        = map.insert_or_assign(key, Value(std::forward<V>(value)));
    auto& [elem_ptr, was_new] = insert_result;
    if (was_new) linkit(elem_ptr->second.links);
    return insert_result;
  }

  ValueT& operator[](const KeyT& key) {
    auto& e = map[key];
    if (e.links.prev == e.links.next && e.links.next != &ends) linkit(e.links);
    return e.value;
  }

  std::size_t erase(const KeyT& key) {
    const auto p = map.find(key);
    if (p == map.end()) return 0;
    unlinkit(p->second.links);
    map.erase(p);
    return 1;
  }

  // TODO: this shouldn't be public!
  const MapT& getMap() const { return map; }

private:
  MapT map;

  Links ends;
  Links*& head = ends.next;
  Links*& tail = ends.prev;

  struct Links {
    Links* prev = this;
    Links* next = this;

    Links()             = default;
    Links(const Links&) = default;
    Links(Links&&)      = default;

    // ignore asignment (move or copy) becaue it would likely break ptrs
    Links& operator=(Links&) noexcept { return *this; }
    Links& operator=(Links&&) noexcept { return *this; }
  };

  struct Value { // could be just a std::pair, but cleaner
    // default cstr needed for std::map::operator[]
    Value() = default;

    Value(ValueT& v) : value{v} {}

    ValueT value;
    Links links;
  };

  void linkit(Links& x) noexcept {
    x.next     = &ends;
    tail->next = &x;
    x.prev     = tail;
    tail       = &x;
  }

  void unlinkit(Links& x) noexcept {
    x.prev->next = x.next;
    x.next->prev = x.prev;
  }
};

// EOF class: Rest is demo usage code

template <class KeyT, class ValueT>
void print_in_insertion_order(const SequencedMap<KeyT, ValueT>& smap) {
  auto curr = smap.chead();
  while (true) {
    auto elem = smap.fromlink(*curr);
    std::cout << elem.first << " -> " << elem.second.value << "\n";
    if (curr == smap.ctail()) break;
    curr = curr->next;
  }
}

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.value << "\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)

  for (auto p: std::vector<std::pair<Key, Value>>{
           {"Mary", 10}, {"Alex", 20}, {"Johnny", 40}, {"Roman", 40}, {"Johnny", 50},
       }) {
    smap.insert_or_assign(p.first, p.second);
  }
  std::cout << "\nsorted by map\n";
  print_in_map_order(smap);

  std::cout << "\nsorted by insert\n";
  print_in_insertion_order(smap);

  std::cout << "\nretrieve by known key\n";
  auto key = "Alex";
  smap[key];
  ++smap[key];
  print_in_insertion_order(smap);

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

  std::cout << "\nchange value for new key: NewGuy++\n";
  ++smap["NewGuy"];
  print_in_insertion_order(smap);

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