Simple play icon Course

C++ Standard Library: Associative Containers

by Giovanni Dicanio

This course will teach you in a practical way, with slides and demo code, how to use important associative containers available in the C++ Standard Library (e.g. std::map). You will learn their pros and cons, and common operations.

What you'll learn

Non-trivial computer programs need to store data and process it. Developing data structures and containers from scratch in C++ is a daunting and bug-prone task. In fact, you would have to consider advanced aspects like manual memory and resource management, proper handling subtle corner cases, writing both generic code and code that is optimized for special cases, and so on. Moreover, there are some data structures like balanced binary search trees or hash tables that are very useful in applications; however, it is definitely non-trivial to implement from scratch.
Thankfully, the C++ Standard Library already offers containers that are high-quality, efficient, and well-tested. It’s a joy to develop C++ code reusing them: in fact, using these containers in your C++ code will boost your productivity, as the C++ Standard Library gives you on a platter high-quality implementations of common and useful data structures that you can easily leverage in your C++ code. C++ Standard Library’s maintainers spend hours looking at these data structures, and improving, refining, and optimizing their C++ implementation code. In this course, C++ Standard Library: Associative Containers, you will learn how to simply reuse that treasure in your own C++ applications.
First, you will explore std::map, which isa very versatile and convenient associative container that you can use when you need to associate some unique keys to additional values. This can come in handy in lots of applications, from translation dictionaries, to computer graphics programs to databases.
Next, you will discover important operations, like inserting, removing, and searching elements. You will first see them described in theory using slides, including a discussion of their asymptotic runtime complexity. Then, you’ll also see them in action in practical demo code. You will also touch on how to achieve even better performance than std::map, using std::unordered_map. You’ll see how that comes at a cost, though, like losing element ordering that is guaranteed by std::map. Then, you will see a practical demo code with a benchmark comparing std::unordered_map vs. std::map performance in action.
Finally, you will learn how to easily store unique elements in a specific container, maintaining element ordering. This is possible using std::set. You will see how to store custom objects in std::set, including how to fix a subtle bug. I hope that discussing subtle bugs that are especially frequent for those starting to learn the C++ Standard Library containers will save you precious time and headache during your C++ programming. To proficiently follow this course, you only need a basic knowledge of C++ language features. You also need to know some basic architectural elements ofthe C++ Standard Library, like iterators, that are described in my “C++ Standard Library: Sequential Containers” course.
After completing this course, you will be able to use high-quality efficient and well-tested C++ Standard Library associative containers like std::map, std::unordered_map and std::set in your own C++ code. You will have practical knowledge about them, and be able to make proper judgement about picking one or the other based on the problem at hand. You will also have knowledge about important common operations with these standard associative containers such as inserting, removing, and searching elements.

About the author

Giovanni Dicanio is a computer programmer specialized in both cross-platform C and C++, and Windows operating system development. Giovanni wrote computer programming articles on C++, OpenGL and other programming subjects on Italian computer magazines. He recently authored some C++ feature articles for MSDN Magazine, too. He contributed code to some open-source projects as well. His computer programming experience dates back to the glorious Commodore 64 and Amiga 500 golden days, with Basic and a... more

Ready to upskill? Get started