SequencedMap which retains insertion order - Design#2

Question

UPDATE: Current best state of a solution incorporating feedback and further development is in this answer.

Review on this Design#2 please:

Simple wrapper class template for std::map for the purpose of "retaining insertion order". This is quite a frequently asked question, here and here.

This is the follow on 2nd Design of a solution for this original question.

Code is still a bit rough, but it implements the new strategy:

1. Basically a std::map<KeyT,ValueT>
2. But the ValueT is wrapped in a struct which hold prev/next pointers to make a doubly linked list
3. These pointers are maintained on insertion and deletion
4. Thus rudimentary iteration in original insertion order is possible (to be improved -- input wanted on best way to do that)

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

template <class KeyT, class ValueT>
struct SequencedMapValue;

template <class KeyT, class ValueT>
class SequencedMap {

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

public:
  template <class K, class V>
  std::pair<MapItT, bool> insert_or_assign(const K& key, V&& value) {
    const auto map_it = map.find(key);
    if (map_it != map.end()) {
      map_it->second.v = value;
      return {map_it, false};
    }
    SequencedMapValue<KeyT, ValueT> s(std::forward<V>(value));
    MapValT pair            = std::make_pair(std::move(key), std::move(s));
    const auto ins_res      = map.insert(std::move(pair));
    auto [elem_it, was_new] = ins_res;
    if (tail) {
      tail->second.next    = &*elem_it;
      elem_it->second.prev = tail;
      tail                 = &*elem_it;
    } else {
      tail = &*elem_it;
      head = tail;
    }
    return ins_res;
  }

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

  ValueT& operator[](const KeyT& key) {
    const 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.v;
  }

  MapItT erase(const KeyT& key) {
    const auto map_it = map.find(key);
    if (map_it != map.end()) {
      // close gap in ptrs
      if (!map_it->second.next) {
        // last one
        tail                             = map_it->second.prev;
        map_it->second.prev->second.next = nullptr;
      } else if (!map_it->second.prev) {
        // this is head
        head                             = map_it->second.next;
        map_it->second.next->second.prev = nullptr;
      } else {
        // somewhere in the middle
        map_it->second.prev->second.next = map_it->second.next;
        map_it->second.next->second.prev = map_it->second.prev;
      }
    }
    return map.erase(map_it);
  }

  const MapT& getMap() const { return map; }

  MapValT* const ibegin() const { return head; }
  const MapValT* const cibegin() const { return head; }

private:
  MapT map;
  MapValT* tail = nullptr;
  MapValT* head = nullptr;
};

template <class KeyT, class ValueT>
struct SequencedMapValue {

  using MapT    = std::map<KeyT, SequencedMapValue<KeyT, ValueT>>;
  using MapValT = typename MapT::value_type;

  template <class V>
  SequencedMapValue(V&& v_) : v{std::forward<V>(v_)} {}

  ValueT v;
  MapValT* next = nullptr;
  MapValT* prev = nullptr;
};

// 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.ibegin();
  while (curr) {
    std::cout << curr->first << " -> " << curr->second.v << "\n";
    curr = curr->second.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.v << "\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);

}

I struggle in insert_or_assign() with all the "universal references" and different template params apparently doing "the same thing". I sprinkled some std::move and std::forward, and made it compile and work, but I am sure it's not right.

I also struggled breaking the recursive template Type params and Type aliases between SequencedMap and SequencedMapValue. It works without static_casting from void* now, but there is probably a better way. I need help on how to do the iterators cleanly.

--

The benchmark (separate code) has been filled out more as well, and it looks good compared to the original design. No more slow deletes. Really on average about the same as std::map (except, insertion ~35% slower). Compiled on clang-8 -std=C++17 -O3.

