Down and out in Swansea

Setting the scene... This is something I have wanted to do a few times throughout my C++ journey, which started about a year ago. Only when I started to understand templates and virtual functions did it become clear why this is not currently possible. Although it will be nice if the standard introduced it. Suppose we have the following data structures struct name { std :: string first, middle, last; }; struct address { int door; std :: string street; }; //... and the following Io modules and worker class class worker { public: template < typename T > void work(T & data) { std :: cout << "work! : " << typeid (data).name() << std :: endl; } }; class Io { protected: std :: unique_ptr < worker > w; public: Io() : w( new worker){} template < typename T > void push(T & data) { std :: cout << "from Io" << std :: endl...

Recap of locking data structures When working with more than one thread care needs to be taken to ensure that we eliminate problem like data races, which sometimes lead to  undefined behavior , and dead locks, which will stall the application altogether. These problems are related. We use locks to try and prevent data races, but when using locks we might introduce a dead lock situation (see this ). Our favorite C++ containers ( std::deque ,  std::stack , etc ) can be wrapped (coarse grained locking) to obtain thread safe variants. Although this does not harness a lot of the available concurrency, it is usually sufficient for the job. If we want to extract more concurrency out of the data structure we can use fine grained locking. To illustrate the difference, I will give two code examples. One where we implement a push  on a thread-safe stack using coarse grained locking and another using coarse grained locking. template < typename T > class coarse_stack {...

Today we are talking about equal_range . Take a look at the signatures   here . This is a handy little algorithm that returns the range (as a pair of forward iterators) where each item in the returned range matches the value (where what "matches" is defined by the Compare). We will look at a practical use in this post, that actually relates to a previous post on a piece of software called Contex.  Suppose we have a vector of strings and we have a vector of unique queries. We want to count the number of times a query appears in the vector of strings. A very obvious way to do it takes $O(ns)$ where $n$ is the length of the string vector and $s$ is the number of queries. This is not very good. There are (at least) two better ideas We can attempt to sweep the strings "at the same time" as the queries. We can carry out a binary search on a sorted version of the strings for the beginning and end of a range of strings that satisfy each query, for each query. Both...