C++ in Competitive Programming: associative containers

This post concludes my introduction to C++ containers. We’ll meet other standard data structures such as lists, queues and heaps when needed along the way.

Some posts ago, I anticipated that understanding containers is crucial for adoperating standard algorithms effectively. In a few words, the reason is that each container has some special features or it’s particularly indicated for some scenarios. On the other hand, algorithms work only in terms of iterators, which completely hide this fact. That’s great for writing generalized code, but it also merits attention because for exploiting a particular property of a container, you generally have to choose the best option yourself.

The only “specialization” that algorithms (may) do is in terms of iterators. Iterators are grouped in categories, which basically distinguish how iterators can be moved. For instance, consider std::advance that moves an iterator by N positions. On random-access iterators, std::advance just adds an offset (e.g. it += N), that is a constant operation. On the other hand, on forward iterators (basically they can advance only one step at a time) std::advance is obliged to call operator++ N times, a linear operation.

Choosing – at compile time – different implementations depending on the nature of the iterators is a typical C++ idiom which works well in many situations (this technique is an application of tag dispatching, a classical C++ metaprogramming idiom). However, to exploit the (internal) characteristics of a container, we have to know how the container works, which (particular) member functions it provides and the differences between using the generic standard algorithm X and the specialized member function X.

As an example, I mentioned std::find and std::map::find. What’s the difference between them? Shortly, std::find is an idiomatic linear search over a range of elements. It basically goes on until either the target value or the end of the range is reached. Instead, std::map::find…Wait, I am not a spoiler! As usual, let me start this discussion through a challenge:

Some days ago I gave my birthday party  and I invited some friends. I want to know which name is the most common among my friends. Or, given a sequence of words, I want to know which one occurs the most.

In this trivial exercise we need a way to count occurrences of words. For example:

matteo riccardo james guido matteo luca gerri paolo riccardo matteo

matteo occurs three times, riccardo twice, the others once. We print matteo.

Imagine to count the words by incrementing a counter for each of them. Incrementing a counter should be a fast operation. Finally, we’ll just print the string corresponding to the greatest counter.

The most common data structures to do this task is generally known as associative array: basically, a collection of unique elements – for some definition of “uniqueness”, which – at least – provides fast lookup time. The most common type of associative container is a map (or dictionary): a collection of key-value pairs, such that each possible key appears just once. The name “map” resembles the concept of function in mathematics: a relation between a domain (keys) and a codomain (values), where each element of the domain is related (mapped) to exactly one element of the codomain.

Designing maps is a classic problem of Computer Science, because inserting, removing and looking up these correspondences should be fast. Associative containers are designed to be especially efficient in accessing its elements by key, as opposed to sequence containers which are more efficient in accessing elements by position. The most straightforward and elementary associative container you can imagine is actually an array, where keys coincide with indexes. Suppose we want to count the most frequent character of a string of lowercase letters:

	array<int, 26> freq{}; // letter counters
	for (auto c : str)
	++freq[c - 'a'];
	cout << "The most frequent letter is: " << char('a' + distance(begin(freq), max_element(begin(freq), end(freq))));

view raw The most frequent letter.cpp hosted with ❤ by GitHub

freq contains the frequencies of each lowercase letters (0 is a, 1 is b, and so on). freq[c – ‘a’] results in the distance between the char c and the first letter of the alphabet (‘a’), so is the corresponding index in the freq array (we already saw this idiom in the previous post). To get the most frequent char we just retrieve the iterator (a pointer, here) to the element with highest frequency (std::max_element returns such iterator), then we calculate the distance from the beginning of freq and finally we transform this index back to the corresponding letter.

Note that in this case lookup costs O(1). Although an array shows many limitations (e.g. cannot be enlarged, keys are just numbers lying in a certain range), we’ll see later in this series that (not only) in competitive programming these “frequency tables” are extremely precious.

A plain array does not help with our challenge: how to map instances of std::string?

In Computer Science many approaches to the “dictionary problem” exist, but the most common fall into a couple of implementations: hashing and sorting. With hashing, the idea is to – roughly speaking – map keys to integral values that index a table (array). The trio “insert, lookup, remove” has average constant time, and linear in the worst case. Clearly this depends on several factors, but explaining hash tables is beyond the target of this post.

The other common implementation keeps elements in order to exploit binary search for locating an element in logarithmic time. Often trees (commonly self-balancing binary search trees) are employed to maintain this ordering relation among the elements and also for having logarithmic performance on insert, lookup and removal operations.

The C++ STL provides both the hash-based (from C++11) and the sort-based implementations, providing also variants for non-unique keys (multi). From now I’ll refer to sort-based implementation as tree-based because this is the data structure used by the major C++ standard library implementers.

There is more: STL provides two kinds of associative containers: maps and sets. A map implements a dictionary – collection of key-value pairs. A set is a container with unique keys. We’ll discover that they provide pretty much the same operations and that under the hood they share a common implementation (clearly, either hash-based or tree-based). Also, a hash container and a tree container can be used almost interchangeably (from an interface point of view). For this reason, I’ll focus on the most used associative container: a tree-based map. We’ll discuss later about some general differences.

Please, give a warm welcome to the most famous C++ associative container: std::map. It’s a sorted associative container that contains key-value pairs with unique keys. Here is a list of useful facts about std::map:

• Search, removal, and insertion operations have logarithmic time complexity;
• elements are kept in order, according to a customizable comparator – part of the type and specified as a template argument (std::less by default – actually the type is different since C++17, read on for more details);
• iterators are bidirectional (pay attention that increments/decrements by 1 are “amortized” constant, whereas by N are linear);
• each map element is an instance of std::pair<const Key, Value>.

The latter point means that we are not permitted to change keys (because it would imply reordering). Eventually, you can get the entry, remove it from the map, update the key, and then reinsert it.

Ordered associative containers use only a single comparison function, that establishes the concept of equivalence: Equivalence is based on the relative ordering of object values in a sorted range.
Two objects have equivalent values with respect to the sort order used by an associative container c if neither precedes the other in c’s sort order:

	!(o1 < o2) // it's not true that o1 < o2
	&& //and
	!(o2 < o1) // it's not true that o2 < o1

view raw Equivalence of two objects.cpp hosted with ❤ by GitHub

In the general case, the comparison function for an associative container isn’t operator< or even std::less, it’s a user-defined predicate (available through std::key_comp member function).

An important observation: in C++, every time you have to provide a “less” comparison function, the standard assumes you implement a strict weak ordering.

Let’s use std::map to solve the challenge:

	map<string, int> freq;
	string curr;
	while (cin >> curr)
	{
	++freq[curr];
	}
	cout << max_element(begin(freq), end(freq), [](const auto& p1, const auto& p2){
	return p1.second < p2.second;
	})->first;

view raw The most frequent string.cpp hosted with ❤ by GitHub

How it works: as far as we read a string we increment the corresponding counter by 1. map::operator[] returns a reference to the value that is mapped to a key that is equivalent to a given key, performing an insertion if such key does not already exist. At the end of the loop, freq is basically a histogram of words: each word is associated with the number of times it occurs. Then we just need to iterate on the histogram to figure out which word occurs the most. We use std::max_element: a one-pass standard algorithm that returns the greatest element of a range, according to some comparison function (that is std::less be default, a standard function object which – unless specialized – invokes operator< on the objects to compare).

Given that map entries are pairs, we don’t use pair’s operator< because it compares lexicographically (it compares the first elements and only if they are equivalent, compares the second elements). For instance:

"marco", 1
"andrea", 5