SequencedMap: insert 100,000=81.4451ms
SequencedMap: iterate in insertion order=0.844402ms
SequencedMap: Check sum=4990318
SequencedMap: modify 100,000 in insertion order=0.871902ms
SequencedMap: iterate in insertion order=0.792979ms
SequencedMap: Check sum=5090318
SequencedMap: delete 10,000=6.52532ms
SequencedMap: iterate in insertion order=0.83679ms
SequencedMap: Check sum=4581601
Map: insert 100,000=59.9917ms
Map: iterate in map order=3.19841ms
Map: Check sum=4990318
Map: modify 100,000 in map order=18.3977ms
Map: iterate in map order=3.66884ms
Map: Check sum=5090318
Map: delete 10,000=4.3003ms
Map: iterate in map order=2.59503ms
Map: Check sum=4581601

Answer 1

Never call map.erase(map.end()). Doing so is undefined.

There are some simple tricks for linked lists to avoid special-cases:

Define your own type for the links (prev and next), instead of letting loose pointers rattle around everywhere.

Also, arrange for a special value which on assignment does nothing:

struct links {
    links() = default;
    constexpr links(char) noexcept {}
    constexpr links& operator=(char) noexcept { return *this; }
    links *prev = this;
    links *next = this;
};

std::map<KeyT, std::pair<links, ValueT>> map;
links order;

void linkit(links& x) noexcept {
    x.next = order;
    order.prev->next = &x;
    x.prev = order.prev;
    order.prev = &x;
}

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

decltype(*map.begin())& fromlink(links& x) noexcept {
    auto& y = *map.begin();
    const auto offset = (char*)&y->second.first - (char*)y;
    return (decltype(y)&)((char*)&x - offset);
}

template <class K, class V>
std::pair<MapItT, bool> insert_or_assign(const K& key, V&& value) {
    auto r = map.insert_or_assign(key, std::pair<char, V&&>(
        '\0', std::forward<V>(value)));
    if (r.second)
        linkit(r.first->second.first);
    return r;
}

ValueT& operator[](const KeyT& key) {
    auto& x = map[key];
    if (!x.first.prev)
        linkit(x.first);
    return x.second;
}

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

Beware: All code is untested.

Answer 2

OK, in the interest of not inventing wheels, I tried boost::multi_index. Took half an hour to get over their approach, type syntax and their API.

But it's actually really good. Very flexible, very performant. And not that verbose for reasonable real world cases. It all seems a bit C++03, but that doesn't actually get in the way. In fact if you use modern features "like auto you can avoid some of the very verbose typename .... ::value_type type syntax, see below

Code does something similar to my code above (ie simple map with an additional "linked-list" sequence index) but using boost::multi_index:

#include <algorithm>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index_container.hpp>
#include <iostream>
#include <iterator>
#include <string>

using boost::multi_index_container;
using namespace boost::multi_index;

struct Pair {
  std::string key;
  int value;

  Pair(std::string key_, int value_) : key(key_), value(value_) {}

  friend std::ostream& operator<<(std::ostream& os, const Pair& p) {
    os << p.key << " -> " << p.value << "\n";
    return os;
  }
};

struct key {};

typedef multi_index_container<
    Pair, indexed_by<sequenced<>, ordered_unique<tag<key>, member<Pair, std::string, &Pair::key>>>>
    PairContainer;

template <typename Tag, typename MIC> void print_out_by(const MIC& mic) {
  auto& i = get<Tag>(mic);
  std::copy(i.begin(), i.end(), std::ostream_iterator<typename MIC::value_type>(std::cout));
}

int main() {

  PairContainer ps;
  ps.push_back(Pair("Johnny", 10));
  ps.push_back(Pair("Alex", 20));
  ps.push_back(Pair("Barty", 30));
  ps.push_back(Pair("Zoe", 40));
  ps.push_back(Pair("Vaughan", 50));

    int sum       = 0;
    for (auto it = ps.begin(); it != ps.end(); ++it) {
        sum += it->value;
    }
    std::cout << sum << "\n";
    {
        const auto& i = get<key>(ps);
        for (auto it = i.begin(); it != i.end(); ++it) {
        std::cout << *it;
        }
    }
    std::cout << sum << "\n";
    {
        for (auto it = ps.begin();  it != ps.end(); ++it) {
        std::cout << *it;
        }
    }
  return 0;
}

