Every self-respecting C/C++ programmer knows what the ternary operator is, and most everyone used it at least once in their programs. But do you know all the secrets of the ternary operator? What potential dangers are associated with its use and what features, seemingly not related to its direct purpose, it has? This article gives you the opportunity to test your knowledge and maybe learn something new. Let’s start with a small test.
In accordance with the C and C++ standards, if the program leads to an integer overflow or any other “undefined behavior” (UB), the result of the program performance can be anything: it can post obscenities to Twitter or format your disk… Unfortunately, “Easter eggs” that would make the program do something out of the ordinary in case of UB, have not been noticed since the GCC 1.17 that invoked NetHack, when the code contained unknown #pragma.
In the previous articles I described the basis, on which lock-free data structures and basic algorithms of the lifetime management of elements of lock-free data structures are built. Actually, it was a prelude to the description of lock-free containers. But then I faced a problem of how to build the story. Describing the known algorithms would be quite boring, as there would be a lot of [pseudo-]code, plenty of details that are important but quite specific.
Today I will continue to introduce techniques that help to write lock-free containers. At the same time, I will advertise (hopefully not too obtrusive), my libcds library. We will talk about one more technique of safe memory reclamation for lock-free containers – RCU. This technique differs significantly from the previously discussed algorithms, such as Hazard Pointer. Read – Copy Update (RCU) is a synchronization technique designed for «almost read-only», meaning rarely changed, data structures.
In the previous article we’ve reviewed Randomized Binary Search Trees. Today we are going to review the implementation of AVL Trees. They must be the first type of Balanced Binary Search Trees. They were invented by two Soviet inventors, G. M. Adelson-Velskii and E. M. Landis in 1962. There are plenty of AVL trees implementations, but, to my mind, none of them is good enough when you try to make sense of it all from scratch.
I have always been surprised by the contrast between the grace of the main concept of binary search trees and implementation complexity of balanced Binary Search Trees (Red-Black Trees, AVL Trees and Treaps). I have recently looked through the “Algorithms” by Robert Sedgewick [1] and found a description of randomized search trees (I’ve also found the original [2]). It is just one third of a page long (nodes insertion, and one more page for deletion).
Unfortunately, standard C++ library doesn’t provide tools for working with HTTP. Therefore, when we want to run a REST service, parse a webpage or write a simple bot or web crawler, we always wonder which library is better to use. Sometimes a project already uses some framework (or even several). But how do we create an HTTP request using available facilities? Not to get confused each time performing such tasks, I decided to make a cheat sheet with examples of HTTP requests in C++ using different libraries.
In the previous articles of the series we’ve reviewed the adaptive process of the square game field for concepts of boost graphs. Now we’ll consider the process of finding the path in the square field. Implementation of boost search allows adapting the algorithm quite accurately. In this article we’ll provide just one example of such parameterization – an ability to create various lengths of graph edges. Let’s begin with describing the parameter.
I’ll briefly remind you of the task. There’s a two-dimensional game field consisting of squares. Some of them are vacant and others are occupied. We should find a path through vacant squares from one field position to another one. We implemented the search algorithm in Boost. But it requires our field to fit the graph definition. Or rather the class should meet the requirements of two concepts: boost::VertexListGraph and boost::IncidenceGraph. We don’t want to change the interface of game field, as it’s not a graph for the remaining project and will never be one.
I had to rebuild a pathfinding algorithm for our game recently. The previous one (Boost Concepts) was bad as any sidestep was dangerous. So I wanted to take a ready algorithm from a good source. That’s exactly when I remembered about boost as there’s functionality for working with graphs. Unfortunately “find a function, call it and everything will work” approach wasn’t meant to be realized. The library is focused on the maximum use flexibility which has badly affected its simplicity.
