Inside STL: The deque, implementation -- Raymond Chen

By Blog Staff | Sep 20, 2023 08:35 AM | Tags: None

Now that we understand the design behind the common STL dequeue implementations, we can peek into the implementation details.

Inside STL: The deque, implementation

By Raymond Chen

From the article:

All three of the major implementations of the standard library maintain an array of pointers to blocks, which they confusingly call a “map” even though it is unrelated to std::map. (Even more confusingly, gcc internally uses the term “node” instead of “block”.) Initially, all the pointers in the map are nullptr, and the blocks are allocated only on demand.

We will say that a block is spare if it contains only spare elements.

Inside STL: unordered_map, unordered_set, unordered_multimap, & unordered_multiset -- Raymond Chen

By Blog Staff | Sep 18, 2023 07:29 AM | Tags: None

The C++ standard library provides hash-based associative containers unordered_map, unordered_set, unordered_multimap, and unordered_multiset.

All of these collections are hash tables with different payloads. The unordered_map and the unordered_multimap use a std::pair<Key, Value> as the payload, whereas the the unordered_set and the unordered_multiset use a Key as the payload.

Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset

By Raymond Chen

From the article:

Conceptually, the hash table consists of a bunch of buckets, and each bucket contains a linked list of the nodes that fall into that bucket. (This design is known as open hashing or separate chaining.) However, that’s not how the information is structured internally, because iterating through a traditionally-structured hash table requires more state than a single pointer: When you reach the end of each hash chain, you need some other information to tell you which chain to enumerate next.

C++ standard library implementations instead structure the hash table like this:

struct hashtable
{
    using hint = std::list<payload>::iterator;

    std::list<payload> list;
    std::vector<hint> buckets;
};

The list is a linked list of payloads, sorted by bucket. The buckets is a vector of iterators (pointers) into the list that tells you where each bucket begins. Each bucket implicitly ends when the next bucket begins, or (for the last bucket) when the end of the list is reached.

Inside STL: The deque, design -- Raymond Chen

By Blog Staff | Sep 14, 2023 04:17 PM | Tags: None

The C++ standard library deque is a double-ended queue that supports adding and removing items efficiently at either the front or the back.

Inside STL: The deque, design

By Raymond Chen

From the article:

All three of the major implementations of the C++ standard library use the same basic structure for a deque, but they vary in both policy and implementation details.

First, let’s design a simple version of a deque that stores its elements in an array.

template<typename T>
struct simple_deque
{
    T* elements;
    T* first;
    T* last;
    size_t capacity;
};

For example, a deque of three integers might look like this:

capacity = 8

size = last − first = 3

 

The elements points to an array whose length is given by the capacity member’s value of 8. In that array, the first three elements are not in use, but which could be used in the future. We’ll call them spares. Next come three elements holding the values 1, 2, and 3, followed by two more spares. The first element in use (1) is pointed to by first, and one past the last element in use is pointed to by last.

C++ Exceptions and Memory Allocation Failure -- Wu Yongwei

By Blog Staff | Sep 12, 2023 03:54 PM | Tags: None

Memory allocation failures can happen. Wu Yongwei investigates when they happen and suggests a strategy to deal with them.

C++ Exceptions and Memory Allocation Failure

By Wu Yongwei

From the article:

C++ exceptions are habitually disabled in many software projects. A related issue is that these projects also encourage the use of new (nothrow) instead of the more common new, as the latter may throw an exception. This choice is kind of self-deceptive, as people don’t usually disable completely all mechanisms that potentially throw exceptions, such as standard library containers and string. In fact, every time we initialize or modify a string, vector, or map, we may be allocating memory on the heap. If we think that new will end in an exception (and therefore choose to use new (nothrow)), exceptions may also occur when using these mechanisms. In a program that has disabled exceptions, the result will inevitably be a program crash.

However, it seems that the crashes I described are unlikely to occur… When was the last time you saw a memory allocation failure? Before I tested to check this issue, the last time I saw a memory allocation failure was when there was a memory corruption in the program: there was still plenty of memory in the system, but the memory manager of the program could no longer work reliably. In this case, there was already undefined behaviour, and checking for memory allocation failure ceased to make sense. A crash of the program was inevitable, and and it was a good thing if the crash occurred earlier, whether due to an uncaught exception, a null pointer dereference, or something else.

Now the question is: If there is no undefined behaviour in the program, will memory allocation ever fail? This seems worth exploring.

Five Advanced Initialization Techniques in C++ -- Bartlomiej Filipek

By Blog Staff | Sep 8, 2023 12:28 PM | Tags: None

