Digging into Data Structures and Algorithms in STL

For programmers, understanding data structures is crucial. The majority of the time, the way you store your data determines the application’s overall efficiency. Take, for example, an email client. You may create an email client that displays the 10 most recent emails and it will have the best user interface available; showing the 10 most recent emails will operate on nearly every device. After 2 years of using your email application, the user will have received hundreds of thousands of emails. When the user needs to find an email, your data structure expertise will come in handy. The way you store the hundreds of thousands of emails and the methods (algorithms) you employ to sort and search them will set your application apart from the others.

While working on different projects, programmers face many problems and try to find the best solutions to those problems – by saying best, I mean the most efficient ones. Using...

Technical requirements

The g++ compiler with the -std=c++20 option was used to compile the examples throughout this chapter. You can find the source files that have been used in this chapter in the GitHub repository for this book at https://github.com/PacktPublishing/Expert-C-2nd-edition.

Sequential data structures

Even if you are a programmer who has never heard of a single data structure and you do not even know what they are, you may be surprised to learn that you have probably used one in your projects. Let’s take, for example, an array, which every experienced programmer must have used at least once. We can use an array to store and order a collection of data.

Programmers frequently use data structures other than arrays in their projects. Knowing about and using the right data structures might make a big difference in the way your software runs. You must have a deeper understanding of data structures before you can select the most appropriate one.

The obvious question is whether we need to learn about the variety of data structures, such as vectors, linked lists, hash tables, graphs, and trees. Let’s imagine a hypothetical situation in which the need for a better data structure emerges.

In the introductory part of this chapter, we briefly...

Iterating containers

A container that is not iterable is analogous to a car that cannot be driven. A container, after all, is a collection of items. The for loop is one of the most frequent techniques we can use to iterate over container elements:

std::vector<int> vec{1, 2, 3, 4, 5};for (int ix = 0; ix < vec.size(); ++ix) {
std::cout << vec[ix] << ", ";
}

For element access, containers offer a distinct set of actions. operator[], for example, is provided by the vector but not by the list. std::list has the front() and back() methods, which return the first and last elements, respectively. std::vector, as already discussed, additionally provides at() and operator[].

This means that we cannot use the preceding loop to iterate list elements. However, we can loop over a list (and vector) with a range-based for loop, as follows:

