In general, the worse case scenario when searching through a data set is when the datum being searched for doesn’t exist. In this case, the complete data storage needs to be searched before it’s possible to conclude that the datum cannot be found. If only there was a way to eliminate the need to perform unnecessary searches when we know the data won’t be found. Fortunately, there is a data structure that allows you to do just that. This data structure is knows as a “Bloom Filter”.
Continue reading “Bloom Filters”
Category: Tutorials
Functional programming using bind
Since the introduction of the STL (Standard Template Library) the use of functors has been a prevalent part of writing C++. Most of the STL algorithms require the use of a functor. For example, the std::transform requires a function object that, given an input of the current value of the current position, it will return a new value what will be used to modify the current value.
Continue reading “Functional programming using bind”
Lowest Common Ancestor (non-BST)
In the earlier article, Lowest Common Ancestor (BST), I discussed how you can use the special ordering of a Binary Search Tree to quickly and easily identify the Lowest Common Ancestor of two nodes. Of course, not all trees are BSTs and so in this article we’ll look at a way of finding the LCA in a non-BST. Continue reading “Lowest Common Ancestor (non-BST)”
Lowest Common Ancestor (BST)
The Binary Search Tree (BST) is a tree like data structure that allows for the quick lookup of data. They work by storing inserted data in a tree like structure that uses the “divide and conquer” approach to locate data. Each node in the tree has, at most, two children. The left hand side (lhs) node will always contain a value that is less than it’s parent. The right hand side (rhs) node will always contain a value that is greater-than or equal to it’s parent.
Condition Variables
You work in a bar, pouring pints for the locals. One of your regulars comes in; he’s looking pretty grumpy today. “Whiskey” he snaps. You put down a glass and pour. You finish pouring and he necks back the drink. “Again”, he snaps. Again, you pour and as soon as you finish he necks it. This repeats two or three more times before the grumpy man slams down the money for his tab and leaves. Congratulations, you have just taken part in a “Producer/Consumer” exchange.
Variadic Functions the C++11 way
The C++11 standard introduced so called Variadic Templates. These have many uses, one of which is the ability to write functions that take any number of arguments without having to mess around with C-style non-type safe “var-args” and printf like format specifiers.
Down-casting re-visited
In my previous article I discussed the difference between up-cast and down-cast and explained why down-casting is rarely a good idea (or even necessary). That said, there are a few times when down-casting is valid and so this article shows how to do so, safely, in C++.
Bloodlines and casting
When working with objects that have an inheritance model you basically have an inverted tree that represents your object hierarchy. Contrary to a normal everyday trees, an inheritance tree has its root at the top. In other words, the root of the tree represents the base class and anything below it represents a more derived class. Continue reading “Bloodlines and casting”
LRU Cache Implementation
One of the problems any developer will eventually have to resolve is one of latency; specifically, being able to retrieve and process data in a timely fashion. This issue can come in many guises but they generally manifest as needing to read data from a backing store that cannot deliver the high performance needed by the application. This can be a tricky problem to solve but the general method is to implement some form of caching. The remainder of this article will discuss one caching mechanism, called the LRU Cache.
Doubt and uncertainty!
The C and C++ standards documents can be a bit of a beast to trawl through and quite often you’ll find yourself reading the same sentence a number of times trying to fathom out what it is actually saying. It’s just like when you read the EULA for a software product; lots of big words and long sentences that don’t actually seem to make a lot of sense.
evilrix 