How to Iteratively Traverse a Binary Tree

Binary tree traversals are generally done in a recursive manner because this type of problem tends to be simplified by such methods. Nevertheless, the key advantage gained by using an iterative approach is the fact that the traversal will not run out of stack space. Moreover, there is always something to learn when solving a problem in an alternative way.

Below are the iterative implementations of the different types of traversals that can be done with a binary tree alongside an explanation of how they work:

Pre-Order Traversal

void print_pre_order(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }

    std::stack<TreeNode*> stack;
    stack.push(root);

    while (!empty(stack))
    {
        auto* node = stack.top();
        stack.pop();

        std::cout << node->val << ' ';

        if (node->right != nullptr)
        {
            stack.push(node->right);
        }
        if (node->left != nullptr)
        {
            stack.push(node->left);
        }
    }
}

Pre-Order traversal consists of traversing the left subtree before advancing to the right subtree. This behavior is achieved through the use of a Last In First Out (LIFO) data structure like a stack. The insertion of the right nodes occurs before the left nodes in order to make sure that the left nodes will be the first ones to be accessed.

Post-Order Traversal

void print_post_order(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }

    std::stack<TreeNode*> stack, out_stack;
    stack.push(root);

    while (!empty(stack))
    {
        auto* node = stack.top();
        stack.pop();

        out_stack.push(node);

        if (node->left != nullptr)
        {
            stack.push(node->left);
        }
        if (node->right != nullptr)
        {
            stack.push(node->right);
        }
    }

    while (!empty(out_stack))
    {
        auto* node = out_stack.top();
        out_stack.pop();

        std::cout << node->val << ' ';
    }
}

The Post-Order iterative tree traversal algorithm is slightly more complex than the Pre-Order one because the solution uses two stacks. The first stack gets the reverse Post-Order traversal in a similar manner to the algorithm used for the Pre-Order traversal with the only difference that the left node is inserted before the right one. The purpose of the second stack is to get the reverse of the first stack and in turn get the proper Post-Order traversal.

In-Order Traversal

void print_in_order(TreeNode* root)
{
    std::stack<TreeNode*> stack;
    auto* curr = root;

    while (!empty(stack) || curr != nullptr)
    {
        if (curr != nullptr)
        {
            stack.push(curr);
            curr = curr->left;
        }
        else
        {
            curr = stack.top();
            stack.pop();

            std::cout << curr->val << ' ';

            curr = curr->right;
        }
    }
}

In-Order traversal involves a current pointer pivot that will traverse the leftmost part of the tree and insert itself to a stack until it reaches a null value. If the current pointer is null and the stack is not empty then the pivot pointer moves towards the rightward node from the node at the top of the stack, otherwise, the traversal stops as the whole tree has been accessed.

Level-Order Traversal

void print_level_order(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }

    std::queue<TreeNode*> queue;
    queue.push(root);

    while (!empty(queue))
    {
        const auto LEVEL_SIZE = size(queue);

        for (std::size_t i = 0; i < LEVEL_SIZE; ++i)
        {
            auto* node = queue.front();
            queue.pop();

            std::cout << node->val << ' ';

            if (node->left != nullptr)
            {
                queue.push(node->left);
            }
            if (node->right != nullptr)
            {
                queue.push(node->right);
            }
        }
    }
}

The Level-Order traversal algorithm is different from all the previous methods mentioned in the fact that it uses a First In First Out (FIFO) data structure in the form of a queue. The way it works consists of accessing every node in a single level and then insert the left and right child nodes to use them in the next cycle of iteration for each upcoming level. As a side note, it is not necessary to include the for loop to iterate through every level of the tree as the queue itself will handle this behavior; nevertheless, this is added to make a distinction for every level of the tree that is being accessed.

Conclusion

Undoubtedly, the iterative approach of traversing a binary tree traversal is a more verbose and complex solution when compared to its recursive counterpart. Despite that, implementing another way of traversing a tree adds a level of comprehension for key data structures such as stacks and queues, as well as, include the benefit of not having to worry about running out of stack space.

Source Code

How to Format a String in C++

String formatting is a common and useful operation that is regularly used in most programming languages. Unfortunately, the formatting solution offered in the C++ Standard Library lacks simplicity and intuitiveness. For that reason, implementing a C-style “printf” type function for string formatting can be a worthy investment as it offers an advantage in terms of convenience over C++ I/O manipulators.

