Ticket Maps

Saturday, 20 March 2021

It has been an increasingly common scenario that I've encountered where you have some ID that's monotonically increasing, such as a subscription or connection index, or user ID, and you need your C++ program to hold some data that's associated with that ID value. The program can then pass round the ID, and use that ID to access the associated data at a later point.

Over time, IDs can become invalidated, so the data associated with that value is removed, and you end up with a sparse set of currently-active IDs. You would therefore naturally lean towards using a map (whether a std::map, std::unordered_map or some other custom map) to associate the data with the ID.

Often such maps are implemented as node-based containers, which means that the nodes can be allocated at disparate memory addresses, which is bad for cache performance. Adding and removing nodes also always requires memory allocation/deallocation.

In his "Better Code: Relationships" presentation, Sean Parent describes an alternative implementation, which he calls the "Russian Coat-Check Algorithm". In this algorithm, the map is implemented as a vector of pairs of key/optional data. Because the keys come from a monotonically increasing index, the vector is always sorted, and inserts are always at the end. Entries can be removed by clearing the data, and if there are too many empty entries then the vector can be compacted. Lookups are always fast, because the vector is always sorted, so a simple binary search will find the right element.

Inspired by watching Sean's presentation at ACCU 2021 last week, I implemented what I call a Ticket Map (it maps a Ticket to a Value). This is an implementation of the algorithm Sean described, fleshed out to a full container. When you insert a value, it is assigned the next available ticket value. You can later access or erase the value using that ticket.

#include <string>
#include <iostream>
#include "ticket_map.hpp"

int main(){
    jss::ticket_map<int,std::string> map;

    auto ticket1=map.insert("hello");
    auto ticket2=map.insert("world");

    std::cout<<map[ticket1]<<" "<<map[ticket2]<<std::endl;

    map.erase(ticket1);
}

You can of course iterate through the container: in this case the iterators are Input Iterators, where the value_type is a std::pair<Ticket const&,Value&>. This allows you to access both the tickets and the raw elements, but also allows the iterator to provide a nice view over the data without exposing the std::optional implementation detail.

#include <string>
#include <iostream>
#include "ticket_map.hpp"

int main(){
    jss::ticket_map<int,std::string> map;

    auto ticket1=map.insert("hello");
    auto ticket2=map.insert("world");
    auto ticket3=map.insert("goodbye");

    for(auto& [ticket,value]: map){
      std::cout<<ticket<<": "<<value<<std::endl;
    }
}

The code is available on GitHub under the Boost Software License.

Enjoy!

Posted by Anthony Williams
[/ cplusplus /] permanent link
Tags: cplusplus, maps, containers
Stumble It! | Submit to Reddit | Submit to DZone

Comment on this post

If you liked this post, why not subscribe to the RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the left.

Design and Content Copyright © 2005-2024 Just Software Solutions Ltd. All rights reserved. | Privacy Policy