C++20 Dynamic Allocations at Compile-time -- Andreas Fertig

By Blog Staff | Sep 26, 2023 09:42 AM | Tags: None

People often say constexpr all the things. Andreas Fertig shows where we can use dynamic memory at compile time.

C++20 Dynamic Allocations at Compile-time

By Andreas Fertig

From the article:

You may already have heard and seen that C++20 brings the ability to allocate dynamic memory at compile-time. This leads to std::vector and std::string being fully constexpr in C++20. In this article, I like to give you a solid idea of where you can use that.

How does dynamic allocation at compile-time work?

First, let’s ensure that we all understand how dynamic allocations at compile-time work. In the early draft of the paper ‘Standard containers and constexpr’ [P0784R1], proposed so-called non-transient allocations. They would have allowed us to allocate memory at compile-time and keep it to run-time. The previously allocated memory would then be promoted to static storage. However, various concerns did lead to allowing only transient allocations. That means what happens at compile-time stays at compile-time. Or in other words, the dynamic memory we allocate at compile-time must be deallocated at compile-time. This restriction makes a lot of the appealing use-cases impossible. I personally think that there are many examples out there that are of only little to no benefit.

Passkey Idiom: A Useful Empty Class -- Arne Mertz

By Blog Staff | Sep 22, 2023 05:39 AM | Tags: None

How do you share some but not all of a class? Arne Mertz introduces the passkey idiom to avoid exposing too much with friendship.

Passkey Idiom: A Useful Empty Class

By Arne Mertz

From the article:

Let’s have a look at an example for useful empty classes. The passkey idiom can help us regain the control that we give up by simply making classes friends.

The problem with friendship

Friendship is the strongest coupling we can express in C++, even stronger than inheritance. So, we’d better be careful and avoid it if possible. But sometimes we just can’t get around giving one class more access than another.

A common example is a class that has to be created by a factory. The factory needs access to the class’s constructors. Other classes should not have that access so as not to circumvent the bookkeeping or whatever else makes the factory necessary.

The problem with the friend keyword is that it gives access to everything. There is no way to tell the compiler that the factory should not have access to any other private elements except the constructor. It’s all or nothing. 

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: