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

CppCon.org
-
Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/CppCon/CppCon2018
-
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
Marc Gregoire is a software architect from Belgium. He worked 6 years as a consultant for Siemens and Nokia Siemens Networks on critical 2G and 3G software running on Solaris for telecom operators. This required working with international teams stretching from South America and the United States to Europe, the Middle East, Africa, and Asia. Now, Marc is a software architect at Nikon Metrology (www.nikonmetrology.com), a division of Nikon and a leading provider of precision optical instruments and metrology solutions for 3D geometric inspection.
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.
Marc is the founder of the Belgian C++ Users Group (www.becpp.org), author of "Professional C++" 2nd, 3rd, and 4th editions, published by Wiley/Wrox, co-author of "C++ Standard Library Quick Reference" (Apress), technical editor for numerous books for several publishers, and a member on the CodeGuru forum (as Marc G). He maintains a blog at www.nuonsoft.com/blog/, and is passionate about traveling and gastronomic restaurants.
-
Videos Filmed & Edited by Bash Films: www.BashFilms.com
*-----*
Register Now For CppCon 2022: cppcon.org/registration/
*-----*

[@atib1980]

I think there is a bug at 16:57. Shouldn't std::set in the using declaration using adjacency_list_type = std::set; be templated on T as well as in the following statement: using adjacency_list_type = std::size_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.

[@Dth091]

std::size_t is not a template. His code is fine, the std::size_t is used as an index into a vector and doesn't have anything to do with the T being stored.