according to pair::operator<, “marco” is greater than “andrea” then it will result the max_element. Instead, we have to consider only the second value of the pairs. Thus we use:

	[](const auto& p1, const auto& p2){
	return p1.second < p2.second;
	}

view raw Comparing only pair.second.cpp hosted with ❤ by GitHub

If your compiler does not support generic lambdas (auto parameters), explicitly declare const pair<const string, int>&. const string is not fussiness: if you only type string, you get an extra subtle copy that converts from pair<const string, int> to pair<string, int>. Bear in mind that entries of map are pair<const K, V>.

Suppose now we have an extra requirement: if two or more names occur the most, print the lexicographically least. Got it?

matteo riccardo matteo luca riccardo

In this case, “matteo” and “riccardo” occur twice, but we print “matteo” because lexicographically lower than “riccardo”.

How to accommodate our solution to fit this extra requirement? There’s an interesting effect of using a sorted container: when we forward iterate over the elements, we go from lexicographically lower strings to lexicographically greater strings. This property combined with max_element automatically supports this extra requirement. In fact, using max_element, if more than one element in the range is equivalent to the greatest element, it returns the iterator to the first such element. Since the first such element is (lexicographically) the lowest, we already fullfill the new requirement!

Guess if we want to print the lexicographically greatest string…it’s just the matter of iterating backward! Having clear in mind these properties is a great thing. In this series we’ll meet many others.

Let’s continue our journey through std::map. Suppose that part of another challenge is to make our own contacts application. We are given some operations to perform. Two of them consist in adding and finding. For the add operation, we will have to add a new contact if it does not exist, or to update it otherwise. For the find operation, we will have to print the number of contacts who have a name starting with that partial name. For example, suppose our list contains:

marco, matteo, luca

find(“ma”) will result in 2 (marco and matteo).

The best data structure for this kind of task is probably a trie, but the pragmatic competitive programmer knows that in several cases std::map suffices. We can take advantage of the fact that a map keeps things in order. The challenge is also an excuse to show you how to insert into a std::map, since there are different ways to achieve this task.

We have two cases:

1. insert/update an entry
2. count names starting with some prefix

Our map looks like:

map<string, string> contacts; // let's suppose the contact number to be a string as well

The first one has been discussed a lot in many books and blogs, so much that C++17 contains an idiomatic function insert_or_assign. In a few words, to efficiently insert or assign into a map, we first look for the contact in the structure and in case of a match we update the corresponding entry; otherwise we insert it.

This is the simplest way to do that:

contacts[toInsertName] = toInsertNumber;

You may ask: why in C++17 do we bother with a specific function for this one-liner? Because we are C++. Because that one-liner is succinct, but it hides a subtle cost when the entry is not in the map: default construction + assignment.

As we have seen, contacts[toInsertName] performs a lookup and returns either the corresponding entry or a brand-new one. In the latter case a default construction happens. Then, = toInsertNumber does an assignment into the just created string. Is that expensive? Maybe not in this case, but it may be in general, and this kind of things matters in C++.

Here is more enlightening example: suppose we have a cache implemented with std::map:

	const auto& entry = cache.fetch_or_insert(key, []{
	..lambda creating the entry, in case key is not there..
	});

view raw Hypothetical fetch_or_insert.cpp hosted with ❤ by GitHub

You don’t want to update anything if key is already there. Rather, you first look for the value corresponding to key and only if it’s not there you invoke the lambda to calculate it. Can you solve it by using operator[]? Maybe (it depends on the value type), but it’s not effective nor even efficient. Often std::map novices come up with this code:

	template<typename Gen>
	ValueType fetch_or_insert(const Key& key, Gen g)
	{
	auto it = data.find(key);
	if (it != end(data))
	{
	return it->second;
	}
	return data.emplace(key, g()).first->second;
	}

view raw Silly fetch_or_insert.cpp hosted with ❤ by GitHub

map::find locates the element with key equivalent to a certain key, or map::end if such element does not exist. map::emplace inserts a new element into the container constructed in-place with the given args if there is no element with the key in the container. emplace returns a pair<iterator, bool> consisting of an iterator to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place. True for “insertion”, false for “no insertion”.

This code implements what I call the infamous double-lookup anti-pattern. Basically, both find and emplace search the map. It would be better to – somehow – take advantage of the result of the first lookup to eventually insert a new entry into the map. Is that possible?

Sure.

This is the idea: if the key we look for is not in the map, the position it should be inserted in is exactly the position where the first element that does not compare less than the key is located. Let me explain. Consider this sorted list of numbers:

1 2 3 5 6 7 8

If we want to insert 4, where should it be inserted? At the position of the first number that does not compare less than 4. In other words, the first element greater or equal to 4. That is 5.

This is nothing more than what mathematics defines as lower bound. std::map provides lower_bound, and for consistency the STL defines std::lower_bound to perform a similar operation on sorted ranges. As a generic algorithm, lower_bound is a binary search.

Here is what the idiom looks like:

	template<typename Gen>
	ValueType fetch_or_insert(const Key& key, Gen g)
	{
	const auto lb = data.lower_bound(key);
	if (lb != end(data) && !(data.key_comp()(key, lb->first)))
	{
	return lb->second;
	}
	return data.emplace_hint(lb, key, g())->second;
	}

view raw Efficient std::map get or insert.cpp hosted with ❤ by GitHub

Since lower_bound returns the first element that does not compare less than key, it can be key itself or not. The former case is handled by the right hand side of the if condition: data.key_comp() returns the comparator used to order the elements (operator< by default). Since two equal elements do not compare less, this check has to be false. Otherwise, key is less than lb->first because lb points to one element past key (or to the end, if such element does not exist). Makes sense?

emplace_hint is like emplace, however it also takes an extra iterator to “suggest” where the new element should be constructed an placed into the tree. If correct, the hint makes the insertion O(1). map::insert has an overload taking this extra iterator too, resulting in a similar behavior (but remember that insert takes an already built pair).

A bit of simplification for pragmatic competitive programmers is when you do not use custom comparators: generally you may use operator== for checking equality:

if (lb != end(data) && key==lb->first)

Ha, C++17 has this insert_or_assign that should search the map and use Value’s operator= in case the entry has to be updated, or insert it otherwise (move semantics is handled as well). There is also another reason why insert_or_assign is important, but I’ll spend a few words about that leater, when unordered_map will be introduced.

Since I introduced lower_bound, I must say there is also an upper_bound: it locates the first element which compares greater than the searched one. For example:

1 2 3 4 5

upper_bound(3) locates 4 (position 3). What’s the point? Let’s turn our list into:

1 2 2 2 3 4

lower_bound(2) locates…2 (position 1), whereas upper_bound(2) results in position 4 (element 3). Combining lower_bound(2) with upper_bound(2) we find the range of elements equivalent to 2! Range is in C++ speaking (upper_bound(2) is one-past the last 2). This is extremely useful in multimap and multiset and indeed a function called equal_range which returns the combination of lower and upper bounds exists. equal_range is provided by all the associative containers (in unordered_* is only for interface interchangeability reason) and by the STL as an algorithm on sorted sequences – std::equal_range.

We’ll see applications of these algorithms in the future.

So, what about our challenge? Suppose it’s ok to use operator[] for inserting/updating elements – in this case string constructor + operator= are not a problem. We need to count how many elements start with a certain prefix. Is that easy? Sure, we have a sorted container, remember? Listen my idea: If we call lower_bound(P) we get either end, the first element equal to P or …suspense… the first element starting with P. Since lower_bound returns the position to the first element which does not compare less than P, the first element that looks like P$something is what we get if such element exists.