std::list<double> lst{1.1, 2.2, 3.3, 4.2};for (auto& elem : lst) {
std::cout << elem << "...

Concepts and iterators

C++20 introduced concepts as one of its major features. Along with concepts, C++20 has new iterators based on concepts. Even though the iterators we’ve explained up to this point are now considered legacy features, they have already been used in many lines of code. That is why we introduced them first before continuing with the new iterator concepts. Now, let’s find out what concepts are and how to use them.

Understanding concepts

Abstraction is essential in computer programming. In the previous chapters, we discussed that OOP is a way to represent data and operations as abstract entities. We also covered template metaprogramming by diving into templates and making our classes even more flexible by reusing them for various aggregate types. Templates allow not just abstraction from specific types but also loose coupling between entity and aggregate types. Consider the std::vector class. It offers a general interface for storing and manipulating...

Using iterators in C++20

Iterators were the first to fully use concepts after they were introduced. Iterators and their categories are now considered legacy because, starting from C++20, we use iterator concepts such as readable (which specifies that the type is readable by applying the * operator) and writable (which specifies that a value can be written to an object referenced by the iterator). Let’s look at how incrementable is defined in the <iterator> header, as promised:

template <typename T>concept incrementable = std::regular<T> && std::weakly_incrementable<T> && requires (T t) { {t++} -> std::same_as<T>; };

Therefore, the incrementable concept requires the type to be std::regular. This means it should be constructible by default and have a copy constructor and operator==(). Besides that, the incrementable concept requires the type to be weakly_incrementable, which means the type supports pre- and post-increment...

Node-based data structures

Node-based data structures do not necessarily take contiguous blocks of memory. They mainly allocate nodes in memory that are connected. In this case, logically, there is no need to allocate a block of memory when nodes can occupy node-size spaces and be connected in some way. This means that nodes might be spread randomly in memory.

The linked list is the most often used and most basic node-based data structure. A visual representation of a doubly linked list is shown in the following diagram:

Figure 6.9: Illustration of a doubly linked list

Apart from the structural differences, the way that operations run on node-based data structures also differs from that of sequential data structures. Some of the operations are faster, while some are slower. For example, if we compare an array and a list, the time complexity of reading an element will be O(1) for an array and O(n) for a list. Here, the insertion will be O(n) for an array...

Graphs and trees

Graphs and trees are considered non-linear data structures, which come in handy in solving various kinds of problems. Though they are both non-linear data structures, they have differences, which help us distinguish them from each other. For example, the tree should have a root node, while the graph doesn’t have one; the tree forms a tree-like structure when dealing with data while the graph organizes the data into a network-like structure; there can be loops in a graph, while a tree doesn’t allow this; and so on.

Trees

Thinking about a combination of a binary search algorithm and sorting algorithms can lead to the idea of having a container that maintains objects so that they’re sorted by default. std::set, which is built on a balanced tree, is one such container. Before discussing balanced trees, let’s look at the binary search tree, which is a great option for quick lookups.

The binary search tree’s concept is that the...

Hash tables

The hash table is the most efficient data structure currently available. It is based on the concept of vector indexing, which is a rather simple concept. Consider the following example of a large vector with list pointers:

std::vector<std::list<T> > hash_table;

Accessing the elements of a vector takes constant time – that is the primary superpower of a vector. The hash table enables us to use any type as the container’s key. The basic idea of the hash table is to use a well-curated hash function that will generate a unique index for the input key. For example, when we use a string as a hash table key, the hash table uses a hash function to generate the hash as the index value for the underlying vector (the code for this can be found at https://github.com/PacktPublishing/Expert-C-2nd-edition/tree/main/Chapter%2006/14_insert_hashtable.cpp).

Here is how we can illustrate a hash table:

Figure 6.18: Illustration of...

Algorithms

Algorithms, as mentioned previously, are functions that take an input, process it, and provide an output. In most cases, in STL, an algorithm refers to a function that processes a set of data. Containers, such as std::vector, std::list, and others, are used to store data collections.

One of the common tasks in a programmer’s routine is to select an efficient algorithm. For example, using the binary search technique to search a sorted vector will be significantly faster than using sequential searching. An asymptotic analysis, which considers the speed of the algorithm concerning the size of the input data, is used to compare the efficiency of algorithms. This means that we should not compare two algorithms by applying them to a container with 10 or 100 elements.

The true difference between methods becomes apparent when they’re applied to a large enough container – one with one million or even one billion elements. Verifying an algorithm’s...

Summary

In this chapter, we went over the basics of data structures and the differences between them. We learned how to use them based on problem analysis. For example, because of the difficulty of linked-list element access operations, using a linked list in applications requiring random lookups is deemed time-consuming. Due to its constant-time element access, a dynamically increasing vector is more suited to such cases. In contrast to, for example, a list, using a vector in problems that require quick insertions at the front of the container is more costly.

This chapter also covered algorithms and how to measure their effectiveness. We compared several problems to develop better methods for solving them more quickly.

In the next chapter, we are going to continue the topic of data structures by diving deeper into it and discussing advanced data structures, their properties, and their implementation details.

Further reading

For more information, refer to the following resources:

• Programming Pearls, by Jon Bentley, available at https://www.amazon.com/Programming-Pearls-2nd-Jon-Bentley/dp/0201657880/
• Data Abstraction and Problem Solving Using C++: Walls and Mirrors, by Frank Carrano and Timothy Henry, available at https://www.amazon.com/Data-Abstraction-Problem-Solving-Mirrors/dp/0134463978/
• Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein, available at https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844/
• C++ Data Structures and Algorithms by Wisnu Anggoro, available at https://www.packtpub.com/product/c-data-structures-and-algorithms/9781788835213

Questions

Answer the following questions to test your knowledge of this chapter:

1. Describe how an element is added to a vector that is expanding dynamically.
2. What distinguishes inserting an element at the front of a linked list from inserting it at the front of a vector?
3. Implement a hybrid data structure that stores its elements as a vector and a list, respectively. Pick the underlying data structure that implements the operation in each case as quickly as possible.
4. How would a binary search tree look if 100 elements were added in increasing order?