From dynamic container operations to compile-time constants, C++ offers a variety of techniques. In this article, we’ll delve into advanced initialization methods likereserve() and emplace_backfor containers to tuples with piecewise_construct and forward_as_tuple. Thanks to those techniques, we can reduce the number of temporary objects and create variables more efficiently.

Five Advanced Initialization Techniques in C++: From reserve() to piecewise_construct and More

By Bartlomiej Filipek

From the article:

As a background, we can use the following class that will be handy to illustrate when its special member functions are called. That way, we’ll be able to see extra temporary objects.

Inside STL: The lists -- Raymond Chen

By Blog Staff | Sep 6, 2023 12:23 PM | Tags: None

The C++ standard library type list represents a doubly-linked list, and forward_list is a singly-linked list. Fortunately, the implementations of both of these lists are pretty much what you expect.

Inside STL: The lists

By Raymond Chen

From the article:

Let’s start with the simpler forward_list.

template<typename T>
struct forward_list
{
    forward_list_node<T>* head;
};

template<typename T>
struct forward_list_node
{
    forward_list_node<T>* next;
    T value;
};

The forward_list itself is a pointer to the first element of the list, or nullptr if the list is empty. Each subsequent element contains a pointer to the next element, or nullptr if there is no next element.

Inside STL: The string -- Raymond Chen

By Blog Staff | Sep 4, 2023 03:07 PM | Tags: None

You might think that a std::string (and all of its friends in the std::basic_string family) are basically a vector of characters internally. But strings are organized differently due to specific optimizations permitted for strings but not for vectors.

Inside STL: The string

By Raymond Chen

From the article:

The starting point for a std::basic_string is this:¹

template<typename T>
struct basic_string
{
    T* ptr;
    size_t size;
    size_t capacity;
};

The ptr is a pointer to the beginning of the string contents.

The size is the number of characters in the string, not including the null terminator.

The capacity is the string capacity, not including the null terminator.

The picture for this simplified version is as follows:

Inside STL: The vector -- Raymond Chen

By Blog Staff | Aug 31, 2023 03:01 PM | Tags: None

The C++ language comes with a standard library, and although implementations are welcome to implement the library types in whatever manner they choose, they are constraints imposed by the standard which often force one of a small number of possible implementations.

Inside STL: The vector

By Raymond Chen

The std::vector is one of those types which is constrained to the point that there’s really only one viable implementation.

Internally, a std::vector basically looks like this:

template<typename T>
struct vector
{
    T* first;
    T* last;
    T* end;
};

The first is a pointer to the beginning of a single memory allocation that holds the vector contents.

The last is a pointer one past the end of the last valid vector element.

The end is a pointer one past the end of the last allocated memory for the vector.

The picture for this is as follows:

Inside STL: The Pair and The Compressed Pair -- Raymond Chen

By Blog Staff | Aug 29, 2023 02:57 PM | Tags: None

The C++ language comes with a standard library. When you’re debugging your C++ code, you may have to go digging inside the implementation to extract information from crash dumps. This mini-series is going to look at how various C++ standard library types are implemented by the three major implementations (clang, gcc, and msvc).

Inside STL: The Pair and The Compressed Pair

By Raymond Chen

From the article:

The C++ language comes with a standard library. When you’re debugging your C++ code, you may have to go digging inside the implementation to extract information from crash dumps. This mini-series is going to look at how various C++ standard library types are implemented by the three major implementations (clang, gcc, and msvc).

We’ll start with the lowly std::pair. Its definition is quite simple.

template<typename T1, typename T2>
struct pair
{
    T1 first;
    T2 second;
};

The names of the members of std::pair are required by the C++ language standard, so you don’t see any variation here. Here’s how it looks in the Windows debugger:

0:000> ?? t
struct std::pair<int,int>
   +0x000 first            : 0n42
   +0x004 second           : 0n99

Understanding Ranges Views and View Adaptors Objects in C++20/C++23 -- Bartlomiej Filipek

By Blog Staff | Aug 27, 2023 02:50 PM | Tags: None

In this article, we’d shed some light on the implementation of ranges::reverse_view and std::views::reverse. We’ll compare them to understand the differences between views and their adaptor objects.

Understanding Ranges Views and View Adaptors Objects in C++20/C++23

By Bartlomiej Filipek

From the article:

Let’s look at an example to understand how these views work. Assume we have a range r of integers from 1 to 5. When we apply std::views::reverse to r, it creates a view representing the elements of r in the reverse order.

#include <ranges> 
#include <vector> 
#include <iostream>  

int main() {
  std::vector<int> r = {1, 2, 3, 4, 5};  
  auto reversed = r | std::views::reverse;  
  for (auto i : reversed)  
     std::cout << i << " ";   

  // same as:  
  for (auto i : r | std::views::reverse)  
     std::cout << i << " "; 
}