Now what? I’m sure you already did this step in your mind. We just iterate until we find either the end or the first element that does not start with P. From the previous post we already know how to verify if a string begins as another:

	auto lb = contacts.lower_bound(P);
	auto cnt = 0;
	if (lb != end(contacts))
	{
	while (lb != end(contacts) && (lb++)->first.compare(0, P.size(), P)==0)
	++cnt;
	}

view raw Counting strings starting with P.cpp hosted with ❤ by GitHub

We are paying both a prefix comparison and a linear iteration from lb (write it as O(|P|*K), where |P| is the length of the prefix P, and K is the number of strings starting with P). Advanced data structures that more efficiently deal with these – possible – problems exist, but they are beyond the scope of this post. In a moment I’ll do another observation about this code.

I realized that the post is becoming longer than I imagined, so let me recap what we have met so far:

• How to insert:
  • operator[] + operator=;
  • infamous double-lookup anti-pattern (e.g. find + insert);
  • efficient “get or insert”: lower_bound + emplace_hint/insert;
  • efficient “get or assign”/”insert or assign”: lower_bound + Value’s operator=;
  • C++17 insert_or_assign.
• How to lookup:
  • find (aka: exact match);
  • lower_bound/upper_bound (aka: tell me more information about what I’m looking for);
  • operator[] (aka: give me always one instance – eventually new, if can be default-constructed);
  • bonus: at (aka: throw an exception if the element is not there);
  • bonus: count (aka: how many elements equivalent to K exist? 0 or 1 on non-multi containers).
• Taking advantage of sorting. For instance:
  • we combined max_element’s “stability” – hold the first max found – with map’s order to get the max element that is also the lexicographically least (or the greatest, by iterating backward);
  • we learnt how to locate and iterate on elements which start with a given prefix.

To erase an element, you just call map::erase(first, last), or erase(iterator), or erase(key). More interesting is how to implement erase_if, an idiom simplified by C++11 because now erase returns the iterator to the last removed element. This idiom can be applied to every associative container:

	template <typename Assoc, typename UnaryPred>
	void erase_if(Assoc& container, UnaryPred p)
	{
	for (auto it = begin(container); it != end(container); )
	{
	if (p(*it))
	it = container.erase(it);
	else
	++it;
	}
	}

view raw Kind of erase_if for associative containers.cpp hosted with ❤ by GitHub

 

Design choices

 

So, we still have an open question, right? What’s the difference between std::find and map::find?

You know, std::find is a linear search on a range. Now, I hope you understood that map::find is a logarithmic search and it uses a notion of equivalence, instead of equality to search elements.

Actually, there is a bit more.

Let’s raise the bar: what’s the difference between std::lower_bound and map::lower_bound? First of all: is it possible to use std::lower_bound with map::iterator? std::lower_bound requires simple forward iterators thus the answer is yes. So what?

Basically, std::lower_bound – just like all the other algorithms – works only in terms of iterators; on the other hand map::lower_bound – just like all the other map’s algorithms – exploits map’s internal details, performing better. For example, std::lower_bound uses std::advance to move iterators and you know that advancing a map::iterator results in linear time. Instead, map::lower_bound does a tree traversal (an internal detail), avoiding such overhead.

Although exceptions exist, the rule of thumb is: if a container provides its own version of a standard algorithm, don’t use the standard one.

I tell you a story about this rule. Remember that the comparator is part of the static interface of an associative container (it’s part of the type), unlike what happens in other languages like C# where the comparator is decoupled from the type and can be dynamically injected:

Dictionary<int, string> dict = new Dictionary<int, strint>(StringComparer.OrdinalIgnoreCase);

Some time ago I had a discussion with a collegue about this aspect of C++: he was using a map<string, SomeValueType> to store some information, but he was using it only for case-insensitive searches by calling std::find (the linear one). That code made my hair stand on end: “why not using a case-insensitive comparator and making this choice part of the map type?” – I asked. He complained: “C++ is breaking incapsulation:  I won’t commit my map to a specific comparator. My clients mustn’t know how elements are sorted”.

At first blush I got annoyed, but after a couple of emails I understood his point (it was about the architecture of the system he designed, rather than about C++ itself). At the end of a quite long  – and certainly interesting – discussion, I come up with a solution to – more or less – save both ways: I introduced a new type which inherited from std::map and allowed to inject a comparator at construction time, like in C# (using less<> by default). I don’t recommend this approach (for example, because the comparator can’t be inlined and every comparison costs a virtual call – it uses std::function under the hood), but at least we are not linearly searching the map anymore…

This story is just to say: use containers effectively. Don’t go against the language. std::map is not for linear search, as std::vector is not for push elements at front.

I’d like mentioning a fact about the cache. std::map is generally considered a cache-unfriendly container. Ok we can use allocators, but try to understand me: by default we are just pushing tree nodes into the heap, moving through indirections, etc. On the other hand, we are all generally happy with contiguous storage, like vectors or arrays, aren’t we? Is that possible to easily design cache-friendly associative containers? It is, when the most common operation is lookup. After all, what about using binary search on a sorted vector? That’s the basic idea. Libraries like boost (flat_map) provide this kind of container.

As my friend Davide Di Gennaro pointed out, given the triplet of operations (insert, lookup, erase), the best complexity you get for a general-purpose usage is O(logN, logN, logN). However, you can amortize one operation, sacrificing the others. For example, if you do many lookups but a few insertions, flat_map performs O(N, logN, N), but the middle factor is much lower (e.g. it’s cache-friendly).

Consider this example: we want to improve our algorithm to count our contact names which start with a certain prefix. This time, we use a sorted vector and std::lower_bound to find the first string starting with the prefix P. In the previous code we just iterated through the elements until a mismatch was found (a string not starting with P).

This time, we try thinking differently: say we have found the position of the first string starting with P. Call that position “lb” (lower bound). Now, it should be clear that we must find the next string not starting with P. Define this string to be the first greater than lb, provided that “greater” means “not starting with P”. At this point, do you remember which algorithm finds the first element greater than another, in a sorted sequence?

std::upper_bound.

So we can employ upper_bound, using a particular predicate, and we expect a logarithmic complexity. What will this predicate look like? Suppose we count “ma” prefixes. Strings starting with “ma” are all equivalent, aren’t they? So, we can use a predicate which compares only “ma” (P) with the current string. When the current string starts with P then it’s equivalent to P and the predicate will return false. Otherwise, it will return true. After all, starting the search from lower_bound’s result, we can get either ma$something or $different-string:

	const auto lb = lower_bound(begin(sortedVec), end(sortedVec), P);
	const auto ub = std::upper_bound(lb, end(sortedVec), P, [](const string& s1, const string& s2){
	return s2.compare(0, s1.size(), s1); // s1 is P
	});
	cout << distance(lb, ub);

view raw Counting strings starting with P.cpp hosted with ❤ by GitHub

Some clarifications: the first parameter of the lambda is always the value (or a conversion) of the upper bound to search for in the range (P, in our case). This is a guarantee to remember. The lambda returns false only when the current string is not starting with P (s1, inside the lambda body). std::upper_bound will handle the rest.

Why didn’t we use this approach directly on std::map? As I said at the beginning of this section, standard algorithms works in terms of iterators. Using std::upper_bound on std::map would result in logN * N. That additional N factor is caused by advancing iterators, that is linear on map::iterators. On the other hand, sorted vector provides random access iterators and so the final cost of counting prefixes is O (|P|*logN), given that we have sacrificed insert and removal operations (at most, linear).

 