The implementation below makes use of several C++11 features that improve readability and safety concerns that would exist in older legacy code. The most notable one being the variadic template parameter pack that acts as a wrapper around the variadic function used in C-style “printf” methods.

template<typename... Args>
std::string format_string(const std::string& format, Args... args)
{
    const auto size = std::snprintf(nullptr, 0, format.c_str(), args...) + 1;
    const auto buffer = std::make_unique<char[]>(size);

    std::snprintf(buffer.get(), size, format.c_str(), args...);

    return std::string(buffer.get(), buffer.get() + size - 1);
}

Here’s a quick rundown of what is happening in this function:

  1. The size of the char array is determined by getting the return value from std::snprintf. (Note: plus one is added to this value to make room for the null terminator at the end of the array)

  2. A new char array is allocated through the use of a unique pointer to not worry about manually deleting this memory again.

  3. std::snprintf is used to write the formatted string into the char array.

  4. A new string is created from the char array buffer and then returned.

While this function seems to get the job done, there is still one more point missing to fully support C++ specific types. More specifically, this method doesn’t work whenever a std::string object is passed as part of its argument list. To fix this issue there needs to be an additional check to convert a std::string object into a “const char*” so that it gets forwarded as a parameter for std::snprintf. The complete implementation considering this aspect is shown below (Note: this solution uses C++17 features):

template<typename T>
auto convert(T&& t)
{
    if constexpr (std::is_same<std::remove_cv_t<std::remove_reference_t<T>>, std::string>::value)
    {
        return std::forward<T>(t).c_str();
    }
    else
    {
        return std::forward<T>(t);
    }
}

template<typename... Args>
std::string format_string_internal(const std::string& format, Args&& ... args)
{
    const auto size = std::snprintf(nullptr, 0, format.c_str(), std::forward<Args>(args)...) + 1;
    const auto buffer = std::make_unique<char[]>(size);

    std::snprintf(buffer.get(), size, format.c_str(), std::forward<Args>(args)...);

    return std::string(buffer.get(), buffer.get() + size - 1);
}

template<typename... Args>
std::string format_string(const std::string& format, Args&& ... args)
{
    return format_string_internal(format, convert(std::forward<Args>(args))...);
}

Now this solution may seem like a lot more complex than the previous one, but in reality, there is not a lot that has changed. The most noticeable difference is the inclusion of the “convert” function that checks at compile-time if the parameter passed is a string, and if it is then it returns the C-string given by the “c_str()” method, otherwise, it returns the type itself. Moreover, an additional format function is added to make sure the user does not have to explicitly call the “convert” method whenever formatting a string. Lastly, the use of std::forward is included to ensure perfect forwarding takes place.

Conclusion

C-style “printf” functions provide a simpler and more intuitive interface compared to the C++ standard solution of using I/O manipulators. Hence, the previous implementation for a string formatting function offers a great alternative from what can currently be done using C++ streams. As a side note, libraries like fmt and boost::format also provide great solutions to string formatting needs.

Source Code

How to Create a Random String in C++

Generating a random string in C++ is a simple task that can be easily achieved by the use of rand(); however, this method is not recommended because rand() lacks a distribution engine and the quality of its implementation leaves more to be desired. To combat this issue, the C++ Standard Library provides a set of functions from the Random header that allows users to generate random numbers from well-defined engines and distributions. The implementation of the function that generates a random string will make use of three key features present in the facilities of the Random header.

The elements used being:

The implementation for the random string generator combining all these features together is shown below:

std::string random_string(std::size_t length)
{
    const std::string characters = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

    std::random_device random_device;
    std::mt19937 generator(random_device());
    std::uniform_int_distribution<> distribution(0, characters.size() - 1);

    std::string random_string;

    for (std::size_t i = 0; i < length; ++i)
    {
        random_string += characters[distribution(generator)];
    }

    return random_string;
}

As you can see, this function hard codes all the possible characters that will be used to form the random string. Then, it initializes the three needed objects from the Random header by creating a Mersenne Twister engine and a distribution that covers all indexes from the possible characters string. Ultimately, it iterates through the arbitrary length given as a parameter to populate the string with a random character in every iteration.

Conclusion