```

Answer 3

Integrating all the pieces. Quite nice now? Faster insert than my version at top (less branches I think!).

See below for state and history:

#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;

  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; }

  // is this portable? How dodgy to reinterpret_cast from a pair to this?
  struct MapExtValT {
    KeyT first;
    ValueT second;
    // Links _dummy_;
  };

  class Iterator {
  public:
    using value_type        = MapExtValT;
    using difference_type   = std::ptrdiff_t;
    using pointer           = MapExtValT*;
    using reference         = MapExtValT&;
    using iterator_category = std::bidirectional_iterator_tag;

    Iterator(SequencedMap<KeyT, ValueT>* m_, Links* curr_) : map(m_), curr(curr_) {}

    reference operator*() { return map->fromlink(*curr); }
    pointer operator->() { return &(map->fromlink(*curr)); }

    // clang-format off
    Iterator& operator++() { curr = curr->next; return *this; }
    Iterator& operator--() { curr = curr->prev; return *this; }
    // clang-format on

    bool operator!=(const Iterator& o) const { return curr != o.curr; }
    bool operator==(const Iterator& o) const { return curr == o.curr; }

  private:
    SequencedMap<KeyT, ValueT>* map;
    Links* curr;
  };

  Iterator begin() { return Iterator(this, head); }
  Iterator end() { return Iterator(this, &ends); }

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;

    // NOP copy/move asignment because it would break ptrs
    Links& operator=(Links&) noexcept { return *this; }
    Links& operator=(Links&&) noexcept { return *this; }
  };

  struct Value { // Could be just a std::pair. This is cleaner
    // default cstr needed for std::map::operator[]
    Value() = default;

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

    ValueT value;
    Links links;
  };

  MapExtValT& fromlink(Links& x) const noexcept {
    // MSVC 2019 balks at this assert Clang 8 passes it, but MSVC apparently runs fine anyway
    static_assert(std::is_standard_layout_v<MapValT>, "MapValT must have StandardLayout");
    return *reinterpret_cast<MapExtValT*>(reinterpret_cast<std::byte*>(&x) -
                                       offsetof(MapValT, second.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(SequencedMap<KeyT, ValueT>& smap) {
  for (auto& pair: smap) {
    std::cout << pair.first << " -> " << pair.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.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);

}

EDIT (4th Dec 2019):

1. Refactored code above.
2. Helper classes for "inner Value" and "links" now inner classes. Reducing public interface.
3. No longer using char('0') "hack/trick" to prevent change of Links ptrs upon assignment to existing map-key (was deemed too confusing). Using proper "no-op" move/copy assignment operators on Links now.
4. static_asserts for type restrictions
5. better "tests"

EDIT (4th Dec 2019 #2):

6. Added Iterator for the "insertion order". works well with external ranged for loop.

7. There is an interesting "reinterpret_cast" to MapExtvalIt which hides the Links member and gives the external user something that looks like a normal map std::pair. Neat. Good perf. But how portable is that?

8. Not clear how to present the other iterator (ie the normal sorted map order). mbeing() and mend() ? that won't work with "ranged for"?

Benchmark:

SequencedMap: insert 100,000=99.8293ms
SequencedMap: iterate in insertion order=0.849751ms
SequencedMap: Check sum=4990318
SequencedMap: modify 100,000 in insertion order=0.964927ms
SequencedMap: iterate in insertion order=0.914365ms
SequencedMap: Check sum=5090318
SequencedMap: delete 10,000=7.02706ms
SequencedMap: iterate in insertion order=0.821281ms
SequencedMap: Check sum=4581601
Map: insert 100,000=83.5828ms
Map: iterate in map order=6.86609ms
Map: Check sum=4990318
Map: modify 100,000 in map order=28.0204ms
Map: iterate in map order=7.2687ms
Map: Check sum=5090318
Map: delete 10,000=7.07613ms
Map: iterate in map order=5.52114ms
Map: Check sum=4581601