Team LiB
Previous Section Next Section

Chapter 10. Associative Containers

第十章 关联容器


Section 10.1 Preliminaries: the pair Type


Section 10.2 Associative Containers


Section 10.3 The map Type


Section 10.4 The set Type


Section 10.5 The multimap and multiset Types


Section 10.6 Using Containers: Text-Query Program


Chapter Summary


Defined Terms


This chapter completes our review of the standard library container types by looking at the associative containers. Associative containers differ in a fundamental respect from the sequential containers: Elements in an associative container are stored and retrieved by a key, in contrast to elements in a sequential container, which are stored and accessed sequentially by their position within the container.


Although the associative containers share much of the behavior of the sequential containers, they differ from the sequential containers in ways that support the use of keys. This chapter covers the associative containers and closes with an extended example that uses both associative and sequential containers.


Associative containers support efficient lookup and retrieval by a key. The two primary associative-container types are map and set. The elements in a map are keyvalue pairs: The key serves as an index into the map, and the value represents the data that are stored and retrieved. A set contains only a key and supports efficient queries to whether a given key is present.

关联容器(Associative containers)支持通过键来高效地查找和读取元素。两个基本的关联容器类型是 map setmap 的元素以键-值(key-value)对的形式组织:键用作元素在 map 中的索引,而值则表示所存储和读取的数据。set 仅包含一个键,并有效地支持关于某个键是否存在的查询。

In general, a set is most useful when we want to store a collection of distinct values efficiently, and a map is most useful when we wish to store (and possibly modify) a value associated with each key. We might use a set to hold words that we want to ignore when doing some kind of text processing. A dictionary would be a good use for a map: The word would be the key, and its definition would be the value.

一般来说,如果希望有效地存储不同值的集合,那么使用 set 容器比较合适,而 map 容器则更适用于需要存储(乃至修改)每个键所关联的值的情况。在做某种文本处理时,可使用 set 保存要忽略的单词。而字典则是 map 的一种很好的应用:单词本身是键,而它的解释说明则是值。

An object of the map or set type may contain only a single element with a given key. There is no way to add a second element with the same key. If we need to have multiple instances with a single key, then we can use multimap or multi set, which do allow multiple elements with a given key.

setmap 类型的对象所包含的元素都具有不同的键,不允许为同一个键添加第二个元素。如果一个键必须对应多个实例,则需使用 multimapmulti set,这两种类型允许多个元素拥有相同的键。

The associative containers support many of the same operations as do the sequential containers. They also provide specialized operations that manage or use the key. In the sections that follow, we look at the associative container types and their operations in detail. We'll conclude the chapter by using the containers to implement a small text-query program.


Table 10.1. Associative Container Types
表 10.1. 关联容器类型


Associative array; elements stored and retrieved by key



Variable-sized collection with fast retrieval by key



map in which a key can appear multiple times

支持同一个键多次出现的 map 类型


set in which a key can appear multiple times

支持同一个键多次出现的 set 类型

Team LiB
Previous Section Next Section