Avoiding the use of rand() is a piece of advice that does not only apply to create random strings. Instead, it is recommended to use the facilities provided in the Random header that were included in the C++11 Standard Library.

Source Code

How to Split a String in C++

Splitting a string seems like a basic function that any language should have out of the box. Yet, C++ doesn’t provide an in-built method in the standard library that takes care of this task. The reason for the absence of this feature is likely due to the fact that the algorithm has to define the type of container it returns, or that there is a large number of configurations with different parameters that would complicate its interface. To deal with this situation we will implement three different split functions with separate needs in mind.

Split Method #1 (Only Whitespace)
The first implementation for a split function consists of a method that accepts the string to split as its parameter and returns a vector of strings that are delimited by whitespace. This solution makes use of stream iterators to populate the vector with all the tokens in the string.

std::vector<std::string> split(const std::string& string)
{
    std::istringstream i_stream(string);

    return std::vector<std::string>{std::istream_iterator<std::string>{i_stream},
        std::istream_iterator<std::string>()};
}

Split Method #2 (Char Delimeter)
The second implementation accepts a custom delimeter in the form of a character and returns a vector of strings with all tokens. It takes advantage of the getline function that extracts all the characters into a token until the delimeter is found.

std::vector<std::string> split(const std::string& string, char delimeter)
{
    std::stringstream stream(string);

    std::string token;
    std::vector<std::string> tokens;

    while (std::getline(stream, token, delimeter))
    {
        tokens.push_back(token);
    }

    return tokens;
}

Split Method #3 (String Delimeter)
The last method provides an even more general solution that accepts a string delimeter to separate all the tokens. The way it works consists of finding the starting index of each delimeter using the string find function and then extract the token by using the substring method.

std::vector<std::string> split(const std::string& string, const std::string& delimeter)
{
    std::size_t start_index = 0, end_index = 0;

    std::vector<std::string> tokens;

    while ((end_index = string.find(delimeter, start_index)) != std::string::npos)
    {
        auto token = string.substr(start_index, end_index - start_index);
        start_index = end_index + delimeter.size();

        tokens.push_back(token);
    }

    tokens.push_back(string.substr(start_index));

    return tokens;
}

Conclusion

Clearly, the lack of a split function in the standard library can be a cumbersome realization. Luckily, implementing the split algorithm is not a complicated task as it was previously shown in the code snippets. On another note, external libraries such as boost include built-in alternatives for split functionality that remove the need to worry about implementation details.

Source Code

The Spaceship Operator and Its Importance for Class Types in Non-Type Template Parameters

The spaceship operator coming in C++20 was first proposed as a means to simplify the overloading of comparison operators for a specific class. Undoubtedly, it fulfilled its goal as it drastically shortened the code needed to describe each comparison operator(==, !=, <, <=, >, >=).

//Previous C++ code
struct Foo
{
  int x;
  
  friend bool operator==(Foo const& foo1, Foo const& foo2) 
  { return foo1.x == return foo2.x; }
  friend bool operator!=(Foo const& foo1, Foo const& foo2) 
  { return !(foo1 == foo2); }
  friend bool operator< (Foo const& foo1, Foo const& foo2) 
  { return foo1.x < foo2.x; }
  friend bool operator<=(Foo const& foo1, Foo const& foo2) 
  { return !(foo2 < foo1); }
  friend bool operator> (Foo const& foo1, Foo const& foo2)
  { return foo2 < foo1; }
  friend bool operator>=(Foo const& foo1, Foo const& foo2) 
  { return !(foo1 < foo2); }
};

//C++20 Code
struct Foo
{
  int x;
  
  auto operator<=>(Foo const&) = default;
};

This new language feature takes advantage of automatic generation; effectively creating the needed comparison operators without any issues. An important thing to note is that the spaceship operator returns five possible types: std::strong_ordering, std::weak_ordering, std::partial_ordering, std::strong_equality, and std::weak_equality. Each of which follow the following models:

Model Return Type Operators
Total orderstd::strong_ordering==, !=, <, <=, >, >=
Weak orderstd::weak_ordering==, !=, <, <=, >, >=
Partial orderstd::partial_ordering==, !=, <, <=, >, >=
Equality comparabestd::strong_equality==, !=
Equivalence comparablestd::weak_equality==, !=