Recent additions

 

C++14 and C++17 add new powerful tools to associative containers:

• Heterogeneous lookup: you are no longer required to pass the exact same object type as the key or element in member functions such as find and lower_bound. Instead, you can pass any type for which an overloaded operator< is defined that enables comparison to the key type. Heterogenous lookup is enabled on an opt-in basis when you specify the std::less<> or std::greater<> “diamond functor” comparator when declaring the container variable, like: map<SomeKey, SomeValue, less<>>. See here for an example. This works only for sorted associative containers.
  This feature is also kwnown by some people as “transparent comparators”, because comparators that “support” this feature have to define a type is_transparent = std::true_type. This is basically required for backwards-compatibility with existing code (see for example here for a more detailed explanation). A terrific usage of this feature is, for example, searching on a map<string, Val> by passing a const char* (no conversion to string will be performed).

• try_emplace and insert_or_assign, as an improvement of the insertion interface for unique-keys maps (more details here).

• Ordered By Default: Mostly for both design and ABI compatibility reasons, ordered associative containers now specify as a default compare functor the new std::default_orderer_t, (that behaves like std::less – more details here).

• Splicing maps and sets: (following words by Herb Sutter) you will now be able to directly move internal nodes from one node-based container directly into another container of the same type (differing at most in the comparator template parameter), either one node at a time or the whole container. Why is that important? Because it guarantees no memory allocation overhead, no copying of keys or values, and even no exceptions if the container’s comparison function doesn’t throw. The mechanics are provided by new functions .extract and .move, and corresponding new .insert overloads (approved proposal here).

• Structure bindings: we should be able to iterate on maps this way:

	for (auto [key, value] : myMap) {
	//...
	}

view raw Enjoying C++17 structure bindings (or, pretty iterating on std::map).cpp hosted with ❤ by GitHub

 

A few words about unordered_map

 

We end this long post by spending some words about unordered associative containers. I don’t show you multi* containers because they are more or less the same as the corresponding non-multi ones. Clearly, they support multiple instances of the same key and, as I said, equal_range plays an important role for lookups. I’ll probably spend more time on multi containers when needed in future challenges.

After this section we’ll see a final example using unordered_set.

As std::map does, std::unordered_map contains key-value pairs with unique keys. Unlike std::map, internally the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into. For this reason, search, insertion, and removal of elements have average constant-time complexity. Due to the nature of hash, it’s hard/impossible to know in advance how many collisions you will get with your hash function. This can add an element of unpredictability to the performance of a hash table. For this reason we use terms like “average”, “amortized” or “statistically” constant-time when referring to operations of a hash container.

This is not a discussion on hash tables, so let me introduce some C++ things:

• STL provides a default std::hash template to calculate hash of standard types;
• std::hash can be eventually specialized for your types (or you can specify your own functor);
• when a collision happens, an “equality” functor is used to determine if two elements in the same bucket are different (std::equal_to by default);
• it’s possible to iterate through the elements of a bucket;
• some hash-specific functions are provided (like load_factor, rehash and reserve);
• unordered_map provides almost all the the functions of std::map.

The latter point simplify our life to interchange std::map with std::unordered_map. There are two important things to say about this fact: 1) lower_bound and upper_bound are not provided, however equal_range is; 2) passing hints to unordered_ containers insertion functions is not really useful – actually it is to make the insertion “exit quickly”.

We know that on ordered associative containers, conditional insertion with lower_bound is the best way of performing an “insert or update”. So what? How can we say that ordered/unordered containers are more or less interchangeable if we miss lower_bound/upper_bound? We may apply equal_range:

	template<typename Gen>
	ValueType fetch_or_insert(const Key& key, Gen g)
	{
	const auto er = data.equal_range(key);
	if (er.first != er.second)
	{
	return er.first->second;
	}
	return data.emplace_hint(er.first, key, g())->second;
	}

view raw Universal map insert that works with both std::map and std::unordered_map.cpp hosted with ❤ by GitHub

This idiom is equivalent to the one using lower_bound (both semantically and from a performance point of view), plus it works on unordered maps.

Note that in C++17, try_emplace and insert_or_assign will dramatically improve the usability of unordered associative containers that will efficiently handle the case when we need to first perform a lookup and eventually insert a new element if that element is not present (first of all, the hash value won’t be recalculated). That’s the real value of such additions: not only using insert_or_assign is more efficient, but also clearer and truly interchangeable.

 

Tree or Hash?

 

There are some general rules/facts to take into account when in doubt between tree-based or hash-based containers. They are general, this means – as always – that when really in doubt you can start with one, profile your code, change to the other (again, thanks to interface compatibility), profile again, and compare.

By the way, here are some facts for the pragmatic competitive coder:

• on average, hash-based lookup is faster;
• generally, hash-based containers occupy more memory (e.g. big array) than tree-based ones (e.g. nodes and pointers);
• tree-based containers keep elements in order, is that feature important? (e.g. prefix lookups, get top elements, etc);

 

An application of unordered_set

 

Since I introduced std::unordered_map…let’s do a challenge involving unordered_set 🙂 Jokes apart, this long post hosted mostly maps, I’d like concluding with set, a really helpful and minimal associative container that we will meet again in the future.

That’s the challenge:

Given N unique integers, count the number of pairs of integers whose difference is K.

For example, for this sequence:

1 5 3 4 2

With K = 2, the answer is 3 (we have three pairs whose difference is 2: 4-2, 3-1, 5-3).

The trivial solution to this problem has quadratic time complexity: we enumerate all the pairs and we increment a counter when the difference is K.

The way to tackle this problem is to convert the problem space from one in which we consider pairs to a search for a single value. The i-th element A contributes to the final count only if A + K is in the sequence. For instance:

1 5 3 4 2

With K = 2. 1 contributes because 1 + 2 = 3 is in the list. Likewise, 3 is fine because 3 + 2 = 5 is in the list. And the same for 2, because we spot 2 + 2 = 4.

We can then store the input into an unordered_set (on average, constant time lookup), iterate on the elements and for each value A search for A + K:

	int N, K;
	cin >> N >> K;
	unordered_set<int> input;
	copy_n(istream_iterator<int>(cin), N, inserter(input, end(input)));
	cout << count_if(begin(input), end(input), [&](int currElem){
	return input.count(currElem+K);
	});

view raw Counting pairs whose difference is K.cpp hosted with ❤ by GitHub

Some sugar: std::count_if makes it clear that we are counting how many elements satisfy a predicate. Our predicate is true when currElem + K exists in the set: we use unordered_set::count(A) to get the number of elements equal to A (either 0 or 1 since we use a non-multi set). As an idiom, on non-multi associative containers, container::count(Key) gives 1 (say, true) if Key exists, 0 (say, false) otherwise.

On average, this solution has linear time complexity.

Another approach that uses no extra space and that involves sorting exists. Can you find it?

That’s enough for now.

Recap for the pragmatic C++ competitive coder:

• Don’t reinvent containers whenever standard ones fit your needs. Consider STL associative containers:
  • std::map, std::set, std::multimap and std::multiset are sorted, generally implemented as self-balancing binary-search trees;
  • std::unordered_map, std::unordered_set, std::unordered_multimap and std::unordered_multiset are not sorted, imlemented as hash tables;
