Professional C__ - Marc Gregoire [289]
How to write your own containers
How to write your own iterators
The previous chapters show that the STL is a powerful general-purpose collection of containers and algorithms. The information covered so far should be sufficient for most applications. However, those chapters show only the basic functionality of the library. The STL can be customized and extended however you like. For example, you can apply iterators to input and output streams; write your own containers, algorithms, and iterators; and even specify your own memory allocation schemes for containers to use. This chapter provides a taste of these advanced features, primarily through the development of a new STL container: the hashmap.
This chapter is not for the faint of heart! The contents delve into some of the most complicated and syntactically confusing areas of the C++ language. If you’re happy with the basic STL containers and algorithms from the previous chapters, you can skip this one. However, if you really want to understand the STL, not just use it, give this chapter a chance. You should be comfortable with the operator overloading material of Chapter 18, and because this chapter uses templates extensively, you should also be comfortable with the template material in Chapter 19 before continuing!
ALLOCATORS
Every STL container takes an Allocator type as a template parameter, for which the default will usually suffice. For example, the vector template definition looks like this:
template The container constructors then allow you to specify an object of type Allocator. These extra parameters permit you to customize the way the containers allocate memory. Every memory allocation performed by a container is made with a call to the allocate() method of the Allocator object. Conversely, every deallocation is performed with a call to the deallocate() method of the Allocator object. The standard library provides a default Allocator class called allocator, which implements these methods as wrappers for operator new and operator delete. If you want containers in your program to use a custom memory allocation and deallocation scheme, you can write your own Allocator class. There are several reasons for using custom allocators. For example, if the underlying allocator has unacceptable performance, there are alternatives that can be constructed. Or, if memory fragmentation is a problem (lots of different allocations and deallocations leaving unusable small holes in memory), a single “pool” of objects of one type can be created, called a memory pool. When OS specific capabilities, such as shared memory segments, must be allocated, using custom allocators allows the use of STL containers in those shared memory segments. The use of custom allocators is complex, and there are many possible problems if you are not careful, so this should not be approached lightly. Any class that provides allocate(), deallocate(), and several other required methods and typedefs can be used in place of the default allocator class. However, in our experience, this feature is rarely used, so we have omitted the details from this book. For more details, consult one of the books on the C++ Standard Library listed in Appendix B. ITERATOR ADAPTERS You can also write your own iterator adapters. Consult one of the books on the Standard Library listed in Appendix B for details. Reverse Iterators The STL provides a reverse_iterator class that iterates through a bidirectional or random access iterator in a reverse direction. Every reversible container in the STL, which happens to be every container that’s part of the standard, supplies a typedef reverse_iterator and methods called rbegin() and
The Standard Library provides four iterator adapters: special iterators that are built on top of other iterators. You’ll learn more about the adapter design pattern in Chapter 29. For now, just appreciate what these iterators can do for you. All four iterator adapters are declared in the