tailieunhanh - A Complete Guide to Programming in C++ part 80

A Complete Guide to Programming in C++ part 80. This book provides both novice and experienced programmers with a comprehensive resource manual for the C++ programming language. Readers gain experience in all aspects of programming, from elementary language concepts to professional software development, with in depth coverage of all the language elements en route. These elements are carefully ordered to help the reader create useful programs every step of the way. | ASSOCIATIVE CONTAINERS 769 Sequences store objects in linear order. Searching for a given object will thus require a linear runtime. If you have only a few objects to deal with this will not cause any significant delay. However it is a major disadvantage in large collections of objects. Representing Sets and Maps Associative containers with different classes that represent sets and maps allow you optimize runtimes. They manage objects in so-called heaps that is in trees with a minimum height. Operations are performed by sortable keys. One of the characteristics of a heap is that the object with the smallest key is always stored at the top of the heap. Insertion deletion and search operations in sets and maps can be performed with logarithmic runtimes. That is the response is proportional to log n where n is the number of objects in a container. Since a logarithmic function grows very slowly response will be phenomenally quick. Unique and Ambiguous Keys In a set each object contains a key. This is why we refer to embedded keys. The relationship between the objects is defined by reference to this key. Besides sets which have unique keys you can also define multisets where multiple objects can have the same key. Maps are used to manage key object pairs. In other words the key is not embedded in the object but stored separately from it. The type of the key is Key and T is the object type. The relationship between the objects is again defined by the keys. Besides maps which contain only unique keys you can also define multimaps where several objects can exist for a single key. Associative Container Classes The opposite page shows various classes used to represent sets multisets maps and multimaps. The template parameter Compare is a comparator class and Allocator is an allocator class. Both parameters have default values which we already saw in the context of sequences. The methods begin and end are defined for access to the positions in all associative container .