• Understand idioms to adoperate STL associative containers effectively:
  • Does an element with key equivalent to K exist? Use count(K);
  • Where is the element with key equivalent to K? Use find(K);
  • Where should the element with key equivalent to K be inserted? Use lower_bound(K) on sorted containers;
  • Insert a new element: use emplace, insert;
  • Insert a new element, knowing where: use emplace_hint, insert (only sorted containers take advices effectively,  unordered ones are presumptuous!);
  • Insert or update an element: operator[] + operator=, (C++17) insert_or_assign, equal_range + hint insertion (this is also for interface compatibility between ordered/unordered), lower_bound + hint insertion (only on sorted containers);
  • Get the element corresponding to key equivalent to K, or default if not present: use operator[K];
  • Get the element corresponding to key equivalent to K, or exception if not present: use at(K);
  • Erase elements: use erase(K), erase(first, last), erase(it).
• Understand the difference between containers member functions and STL generic algorithms. For example:
  • std::find and $associative_container::find do different searches, using different criteria;
  • std::lower_bound and $sorted_container::lower_bound do the same, but the former performs worse than the member function because the latter works in terms of the container internal details and its structure.
• Exploit standard algorithms properties. For example:
  • std::max_element and std::min_element are “stable”: max/min returned is always the first one found.
• Prefer standard algorithms to hand-made for loops:
  • std::max_element/min_element, to get the first biggest/smallest element in a range;
  • std::count/count_if, to count how many elements satisfy specific criteria;
  • std::find/find_if, to find the first element which satisfies specific criteria;
  • std::lower_bound, std::upper_bound, std::equal_range, to find the “bounds” of an element within a sorted range.

Either capture this or copy *this

This post is just a reminder to myself because I fell for it, again…Well, let me step back and explain the scenario.

Suppose we are using this generic approach for memoization:

template <typename R, typename... Args>
auto memoize(R(*fn)(Args...))
{
    std::map<std::tuple<Args...>, R> table;
    return [fn, table](Args... args) mutable -> R {
        auto argt = std::make_tuple(args...);
        auto memoized = table.find(argt);
        if(memoized == table.end())
        {
            auto result = fn(args...);
            table[argt] = result;
            return result;
        }
        else
        {
            return memoized->second;
        }
    };
}

Suppose also – at some point – two new requirements pop up:

• ability to remove/update some entries of the table – because something changes somewhere else and those results become old,
• ability to switch to other functions (the table is not needed there).

We decide to store the table and the lambda into a struct. For the sake of simplification, this is a specialized version of such a class using a toy-function simulate:

struct Memoization
{
    Memoization()
    {
        calc = [this](int i)
        {
            auto memoized = table.find(i);
            if(memoized == table.end()) {
                auto result = simulate(i); // <- somewhere
                table[i] = result;
                return result;
            } else {
                return memoized->second;
            }
        };
    }

    function<int(int)> calc;
    std::map<int, int> table;
};

Even if this design is probably silly, we can easily satisfy both the requirements (e.g. calc can be set to something else, and table is fully accessible).

This code is fine for rapid prototyping, so we don’t refactor it yet but instead we experiment a bit more. For example, we create a factory for creating different Memoization instances depending on some configuration. Each configuration merely results in a new core function to use (e.g. remember the second requirement). Since it’s prototyping, we leave the constructor as is and we instead set the function by hand:

Memoization CreateMemo(const Configuration& config)
{
   Memoization memo;
   // using config to create memo
   // e.g. memo.calc = ...
   return memo;
}

We try this code and we note that it behaves differently on two compilers: on Visual Studio 2013 we get a crash at some point while calling calc(), instead on clang it seems to work smoothly. We start debugging and we immediately spot what’s going on…Do you note that we are one step away from falling into a dangling reference problem? Actually, this accident happens on both clang and Visual Studio, but some (un)lucky condition makes this work on the former.

The culprit – in this case – is RVO, but the issue is…both capturing this into calc – that is a member variable – and copying/moving *this.

By capturing this, we have coupled calc to this->table, that won’t change anymore – say when you do move (or copy). this has not special treatment inside the callable object created by the lambda expression. It’s just a Memoization pointer and when the lambda gets moved (or copied), so does the pointer. Shallowly.

In our factory function, RVO is probably working a bit differently between clang and VS. VS is not using RVO here, clang instead uses RVO and the problem is apparently concealed. By disabling RVO on clang (e.g. -fno-elide-constructors), we get the same problem found on VS.

Did you get the point? In case of the original “memoized” version of calc (which captures this), after the move (or the copy), the returned Memoization instance has a reference to the local memo->table, not to the new one. Finally, the local temporary instance is destroyed and we get a dangling reference. This problem is subtle since the code could still “work” under certain conditions – e.g. RVO. It should be clear that copying instead of moving has the same effect.

Maintaining the original design, the problem can be quickly solved, for example by constructing the object directly:

class Memoization
{
public:
   Memoization()
   {
    // same as before
   }

   Memoization(function<int(int)> calcFn)
      : calc(calcFn)
   {
   // ...
   }
// ...
};

Memoization CreateMemo(const Configuration& config)
{
   if (config. ...)
      return {...} // won't copy nor move
   //...
}

But the main issue holds and this could lead to disaster:

Memoization m1;
auto m2 = m1; // [this] in m2.calc points to m1

Not only is it dangerous, but also wrong: you probably expect each Memoization instance has its own copy of the table – i.e. for this reason a solution – say – with shared ownership of the table doesn’t fit well.

At the end of the story we changed our design and we came up with another better solution. But this is not the main point of the article. Even if my example is probably goofy, this experience left a valuable lesson: capturing this into a member variable lambda is valid C++ code and may cause headache if we copy/move *this. Sometimes I think we have a duty to set some limits, for preventing traps other people could fall into. For this reason, I came to a couple of observations:

(You understand that moving instead of copying does not twist the meaning, so let me just mention copying so I do not need to write copy/move every time).

First, we usually don’t need to capture this into a member variable lambda at all. Exploring better ways is always more advisable.

Some of you could still complain that C++ is missing an opportunity by letting this behavior go undisturbed. You could expect the compiler magically sets the this pointer to the copied instance, don’t you? Honestly, I have no strong opinions on that, I’m just thinking aloud.

Second: we can judge pragmatically. Capturing this into a member variable lambda and copying *this just do not get along. Doing either is realistically better than adding some special treatment.

For this reason, I see a terse idiom: either capture this into a member variable lambda or copy *this (or neither).

This is eventually another subtle case the Rule of Zero does not cover and – in case you cannot live without capturing this – I think deleting copy and move operations in the host class is such a desirable design decision to apply (and to document?) – being understood that maybe you don’t need to capture this into a member variable lambda at all.

Bring named parameters in modern C++

[Note: thanks to Davide Di Gennaro for having reviewed this post and for having suggested some improvements. A paragraph has been completely written by Davide.]

[From Wikipedia] In programming, named parameters refer to a computer language’s support for function calls that clearly state the name of each parameter within the function call itself. A function call using named parameters differs from a regular function call in that the values are passed by associating each one with a parameter name, instead of providing an ordered list of values.

Compare with a traditional positional function call:

createArray(10, 20); // what does this mean, precisely?
createArray(length=10, capacity=20); // oh, I see...
createArray(capacity=20, length=10); // same as previous

A typical example:

// some pseudo-language
window = new Window {
   xPosition = 10,
   yPosition = 20,
   width = 100,
   height = 50
};