Beyond the clear gains in conciseness, the three-way comparison operator provides a new solution to the existing irregularities for class types in non-type template type parameters; an idea that wasn’t expected by the creator of the spaceship operator proposal(Herb Sutter). The problem with non-type template type parameters is that they currently only accept a small subset of types consisting of integral types, enum types, pointer types, pointer-to-member types, reference types, and std::nullptr_t; which in turn causes an inconsistency in the language by separating the use of certain types for no concrete reason. Removing this inconsistency became apparently hard, until the proposal for the spaceship operator came into fruition.

Integrating the spaceship operator to the language would guarantee equality for different instantiations of a templated entity; effectively letting custom types to be accepted as template type parameters by ensuring the following:

  • The class type has a comparison operator.

  • The class type has the same comparison operator available in all translation units.

  • The class implements member-wise equality.

Conclusion

The spaceship operator not only reduces the code needed to overload comparison operators as it also provides a clear solution to the inconsistencies related to class types in non-type template parameters. For further reading into this topic read the spaceship operator proposal as well as the class types in non-type template parameters proposal.

Concepts: The Next Major Change Coming to C++

The upcoming C++ standard is set to promise many different features and changes that will simplify and expand the way we write and think of code. Upon the wide variety of additions to the language, the inclusion of Concepts tops the list as the most significant one, as they are essential to simplify the use of generic programming. The currently ongoing CppCon has sparked my interest on the topic thanks to the talk given by Bjarne Stroustrup on the future of generic programming. Which covered the importance of concepts in the future of the language as described by the Concepts TS.

What is a Concept?

A Concept is a set of requirements that yield a boolean value at compile-time. They describe the characteristics needed for a certain group of objects to be used inside a template e.g.
Number: - Must provide arithmetic operators(+, +=, -, -=, *, *=, /, /=)
- Must be constructible from 0
- Must be copyable
- Must be movable

Why do we need Concepts?

- Simplify the way we write generic code by removing the verbosity and repetitiveness that templates bring e.g.

//Old C++ template version
template<typename T>
void sort(T& container)
{
    //Sort algorithm
}

//New C++ concept version
void sort(Sortable& container) //Sortable is a concept
{
    //Sort algorithm
}

- Provide more precise and helpful error messages which in the past have been known to daunting and irrelevant e.g.

int a = 42;

//Old error message 
sort(a) // -> error: 'a' doesn't have a [] operator

//New error message with concepts
sort(a) // -> error: 'a' is not Sortable (int doesn't provide [] operator)

- Allow the use of overloads for functions using concepts e. g.

template<RandomAccessIterator Iter>  //RandomAccessIterator is a concept
void distance(Iter first, Iter last)
{
  //Distance Implemnetation for random access iterators
}

template<Iterator Iter> //Iterator is a concept
void distance(Iter first, Iter last)
{
  //Distance implementation for the rest of iterators
}

- Remove the ugliness and complexity coming from the use of enable_if by replacing it with the use of the keyword requires e.g.

//Old code using enable_if
template<typename T>
class Foo
{
  public:
  template<typename U, std::enable_if<std::is_same<T, U>::value && std::is_copy_constructible<U>::value>>
  explicit Foo(const T& object) :
      object(object)
  {}

  private:
  T object;
};

//New code using concepts
template<typename T>
class Foo
{
  public:
  explicit Foo(const T& object)
  requires std::is_copy_constructible<T>::value :
  object(object)
  {}

  private:
  T object;
};


How do we use Concepts?

The first step is to either define a new concept or use an already existing one. Here is an example using the previously mentioned concept of a number:

template<typename T>
concept Number = requires(T a, T b)
{
  { a + b } -> T;
  { a += b } -> T&;
  { a - b } -> T;
  { a -= b } -> T&;
  { a * b } -> T;
  { a *= b } -> T&;
  { a / b } -> T;
  { a /= b } -> T&;
  
  { T{0} };
  
  requires std::is_copy_constructible<T>;
  requires std::is_move_constructible<T>;
}

Then we simply use the already defined concept in a function:

template<Number N>
N pow(N number)
{
  //power exponent implementation
}

Conclusion

Concepts fill in a void that was missing in the language; they effectively improve and simplify the use of generic code. It’s important to understand and appreciate their benefits to start adhering them into our code base as soon as C++20 arrives.

Range-V3: The Blueprint for Standardized Ranges

