CppCon 2018: Marc Gregoire “Writing Standard Library Compliant Data Structures and Algorithms”

—
—
The C++ Standard Library provides a lot of data structures, such as sequential containers (vector, array, deque, list, and forward_list), ordered associative containers (set, map, multiset, and multimap), unordered associative containers (unordered_set, ...), and container adaptors (stack, queue, and priority_queue). It also provides a wealth of algorithms for sorting, searching, computing, and so on.

Even so, it cannot provide every possible data structure or algorithm that you might need. So, sometimes, you might find the need to write your own data structure or algorithm. Since you are writing them yourself, you could give them any interface that suits you. However, wouldn't it be better to make them compliant with the Standard Library? That way, when you write your own algorithm, you will be able to use that algorithm independently of the type of the container that contains the data for your algorithm. Similarly, if you write a Standard Library compliant data structure, then you will be able to use Standard Library algorithms on the data in your own data structure.

It's clear, there are a lot of advantages in making your data structures and algorithms compliant with the Standard Library. We'll first develop a simple algorithm with our own interface. Then we'll look into what changes we have to make to transform the interface to be Standard Library compliant. Finally, we'll demonstrate our adapted algorithm by running it on data in a variety of Standard Library containers.

In the last part of the presentation we'll crank it up a notch. We'll start by writing our own data structure, initially without thinking too much about the Standard Library. Then we'll look at an overview of the different sets of requirements that the Standard Library imposes for the different types of containers (sequential, associative, and unordered associative). Finally, we'll adapt our data structure step-by-step to transform it into a Standard Library compliant data structure. This of course includes writing a suitable iterator. Finally, we'll demonstrate the transformed data structure by running Standard Library algorithms on the data in it.

If you want to write truly generic and flexible data structures and algorithms, then this session is for you.
—
Marc Gregoire, Nikon Metrology
Software Architect

His main expertise is in C/C++, and specifically Microsoft VC++ and the MFC framework. He has experience in developing C++ programs running 24/7 on Windows and Linux platforms: for example, KNX/EIB home automation software. In addition to C/C++, Marc also likes C# and uses PHP for creating web pages.

Since April 2007, he has received the annual Microsoft MVP (Most Valuable Professional) award for his Visual C++ expertise.

—

*-----*
*-----*

[atib]

I think there is a bug at 16:57. Shouldn't std::set<size_t> in the using declaration using adjacency_list_type = std::set<size_t>; be templated on T as well as in the following statement: using adjacency_list_type = std::size_t<T>; It only makes sense to make the node's value_type templated on T as well, because he doesn't keep track of each node's id (size_t) value separately.