This approach is especially useful if a function takes a large number of optional parameters, and users are usually going to accept the default for most of them.
Several languages support named parameters (e.g. C#, Objective-C, …). C++ does not. In this post, I’m going to explore some of the classical ways to emulate named parameters in C++ as well as mention new approaches.

Comments

Only to mention, the most trivial way to emulate named parameters is through comments 🙂

Window window {
 10, // xPosition
 20, // yPosition
 100, // width
 50 // height
};

This approach is very popular among windows developers, as MSDN pubishes Windows API usage examples with such comments.

Named Parameter Idiom

Imported from Java programming style is the Named parameter idiom (and this is just another post about). The idea is simple: create a proxy class which houses all the parameters. Optional ones are settable via a fluent interface (e.g. by using method chaining):

// 1
File f { OpenFile{"path"} // this is mandatory
   .readonly()
   .createIfNotExist()
   . ... };

// 2 classical version (not compliant with the auto-everything syntax)
File f = OpenFile { ... }
   .readonly()
   .createIfNotExist()
   ... ;

// 3 for auto-everything syntax just add a layer (I prefer 1)
auto f = CreateFile ( OpenFile("path")
 .readonly()
 .createIfNotExists()
 . ... ));

OpenFile is a sort of parameter object and File’s constructor accepts an OpenFile instance. Some authors (for instance, here) argue that OpenFile should have only private members and declare File as friend. This makes sense if you want to add more complex logic to set your parameters via the fluent interface. If you merely want to set plain parameters then a public struct suffices.

In this approach:

• mandatory parameters are still positional (as the constructor of OpenFile is a regular function call),
• optional parameters must be copy/move-assignable (basically, settable) – possible runtime penalty,
• you need to write an extra class (the proxy).

I – almost – never found usages in critical code.

A final note: the fluent interface can be polymorphic as I wrote more than two years ago.

Parameter Pack Idiom

Similar to the one above it’s the parameter pack idiom – from Davide Di Gennaro’s Advanced C++ Metaprogramming – a technique using proxy objects to set parameters via assignment operator (=), resulting in a sweet syntactic sugar:

MyFunction(begin(v), end(v), where[logger=clog][comparator=greater<int>()]);

The actors involved here are:

1. logger and comparator are global constants; the assignment operator just returns a wrapped copy of the assigned value,
2. where is a global constant of type “parameter pack”, whose operator[] just returns a new proxy that replaces one of its members with the new argument.

In symbols:

where = {a, b, c }
where[logger = x] → { a,b,c }[ argument<0>(x) ]  →   {x,b,c}

Sketching an implementation, just to give you an idea:

// argument
template <size_t CODE, typename T = void>
struct argument
{
   T arg;
   argument(const T& that)
      : arg(that)
   {
   }
};

// void argument - just to use operator=
template <size_t CODE>
struct argument<CODE, void>
{
   argument(int = 0)
   {
   }
   template <typename T>
   argument<CODE, T> operator=(const T& that) const
   {
     return that;
   }
   argument<CODE, std::ostream&> operator=(std::ostream& that) const
   {
      return that;
   }
};

// argument pack (storing the values)
template <typename T1, typename T2, typename T3>
struct argument_pack
{
   T1 first;
   T2 second;
   T3 third;
   argument_pack(int = 0)
   {
   }
   argument_pack(T1 a1, T2 a2, T3 a3)
     : first(a1), second(a2), third(a3)
   {
   }
   template <typename T>
   argument_pack<T, T2, T3> operator[](const argument<0, T>& x) const
   {
      return argument_pack<T, T2, T3>(x.arg, second, third);
   }
   template <typename T>
   argument_pack<T1, T, T3> operator[](const argument<1, T>& x) const
   {
      return argument_pack<T1, T, T3>(first, x.arg, third);
   }
   template <typename T>
   argument_pack<T1, T2, T> operator[](const argument<2, T>& x) const
   {
      return argument_pack<T1, T2, T>(first, second, x.arg);
   }
};

enum { LESS, LOGGER };
const argument<LESS> comparator = 0;
const argument<LOGGER> logger = 0;
typedef argument_pack<basic_comparator, less<int>, std::ostream> pack_t;
static const pack_t where(basic_comparator(), less<int>(), std::cout);

For the complete code, please refer to Davide’s book.

While this technique may look interesting, in practice it’s hard to generalize. In the book, in fact, it’s included as an example of “chaining” multiple calls to operator[].

Tagging

Andrzej Krzemieński published an interesting post Intuitive interface, where he mentions an alternative approach.
Named parameters are introduced by companion tags (empty structs used just to select different overloads of the same function). Notable examples of tags are from the STL:

std::function<void()> f{std::allocator_arg, a}; // treats a as an allocator instead of a callble object
std::unique_lock<std::mutex> l{m, std::defer_lock}; // don't lock now

Andrzej proposes tags to improve readability:

// not real STL
std::vector<int> v1(std::with_size, 10, std::with_value, 6);

I like his approach, but – as it stands – you possibly need to create lots of overloads and you cannot choose the order of the parameters. However, there are no requirements on copy-assignment, default values and forwarding is also clear. From the article: “However, tags are not an ideal solution, because they pollute the namespace scope, while being only useful inside function (constructor) call.”

Additionally (from the comments to the article) a reader proposes a slightly different idea that uses a proxy:

std::vector<int> v1(std::with_size(10), std::with_value(6));

Boost

Boost has the Parameter Library.

It’s possibly the most complete option if you really need named parameters in C++. An example:

// class code
#include <boost/parameter/name.hpp>
#include <boost/parameter/preprocessor.hpp>
#include <string>

BOOST_PARAMETER_NAME(foo)
BOOST_PARAMETER_NAME(bar)
BOOST_PARAMETER_NAME(baz)
BOOST_PARAMETER_NAME(bonk)

BOOST_PARAMETER_FUNCTION(
   (int), // the return type of the function, the parentheses are required.
   function_with_named_parameters, // the name of the function.
   tag, // part of the deep magic. If you use BOOST_PARAMETER_NAME you need to put "tag" here.
   (required // names and types of all required parameters, parentheses are required.
      (foo, (int))
      (bar, (float))
   )
   (optional // names, types, and default values of all optional parameters.
      (baz, (bool) , false)
      (bonk, (std::string), "default value")
   )
)
{
   if (baz && (bar > 1.0)) return foo;
      return bonk.size();
}

//client code
function_with_named_parameters(1, 10.0);
function_with_named_parameters(7, _bar = 3.14);
function_with_named_parameters( _bar = 0.0, _foo = 42);
function_with_named_parameters( _bar = 2.5, _bonk= "Hello", _foo = 9);
function_with_named_parameters(9, 2.5, true, "Hello");

Modern named parameters

Modern C++ opened some new doors. Can the new language features lead to slimmer implementations of named parameters?

Lambdas

Method chaining is verbose. I don’t like adding all the functions returning the object itself. What about defining just a struct and assign all the members through a lambda?

struct FileRecipe
{
   string Path; // mandatory
   bool ReadOnly = true; // optional
   bool CreateIfNotExist = false; // optional
   // ...
};

class File
 {
   File(string _path, bool _readOnly, bool _createIfNotexist)
      : path(move(_path)), readOnly(_readOnly), createIfNotExist(_createIfNotExist)
 {}

private:
   string path;
   bool readOnly;
   bool createIfNotExist;
 };

auto file =  CreateFile( "path", [](auto& r) { // sort of factory
   r.CreateIfNotExist = true;
});

You still have to provide a parameter object but this approach scales quite better than the classical named parameter idiom in which even chaining functions have to be written.

A variant consists in making File constructible from a FileRecipe (like the named parameter idiom).

How to improve the fluency of mandatory parameters? Let’s mix this approach with tags:

