Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
SequencedMap a C++ container like std::map which retains insertion order
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";
}
}
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment