Professional C__ - Marc Gregoire [187]
Choosing an Algorithm
The number and capabilities of the algorithms might overwhelm you at first. It can also be difficult to see how to apply them in the beginning. However, now that you have an idea of the available options, you are better able to tackle your program designs. The next chapters cover the details of how to use these algorithms in your code.
What’s Missing from the STL
The STL is powerful, but it’s not perfect. Here is a list of omissions and unsupported functionality:
The STL does not guarantee any thread safety for accessing containers simultaneously from multiple threads.
The STL does not provide any generic tree or graph structures. Although maps and sets are generally implemented as balanced binary trees, the STL does not expose this implementation in the interface. If you need a tree or graph structure for something like writing a parser, you will need to implement your own or find an implementation in another library.
However, it is important to keep in mind that the STL is extensible. You can write your own containers or algorithms that will work with existing algorithms or containers. So, if the STL doesn’t provide exactly what you need, consider writing your desired code such that it works with the STL. Chapter 17 covers the topic of customizing and extending the STL.
SUMMARY
This chapter provided an overview of the C++ standard library, which is the most important library that you will use in your code. It subsumes the C library and includes additional facilities for strings, I/O, error handling, and other tasks. It also includes generic containers and algorithms, which are together referred to as the standard template library (STL). The next chapters describe the standard template library in more detail.
Chapter 12
Understanding Containers and Iterators
WHAT’S IN THIS CHAPTER?
What iterators are
What the different container classes are and how to use them
Chapter 11 introduced the STL, described its basic philosophy, and provided an overview of the various containers and algorithms. You should be familiar with Chapter 11 before you tackle Chapter 12.
This chapter begins a tour of the STL by covering the STL containers, including the following:
Containers Overview: requirements on elements, general error handling, and iterators
Sequential Containers: vector, deque, list, array, and forward_list
Container Adapters: queue, priority_queue, and stack
Associative Containers: the pair utility, map, multimap, set, and multiset
Unordered Associative Containers/Hash Tables: unordered_map, unordered_multimap, unordered_set, and unordered_multiset
Other Containers: standard C-style arrays, strings, streams, and bitset
A detailed list of available classes and methods can be found in the Standard Library Reference resource on the website.
The next chapters will go deeper in on topics like algorithms, strings, regular expressions, I/O and how you can customize and extend the STL.
CONTAINERS OVERVIEW
Containers in the STL are generic data structures useful for storing collections of data. You should rarely need to use a standard C-style array, write a linked list, or design a stack when you use the STL. The containers are implemented as templates, which allow you to instantiate them for any type that meets certain basic conditions outlined below. Most of the STL containers, except for the std::array and std::bitset, are flexible in size and will automatically grow or shrink to accommodate more or fewer elements. This is a huge benefit compared to the old standard C-style arrays, which had a fixed size. Because of the fixed-size nature of standard C-style arrays, they are more vulnerable to overruns, which in the simplest cases merely cause the program to crash because data has been corrupted, but in the worst cases allow certain kinds of security attacks. By using STL containers your programs will be less vulnerable to these