auto file =  CreateFile( _path, "path", [](auto& r) {
   r.CreateIfNotExist = true;
 });

But they are still positional. If you rest easy with a runtime error if a mandatory parameter is missing then use an optional type and check it at runtime.

CreateFile is trivial and left to the reader.

I’ve recently used this approach to configure test recipes and mocks. For example, I needed to create tests of a trivial dice game. Every game had a configuration and tests used to look like:

TEST_F(SomeDiceGameConfig, JustTwoTurnsGame)
{
   GameConfiguration gameConfig { 5u, 6, 2u };
}

By using the approach above we could have:

TEST_F(SomeDiceGameConfig, JustTwoTurnsGame)
{
   auto gameConfig = CreateGameConfig( [](auto& r) {
       r.NumberOfDice = 5u;
       r.MaxDiceValue = 6;
       r.NumberOfTurns = 2u;
   });
}

Diehards may suggest a macro to reduce verbosity:

TEST_F(SomeDiceGameConfig, JustTwoTurnsGame)
{
   auto gameConfig = CREATE_CONFIG(
       r.NumberOfDice = 5u;
       r.MaxDiceValue = 6;
       r.NumberOfTurns = 2u;
   );
}

Exploiting Variadics

Variadics can improve techniques I described above. What about Andrej’s tags approach? Tags could be preferred over the lambda + parameter object because you don’t have to create another object, you don’t have problems with settability and you consider all the parameters the same (e.g. by using the lambda approach you have to treat mandatory parameters differently). But I think tags would be better, if I could:

• define only one overload of my constructor (or function),
• decide the order of the parameters (pairs tag-value),
• the two above + having optional and mandatory parameters.

Something simple like:

File f { _readonly, true, _path, "some path" };

or (my preference):

File f { by_name, Args&&... args) {} 

My idea is: I just want to use variadics to let the user decide the order and let her omit optional parameters.

Imagine two constructors:

File(string path, bool readonly, bool createIfNotExist) {} // all mandatory

template<typename... Args>
File(by_name_t, Args&&... args) {}

A instance of File can be created by using both. If you use the variadic one then I’ll look for all parameters in the pack and delegates the other constructor to really make the instance. Search is (at compile-time) linear over the pack that contains parameters in the order chosen by the caller.

[Note: my implementation is just a proof of concept I did more than one year ago (I only added decltype(auto) somewhere). It could be done better and better.]

Here is how the class designer may look at her class:

File(string path, bool readonly, bool createIfNotExists /*...*/)
   : _path (move(path)), _createIfNotExist(createIfNotExist), _readonly(readonly) // ,etc...
{
}

