Last active
December 4, 2019 20:07
-
-
Save oschonrock/6a3bd63ceb2be66fb32628ececd6e82c to your computer and use it in GitHub Desktop.
SequencedMap a C++ container like std::map which retains insertion order
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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"; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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