Team LiB
Previous Section Next Section

Chapter 10. Associative Containers

第十章 关联容器

CONTENTS

Section 10.1 Preliminaries: the pair Type

356

Section 10.2 Associative Containers

358

Section 10.3 The map Type

360

Section 10.4 The set Type

372

Section 10.5 The multimap and multiset Types

375

Section 10.6 Using Containers: Text-Query Program

379

Chapter Summary

388

Defined Terms

388


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.

本章将继续介绍标准库容器类型的另一项内容——关联容器。关联容器和顺序容器的本质差别在于:关联容器通过键(key)存储和读取元素,而顺序容器则通过元素在容器中的位置顺序存储和访问元素。

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. 关联容器类型

map

Associative array; elements stored and retrieved by key

关联数组:元素通过键来存储和读取

set

Variable-sized collection with fast retrieval by key

大小可变的集合,支持通过键实现的快速读取

multimap

map in which a key can appear multiple times

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

multiset

set in which a key can appear multiple times

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


Team LiB
Previous Section Next Section