template<typename Args...>
File(named_tag, Args&&... args)
   : File{ REQUIRED(path), OPTIONAL(read, false) // , etc... } // delegating
{
}

Prior to show you a working code, it’s clear we can apply the same idea to proxies and obtain:

auto f = File { by_name, readonly=true, path="path" };

The real difference here is about forwarding: with proxies, we benefit from the syntax sugar (the operator=) but now we have to store the values and forward them (not ideal for non-movable/copyable types – and other problems could arise).

Here you can play with the code (and here is the same file on Gist). I first started with the tag version and then I tried with proxies. For this reason there are two versions: the former works with tags ([tag, value]…) and the latter with proxies ( [tag=value]…). Some code could (and should) be refactored.

You’ll find two sections called “PACK UTILS” (two versions: tag and proxy). These contain code I wanted to play originally (e.g. playing with variadics). I also think these kind of operations can be done by using std::forward_as_tuple and then by exploiting tuple’s utilities.

Another part of the code contains macros to retrieve parameters and to generate tags.

The final section is a full example.

Here is what a class looks like:

class window
{
public:
    // classic constructor
    window( string pTitle, int pH, int pW,
    int pPosx, int pPosy, int& pHandle)
       : title(move(pTitle)), h(pH), w(pW), posx(pPosx), posy(pPosy), handle(pHandle)
    {
    }

    // constructor using proxies (e.g. _title = "title")
    template<typename... pack>
    window(use_named_t, pack&&... _pack)
       : window { REQUIRED_NAME(title), // required
                  OPTIONAL_NAME(h, 100), // optional
                  OPTIONAL_NAME(w, 400), // optional
                  OPTIONAL_NAME(posx, 0), // optional
                  OPTIONAL_NAME(posy, 0), // optional
                  REQUIRED_NAME(handle) } // required
    {
    }

    // constructor using tags (e.g. __title, "title")
    template<typename... pack>
    window(use_tags_t, pack&&... _pack)
       : window { REQUIRED_TAG(title), // required
                  OPTIONAL_TAG(h, 100), // optional
                  OPTIONAL_TAG(w, 400), // optional
                  OPTIONAL_TAG(posx, 0), // optional
                  OPTIONAL_TAG(posy, 0), // optional
                  REQUIRED_TAG(handle) } // required
    {
    }

private:
  string title;
  int h, w;
  int posx, posy;
  int& handle;
};

You see, both named and tag constructors always delegate the real constructor to perform initialization.

The following code fragment shows how the caller uses the contraption:

int i=5;
// tags version
window w1 {use_tags, __title, "Title", __h, 10, __w, 100, __handle, i};
cout << w1 << endl;

// proxies version
window w2 {use_named, _h = 10, _title = "Title", _handle = i, _w = 100};
cout << w2 << endl;

// classic version
window w3 {"Title", 10, 400, 0, 0, i};
cout << w3 << endl;

by_name here is called use_named, but the meaning is the same.

Pros:

• mandatory and optional parameters are uniform (named or tagged)
• order is not defined a priori
• tag approach has no forwarding issues

Cons:

• compile-time errors could be hard to understand (static_assert helps a bit)
• available parameters should be documented
• pollution of the namespace scope still remains
• default-values are always evaluated (some improvements for laziness are possible)
• proxy approach is not ideal for forwarding.

A note about the first trouble: Clang is a gentleman and it complains politely. For instance, suppose I forget a title for my window. Here is the output:

main.cpp:28:2: error: static_assert failed "Required parameter"
        static_assert(pos >= 0, "Required parameter");
        ^             ~~~~~~~~

main.cpp:217:14: note: in instantiation of template class 'get_at<-1, 0>' requested here
                :       window { REQUIRED_NAME(title),
                                 ^

This way you know precisely where you miss a required parameter. This could be improved.

A minimalistic approach using std::tuple

[Note: completely by Davide Di Gennaro]

We can exploit some of the power of std::tuple to write an extremely compact and portable implementation. We will stick to some simple principles:

• the parameter pack will be a special tuple, where a “tag type” is immediately followed by its value (so the type would be something like std::tuple<age_tag, int, name_tag, string, … >)
• the standard library already has utility functions to forward / concatenate objects and tuples that guarantee optimal performance and correctness in move semantics
• we will use a macro to introduce global constants that represent a tag
• the syntax for constructing a parameter pack will be (tag1=value1)+(tag2=value2)+…
• the client will take a parameter pack as a reference to template type, e.g.

template <typename pack_t>
void MyFunction([whatever], T& parameter_pack)      // or const T&, T&&, etc.

• With a function call, the client will extract a value from the pack and (say) move it into a local variable.

Ideally, here’s how the code will look like:

namespace tag
{
   CREATE_TAG(age, int);
   CREATE_TAG(name, std::string);
}

template <typename pack_t>
void MyFunction(T& parameter_pack)
{
   int myage;
   std::string myname;
   bool b1 = extract_from_pack(tag::name, myname, parameter_pack);
   bool b2 = extract_from_pack(tag::age, myage, parameter_pack);
   assert(b1 && myname == "John");
   assert(b2 && myage == 18);
}

int main()
{
   auto pack =  (tag::age=18)+(tag::name="John");
   MyFunction(pack);
}

Here is how the implementation may look like. We will omit most of the potential optimizations for sake of clarity (and they are probably unnecessary).

First, the macro:

#include <tuple>
#include <utility>

template <typename T>
struct parameter {};

#define CREATE_TAG(name, TYPE) \
\
   struct name##_t \
   { \
      std::tuple<parameter<name##_t>, TYPE> operator=(TYPE&& x) const \
      {  return std::forward_as_tuple(parameter<name##_t>(), x); } \
      \
      name##_t(int) {} \
}; \
\
const name##_t name = 0

The expansion of CREATE_TAG(age, int); creates a class and a global object. Note that this will work if positioned inside a namespace.

struct age_t
{
   std::tuple<parameter<age_t>, int> operator=(int&& x) const
   {
      return std::forward_as_tuple(parameter<age_t>(), x);
   }
   age_t(int) {}
};

const age_t age = 0;

 

Conceptually the assignment

age = 18

Translates into something similar to:

make_tuple(parameter<age_t>(), 18);

Observe that we wrote:

std::tuple<parameter<age_t>, int> operator=(int&& x) const

As written, we require an r-value on the right. First, this is an extra safety feature: to increase the readability of the code with parameter packs, you may want to assign constants, not variables (otherwise, renaming the variable would be sufficient). e.g.

int myage = 18;
f(myage); // ok, clear

g((...) + (age=18)); // ok, clear
g((...) + (age=myage)); // compiler error, and redundant from a readability point of view

Second, we can exploit move semantics:

The difference between

std::tuple<parameter<age_t>, int> operator=(int&& x) const
{
   return std::make_tuple(parameter<age_t>(), x);
}

and

std::tuple<parameter<age_t>, int> operator=(int&& x) const
{
   return std::forward_as_tuple(parameter<age_t>(), x);
}

is very subtle. The latter returns std::tuple<…, int&&>, but since the return type is tuple<…, int> then tuple’s move constructor is invoked.
Alternatively we could write

std::tuple<parameter<age_t>, int> operator=(int&& x) const
{
   return std::make_tuple(parameter<age_t>(), std::move(x));
}

Now, we add a suitable tuple-concatenation operator.

We informally agree that all tuples starting with parameter<T> have been generated by our code, so without any explicit validation, we just cat them:

template <typename TAG1, typename... P1, typename TAG2, typename... P2>
std::tuple<parameter<TAG1>, P1..., parameter<TAG2>, P2...>
operator+ (std::tuple<parameter<TAG1>, P1...>&& pack1, std::tuple<parameter<TAG2>, P2...>&& pack2)
{
    return std::tuple_cat(pack1, pack2);
}

Very simply, this function will do a simple pattern matching on two tuples: if they both look like:

tuple<parameter<tag>, type, [maybe something else]>

then they are joined together.

Finally, we publish a function to perform the extraction of an argument from the pack. Note that this function has move semantics (i.e. after a parameter is moved out of the pack).

template <typename TAG, typename T, typename... P, typename TAG1>
bool extract_from_pack(TAG tag, T& var, std::tuple<parameter<TAG1>, P...>& pack);

the effect of this function is:

if the “pack” contains parameter<TAG>, then var receives the value immediately following, and the function returns true. otherwise something bad happens (we can choose between: a compiler error, return false, throw exception, and a few more…)

To make this selection possible, actually the function will be:

template <typename ERR, typename TAG, typename T, typename... P, typename TAG1>
bool extract_from_pack(TAG tag, T& var, std::tuple<parameter<TAG1>, P...>& pack)

So we will invoke it as:

extract_from_pack< erorr_policy > (age, myage, mypack);

Due to variadic templates pattern matching, extract_from_pack knows that the pack has the form tuple<parameter<TAG1>, … > so it needs to examine recursively if TAG is equal to TAG1. We will do this dispatching the call to a class:

extract_from_pack< erorr_policy > (age, myage, mypack);

calls

extractor<0, erorr_policy >::extract (age, myage, mypack);

which in turn calls

extractor<0, erorr_policy >::extract (age, myage, std::get<0>(pack), mypack);

which has two overloads:

extract(TAG, … , TAG, …)

which succeeds, performs the assignment and returns true, or

extract(TAG, … , DIFFERENT_TAG, …)

which keeps on iterating, calling again

extractor<2, erorr_policy >::extract (age, myage, mypack);

when iteration is not possible, error_policy::err(…) is invoked.

template <size_t N, typename ERR>
struct extractor
{
   template <typename USERTAG, typename T, typename TAG, typename... P>
   static bool extract(USERTAG tag, T& var, std::tuple<parameter<TAG>, P...>&& pack)
   {
      return extract(tag, var, std::get<N>(pack), std::move(pack));
   }

   template <typename USERTAG, typename T, typename TAG, typename... P>
   static bool extract(USERTAG tag, T& var, parameter<TAG> p0, std::tuple<P...>&& pack)
   {
      return extractor<(N+2 >= sizeof...(P)) ? size_t(-1) : N+2, ERR>::extract(tag, var, std::move(pack));
   }

   template <typename USERTAG, typename T, typename... P>
   static bool extract(USERTAG tag, T& var, parameter<USERTAG>, std::tuple<P...>&& pack)
   {
      var = std::move(std::get<N+1>(pack));
      return true;
   }
};

template <typename ERR>
struct extractor<size_t(-1), ERR>
{
   template <typename TAG, typename T, typename DIFFERENT_TAG, typename... P>
   static bool extract(TAG tag, T& var, std::tuple<parameter<DIFFERENT_TAG>, P...>&& pack)
   { return ERR::err(tag); }
};

template <typename ERR, typename TAG, typename T, typename... P, typename TAG1>
bool extract_from_pack(TAG tag, T& var, std::tuple<parameter<TAG1>, P...>& pack)
{
   return extractor<0, ERR>::extract(tag, var, std::move(pack));
}

Due to the flexible nature of parameter packs, the best error policy would be a plain “return false” (any stronger error would in fact make that parameter mandatory). So:

struct soft_error
{
   template <typename T>
   static bool err(T)
   {
      return false;
   }
};

However we are free to chose any of these:

struct hard_error
{
   template <typename T>
   static bool err(T); // note that static_assert(false) here won’t work. can you guess why?
};

struct throw_exception
{
   template <typename T>
   static bool err(T)
   {
      throw T();
      return false;
   }
};

An additional improvement could be a redundancy check, that prevents code like (age=18)+(age=19).

The code for this is short, but it requires some subtle manipulation with variadic templates, so we leave it as an excercise.

Final notes

I have not discussed about runtime techniques, e.g.:

void MyFunction ( option_parser& pack )
{
   auto name = pack.require("name").as<string>();
   auto age = pack.optional("age", []{ return 10; }).as<int>();
   ...
}

Whereas the opening techniques I have presented are fairly consolidated, last ideas are just work in progress and I’m still trying to understand if they make sense. The code I’ve shown is just a proof of concept and it does not claim to be optimal nor suitable for production. I wrote these lines more than one year ago, to practice with variadics and I finally found some time to summarize my ideas in a decent (I hope) post and share with you. If this will be helpful or inspiring to anyone, I’ll be really glad.

I found a recent proposal aiming to introduce named arguments in C++ here. Cool!

Anyhow I have a question for you: where would you have wanted to use named parameters in C++?