Iterators have been one of the basic and most important components in the Standard Template Library(STL) ever since its creation. Their usage has become so fundamental that they’ve been provided overloads for almost all generic algorithms in the standard library. Iterators seem to do the job they’re supposed to; but are they the most convenient solution? Most of the time we want to modify the elements of an entire container without having to bother about anything else. The standard library has imposed the use of begin() and end() iterators to manage the totality of a container, but this in turn has damaged the readability and simplicity of our code in multiple scenarios. The solution to this problem has been presented through the use of ranges in the Ranges TS, expected to be part of the new standard in C++20.

Since the integration of ranges to the standard is still a couple years away, we have to use library alternatives such as Range-V3 to unveil the power of ranges. Luckily for us, Range-V3 is the basis for the new proposal; meaning that most of its interface will be very similar to what we’ll see in C++20.

What is a Range?

A range is a sequence of objects with a beginning and an end. The motivation behind them is mainly convenience and composability. They’re convenient because they allow algorithms to take a single range object instead of a pair of iterators, making code more readable. In terms of composability, they enable the use of algorithm chaining adding more expressiveness in less lines of code.

Convenience

std::vector<int> unorderedNumbers{ 3, 1, 8, 2, 0, 5, 6, 4 };

//Iterator version
std::sort(unorderedNumbers.begin(), unorderedNumbers.end()); 

//Range version
ranges::sort(unorderedNumbers); 

Composability

std::vector<int> numbers{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

//reverse + remove even numbers

//Iterator version
std::reverse(numbers.begin(), numbers.end());
numbers.erase(std::remove_if(numbers.begin(), numbers.end(), 
[](auto number) { return number % 2 == 0; }), numbers.end());

//Range version
auto reversedOddNumbers = numbers | ranges::view::reverse | ranges::view::remove_if(
[](auto number) { return number % 2 == 0; });

Conclusion

Ranges are the next big leap for the standard library and we need to expand our perspective to welcome them into our codebase. The convenience and composability inherent in ranges makes them a worthwhile addition to the language.

DynaMix: An Alternative for Polymorphism

Polymorphism in C++ has usually been implemented through the use of an inheritance hierarchy and virtual function calls. This method while effective has one key drawback originating from the problem of multiple inheritance: a derived class having two or more parents can be the source of many ambiguities. The 'solution' to this problem was addressed by means of virtual inheritance: a technique used to prevent multiple instances of one class in an inheritance hierarchy. Although virtual inheritance fixes the diamond problem, it generates additional performance overhead and higher levels of complexity to a code base. An optimal alternative to the use of virtual inheritance is the concept of Mix-Ins, founded on the idea of granularity and composition. 

DynaMix is a useful library that elaborates on the concept of Mix-Ins, letting the user compose and modify polymorphic objects at runtime. It provides users with an effective alternative to the commonly used approach of inheritance, while still not adding many of the nuances that come from the solution using virtual inheritance. The library encompasses the notion of composition by the use of a dynamix::object that can be mutated with any number of Mix-Ins. Its benefits show when dealing with larger projects that need the use of complex objects composed of multiple parts; an example of such project would be a game composed of entities that have different behaviors or characteristics that define them.

Here is a basic example of the library in action:

#include <dynamix/dynamix.hpp>
#include <iostream>

struct Label
{
    void display()
    {
        std::cout << "Label\n";
    }
};

struct Sprite
{
    void display()
    {
        std::cout << "Sprite\n";
    }
};

DYNAMIX_DECLARE_MIXIN(Label);
DYNAMIX_DECLARE_MIXIN(Sprite);

DYNAMIX_MESSAGE_0(void, display);

DYNAMIX_DEFINE_MIXIN(Label, display_msg);
DYNAMIX_DEFINE_MIXIN(Sprite, display_msg);

DYNAMIX_DEFINE_MESSAGE(display);

int main()
{
    dynamix::object object;

    dynamix::mutate(object).add<Label>();

    display(object);

    dynamix::mutate(object).remove<Label>().add<Sprite>();

    display(object);
}

Output:
Label
Sprite

DynaMix offers a different view to what polymorphism can look like. Mix-Ins are more flexible and effective in handling complex objects that depend on multiple traits, composition through the use of Mix-Ins is the prime alternative to what inheritance can offer.