STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library, 2nd Edition

Features

• NEW!

"The second edition is clearer and adds more examples on how to use STL in a practical environment. Moreover, it is more concerned with performance and tools for its measurement. Both changes are very welcome."
--Lawrence Rauchwerger, Texas A&M University

"So many algorithms, so little time! The generic algorithms chapter with so many more examples than in the previous edition is delightful! The examples work cumulatively to give a sense of comfortable competence with the algorithms, containers, and iterators used."
--Max A. Lebow, Software Engineer, Unisys Corporation

The STL Tutorial and Reference Guide is highly acclaimed as the most accessible, comprehensive, and practical introduction to the Standard Template Library (STL). Encompassing a set of C++ generic data structures and algorithms, STL provides reusable, interchangeable components adaptable to many different uses without sacrificing efficiency. Written by authors who have been instrumental in the creation and practical application of STL, STL Tutorial and Reference Guide, Second Edition includes a tutorial, a thorough description of each element of the library, numerous sample applications, and a comprehensive reference.

You will find in-depth explanations of iterators, generic algorithms, containers, function objects, and much more. Several larger, non-trivial applications demonstrate how to put STL's power and flexibility to work. This book will also show you how to integrate STL with object-oriented programming techniques. In addition, the comprehensive and detailed STL reference guide will be a constant and convenient companion as you learn to work with the library.

This second edition is fully updated to reflect all of the changes made to STL for the final ANSI/ISO C++ language standard. It has been expanded with new chapters and appendices. Many new code examples throughout the book illustrate individual concepts and techniques, while larger sample programs demonstrate the use of the STL in real-world C++ software development. An accompanying Web site, including source code and examples referenced in the text, can be found at http://www.cs.rpi.edu/~musser/stl-book/index.html.

Source Code

Click below for Source Code related to this title:
Source Code
Source Code

Praise For STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library, 2nd Edition

"The STL Tutorial and Reference Guide is still one of the best introductions to the STL. Even though the first edition is only slightly outdated, the second edition is unreservedly recommendable as a tutorial to the STL. Programmers who have already been using the STL might find the book too basic, but it is a very accessible and practical first-time exposition for novices." - DevX.com

Index

A

Abstract data types, 127

Abstractions, family of, 127-128

Accessor(s)

container, 144-145

lists and, 160

maps/multimaps and, 181

sorted associative containers and, 170-173

deque and, 151

accumulate algorithm, 33-42, 122-123, 184-187, 427

Actual types, 8

Adaptability, 5

Adaptor(s)

basic description of, 40-43

pointer-to-function, 43

priority_queue, 43

queue, 43

reference guide, 431-440

stack, 43

adjacent_difference algorithm, 124-125, 430

adjacent_find algorithm, 77, 78-80, 231, 248, 389, 392-393

allocate function, 451

Allocator(s)

basic description of, 3, 43-44

class, 441-454

common member functions in all, 443-445

constructors, 446

custom, 448-454

destructors, 446

objects, 320

reference guide, 441-454

passing, to STL containers, 441-442

requirements, 442-445

Allocator template parameter, 14, 150, 154, 332, 340, 360, 374

Amortized

constant time, 17-18

time complexity, 17-18

Anagram groups. Anagrams

copying, to output streams, 232

finding, 225-233

outputting, in order of size, 237-238, 249

Anagrams. See also Anagram groups

multimaps and, 243-250

searching for, 215-217, 225-342

ANSI/ISO C++ Committee, 4

ANSI/ISO C++ Standard, 484

arithmetic operations, 433

Arrays

copying versions of algorithms and, 74-75

demonstrating the find algorithm with, 26-30

demonstrating the merge algorithm with, 31-32

find algorithm and, 66

input iterators and, 51-52

lists and, 153

maps and, 174-175

output iterators and, 53-54

rearranging elements of, 76

ASCII (American Standard Code for Information Interchange), 267, 273

assert macro, 21

assign function, 146-147, 152, 160, 174

Associative containers, 24-26, 320-321

Automatic expansion, 240-241

B

back function, 140-143, 193, 196

back_inserter template, 60-61, 63

back_inserter function, 314

back insert iterators, 60-61, 313-315

basic_string class, 462-472

begin function, 20-21, 24, 28, 34, 69-70, 165, 220

Bidirectional iterator(s), 36, 49, 55-57. See also Iterators

classification of, 58

requirements, 299-300

as more powerful, 67

random access iterators and, 56

reverse algorithm and, 96

sequence containers and, 137-138

Big-Oh notation, 15-18, 287, 292, 389

binary_function, 39, 187

binary predicate parameters, 75-76

binary_search algorithm, 68, 112-114

basic description of, 410, 415-417

random access iterators and, 56-57

searching dictionaries and, 218, 221, 228

Binders, 43, 205-206, 435-436. See also Function adaptors

Boolean values, 7, 21, 166

Borland C++, 484

Briggs's nuweb tool, 217

C

C++ (high-level language)

compilers, STL-compatible, 484

literate programming and, 223

libraries, STL and difference between, 45-48

partial specialization and, 147

templates, generic programming and, relationship of, 7-14

Standard Library, 4

C++ Programming Language, The (Stroustrup), 260, 261

char* data type, 28

char_traits class, 472-476

char_type, 474-475

Character

manipulation functions, 473-476

traits, 472-476

Class(es). See also Classes (listed by name); Container adaptors

declarations, 330, 332

descriptions, organization of, 330-331

I/O stream, interacting with, 218-220

Classes (listed by name). See also Classes

allocator class, 441-454

basic_string class, 462-472

calc_square<int> class, 91

char_traits class, 472-476

earlier class, 275

greater class, 76

istream_iterator class, 72, 304-307

iterator_category class, 303-304

iterator_traits class, 254, 301-303

line class, 260

list<char> class, 13

list class, 56

map class, 162

multimap class, 162

multiply class, 39

multiset class, 162-174

ostream_iterator class, 54, 72, 289, 298, 304-309

PriorityQueueAsList class, 194

PriorityQueueAsVector class, 194

QueueAsDoubleList class, 194

QueueAsList class, 194

QueueAsVector class, 194

rectangle class, 260-261

reverse_iterator class, 203, 310-311

set class, 162-174

shape class, 260

StackAsList class, 194

string class, 21-22, 26, 103, 218-220, 461-472

timer class, 284-292

vector<char> class, 12-14

vector class, 12, 28, 30, 331-339

clock function, 279-280, 282-283

CLOCKS_PER_SEC constant, 280

clock_t, 280

"Code bloat" problem, 14, 208, 259, 265-266

Comments, 274

Compare(), 164

Comparison

functions, 455-457

objects, sorting word pairs with, 230

operations, 58, 433-434, 455-457

Compatibility

algorithm/container, 48, 68

plug, 6

Compilers, STL-compatible, 484

Components

categories of, 34

interchangeability of, 46-48

overview of, 18-44

const_iterator, 69-72, 130, 145

const_pointer, 130

const_reference, 130, 145

const_reverse_iterator, 201

Constant iterators

basic description of, 296

versus mutable iterators, 68-70

Constant reference parameters, 9

Constant time, 16, 56, 147, 167, 296

Constructor(s)

allocator, 446

basic description of, 319, 324-325

class descriptions and, 331

constructing sequences with, 130-135

deque, 340-341

function objects and, 190

iterators and, 306-309, 311, 314-316

lists and, 154, 347-348

map, 176, 368

multimap, 176, 374

priority_queue, 384

queue, 382

sequence containers and, 130-135, 150, 154

set, 154, 356

sorted associative containers and, 164, 176

stacks and, 379

string, 463-466

utilities and, 457

vector, 334-335

Container(s)

accesssors, 144-145

adaptors, 193-200, 319

allocators and, 43-44

associative, 24-26, 320-321

basic description of, 19-26

in C++ libraries other than STL, 45-48

class descriptions, 330-339

classes, generic, 9

combining, with algorithms, 58-59

common type definitions in all, 320-321

common member functions in all, 322-323

common members in all, 320-323

compatibility of, with algorithms, 48, 68

connecting, with iterators, 4, 5

converting strings to, 13

design and organization of, 319-320

equality, 145-146

important characteristics of, 319-320

instances, "code bloat" from, 265-266

iterator categories and, 58, 59, 71-72

less-than relations and, 145-146

passing allocators to, 441-442

reference guide, 319-386

reversible, 324

sequence, 19-24

sorted, 24-26

sorted associative, 127

Container template parameter, 13

Converse relation, 105

copy algorithm, 53-54, 87-89, 289

basic description of, 398, 399-400

iterators and, 204, 297

searching dictionaries and, 218, 249

copy_backward algorithm, 87-89

copy constructor, 134, 190

defining iterator classes and, 253, 254-255

insert iterators and, 60, 61

copying versions, of algorithms, 74-75

count algorithm, 77, 80-81, 172-173, 389, 393-394

count_if algorithm, 80-81

counting iterators, 251-258

ctime header, 280

Custom allocators, 448-454. See also Allocators

CWeb, 223

D

Data abstraction, 127

Database(s)

associating students with advisors in, 268-270

sorting student data in, 267-268

trees, finding the roots of, 270-273

data_map, 268, 275

Data structures

defining, 226-227

holding iterator pairs, 234-235

deallocate function, 451, 454

default allocators, 445-448

Default template parameters, 14

Deferenceable value, use of the term, 295

Deletions, See also Erasure

container adaptors and, 193

lists and, 152-153

stacks and, 378

deque

basic description of, 29, 148-152, 339-345

common members of, 320-321

constructors, 151, 340-341

destructors, 340-341

container adaptors and, 193, 194-197

demonstrating the find algorithm with, 29-30

demonstrating the merge algorithm with, 31-32

destructors, 340-341

erasure and, 142, 344, 345-354

find algorithm and, 66

insert functions, 343-345, 350

iterators, 61, 62, 59, 150

lists and, 153, 154

deque container, 127, 359

Destructor(s)

allocator, 446

basic description of, 319

class descriptions and, 331

deque, 340-341

list, 347-348

map, 368

multimap, 374

set, 356

string, 463-466

vector, 334-335

Dictionaries

finding anagram groups in, 225-233

finding anagrams for a given word in, 215-217

permutations for membership in, testing, 220-221

programs for searching, 215-223

reading, into multimaps, 247-249

reading, into vectors of PS objects, 229-230

Difference types, 130, 295

Directory blocks, reallocation of, 150

Discussion lists, 484

distance function, 249

draw function, 261

E

earlier class, 275

earlier relation, 269

Efficiency, 5

Emptiness, testing for, 379

empty function, 193-194, 196, 198-200

Encapsulation, 43-44, 320

end function, 20-21, 24, 28

accumulate function and, 34

searching dictionaries and, 220

sorted associative containers and, 165

End markers, 72

Equality

deque and, 152

equal algorithm and, 77, 82-85, 389, 395-396

equal_range algorithm and, 112, 172, 410

iterators and, 313

less-than relations and, 145-46

lists and, 160

maps/multimaps and, 181-182

predicate objects, 230-231

sorted associative containers and, 173

erase function, 320, 325-326, 329, 331

deque and, 344, 345-354

iterators and, 70, 71-72

lists and, 155-156, 351, 354

maps and, 371-372

multimaps and, 378

multisets and, 364

sequence containers and, 142-143, 151, 155-156

set and, 359-360

sorted associative containers and, 168-170

strings and, 471

vectors and, 338-339

Erasure. See also Deletion

with the pop_back function, 140-143

lists and, 155-156

maps/multimaps and, 181

with the pop_back function, 140-143

sequence containers and, 140-143, 151, 155-156

sorted associative containers and, 168-170

Extensibility, 46

F

FIFO (first-in, first-out), 196

fill algorithm, 89-90, 398, 403

fill_n algorithm, 89-90

find algorithm, 26-30, 36, 40, 45, 77-78, 389, 391

advantages of, 112

compatibility of, with containers, 48, 68

component interchangeability and, 47-48

defining iterator classes and, 257

definition of, 65-66

iterators and, 50-52, 59, 64-65, 202-203

predicate version of, 77

sorted associative containers and, 168-171

find_end algorithm, 390, 397-398

find_first algorithm, 391-392

find_first_of algorithm, 389

find_if algorithm, 77, 205, 231, 232, 248

first iterator, 21-22, 28, 33, 49-50, 57

function objects and, 184

sequence containers and, 137-138

firstEqual function object, 227-228, 231, 248

firstLess function object, 227-228, 230

for_each algorithm, 77, 81-82, 389-391

Forward iterators, 36, 49, 54-55

classification of, 58

random access iterators and, 56

requirements, 299

sequence containers and, 137-138

forward_counting_iterator, 257

forward_iterator_tag, 254

ForwardIterator template parameter, 54-55, 253

front function, 196, 198

front_inserter function, 61

front insert iterators, 60-61, 315-316

Function(s). See also Function adaptors; Function objects; Functions (listed by name)

parameters, 75-77

pointers to, function adaptors for, 205, 208-211, 436-439

templates, 7, 10-11

virtual, 260-265

Function adaptors, 205-211, 432

binders, 43, 205-206, 435-436

categories of, 205

negators, 43, 205, 206-208, 435

for pointers to functions, 205, 208-211, 436-439

using, to obtain predicate objects, 231-232

Function object(s)

basic description of, 36-40, 183-191

creating, for comparisons, 227-228

reference guide, 431-440

operator overloading and, 38

specifying, with template parameters, 186-191

STL-provided, 191

Functions (listed by name). See also erase function; insert function

accumulate function, 33-42, 184-187

allocate function, 451

assign function, 146-147, 152, 160, 174

back function, 140-143, 193, 196

back_inserter function, 314

begin function, 20-21, 24, 28, 34, 69-70, 165, 220

capacity function, 138-140, 151, 160

clock function, 279-280, 282-283

deallocate function, 451, 454

distance function, 249

draw function, 261

empty function, 193-194, 196, 198-200

end function, 20-21, 24, 28, 34, 165, 220

front function, 196, 198

front_inserter function, 61

inserter function, 62, 314

key_compare function, 162-163, 173, 175, 182, 355

key_type function, 162, 175

lexicographical_compare function, 146

make function, 13-14, 23

memcpy function, 474

memmove function, 474

memset function, 474

move function, 261

mult function, 38

my_algorithm function, 304

my_algorithm_impl function, 304

pop_back function, 140-143, 193-194, 198

pop_front function, 61, 142, 151, 196-197

pop function, 194, 199

print_list function, 82

push_back function, 60, 61, 135-140, 148-149, 153-154, 193-198

push_front function, 60, 61, 127, 148-149, 151, 153-154

push function, 194

rbegin function, 201

remove function, 160

rend function, 42-43, 201

report function, 252

reserve function, 138-140, 149-151, 155

reverse function, 136-138

size function, 146, 193, 194, 196, 198-200

sort function, 48

splice function, 156

strchr function, 474

strcmp function, 473

strlen function, 474

swap function, 147, 152, 160, 182

time function, 283-284

top function, 194, 199

unique function, 158-159

vector function, 23, 261

Function templates

basic description of, 7, 10-11

member, 12

functional header, 76

G

Genealogy program, 267-278

Generalized numeric algorithms, 426-427

generate algorithm, 90-91, 398, 404

Generic. See also Generic algorithms

container classes, 9

programming, basic description of, 4-7

Generic algorithms. See also Generic algorithms (listed by name)

basic description of, 3, 5-6, 26-32, 73-126

C++ templates and, relation of, 7-14

choosing the right, 68-70

combining, with containers, 58-59

compatibility of, with containers, 48, 68

component interchangeability and, 47

copying versions of, 74-75

definition of, with function templates, 10-11

demonstrating, with arrays, 26-27

descriptions, organization of, 387-389

designing, 65-66

function parameters and, 75-77

in-place versions of, 74-75

iterator categories and, 58-59, 64-65

organization of, in STL, 73-77

partial specialization and, 14

reference guide, 387-430

which require more powerful iterators, 67

sequence types and, 20

single-pass, 66

timing, class for, 279-317

Generic algorithms (listed by name). See also find algorithm; merge algorithm;

sort algorithm

accumulate algorithm, 122-123, 427

adjacent_difference algorithm, 124-125, 430

adjacent_find algorithm, 77, 78-80, 231, 248, 389, 392-393

binary_search algorithm, 56-57, 68, 112-114, 218, 221, 228, 410, 415-417

copy algorithm, 53-54, 87-89, 204, 218, 249, 289, 297, 398, 399-400

copy_backward algorithm, 87-89

count algorithm, 77, 80-81, 172-173, 389, 393-394

fill algorithm, 89-90, 398, 403

fill_n algorithm, 89-90

find_end algorithm, 390, 397-398

find_first algorithm, 391-392

find_first_of algorithm, 389

find_if algorithm, 77, 205, 231, 232, 248

generate algorithm, 90-91, 398, 404

includes algorithm, 115, 410, 418-421

inner_product algorithm, 125-126, 177-178, 427

inplace_merge algorithm, 114

introselect algorithm, 112

lexicographical_compare algorithm, 120-121, 173

lower_bound algorithm, 112-114, 170-172, 410

make_heap algorithm, 117-119, 410, 421-423

max algorithm, 11, 119-120, 410, 423-424

max_element algorithm, 119-120, 410, 423-424

min algorithm, 119-120, 410, 423-424

min_element algorithm, 119-120, 410, 423-424

mismatch algorithm, 77, 82-85, 389, 394-395

next_permutation algorithm, 121-122, 221, 425-426

nth_element algorithm, 110-112, 410, 414-415

partial_sort algorithm, 106-110, 292, 410, 412-414

partial_sum algorithm, 123-125, 429

partition algorithm, 91-93, 399, 409-410

pop_heap algorithm, 117-119, 410, 421-423

prev_permutation algorithm, 121-122, 425-426

push_heap algorithm, 117-119, 410, 421-423

random_shuffle algorithm, 76, 93-94, 346, 399, 408-409

remove algorithm, 94-95, 351-353, 398, 404-405

remove_if algorithm, 351-353

replace algorithm, 54-55, 95-96, 398, 402-403

replace_copy algorithm, 75

reserve algorithm, 469

reverse_copy algorithm, 74-75

rotate algorithm, 96-97, 399, 408

search algorithm, 65, 77, 96-97, 389, 396

search_n algorithm, 390, 397

set_difference algorithm, 115-117, 410, 418-421

set_intersection algorithm, 115-117, 410, 418-421

set_symmetric difference algorithm, 115-117, 410, 418-421

set_union algorithm, 115-117, 410, 418-421

sort_heap algorithm, 117-119, 410, 421-423

splice algorithm, 351-353

stable_partition algorithm, 91-93

stable_sort algorithm, 106-110, 291, 410, 412-414

swap algorithm, 97-98, 147, 174, 398, 400-401

swap_ranges algorithm, 98-99

transform algorithm, 99-100, 398, 401-402

unique algorithm, 87, 100-102, 351-353, 398, 406-407

Global operations, 313

greater class, 76

greater function object type, 103

greater<string>() binary predicate, 80

greater<T>(), 105

GreaterThan50 object type, 78

H

Hashed associative containers, 161-162

Header files, 260, 289, 359, 477, 479, 481

Heap operations, 117-119, 421-423

heapsort, 106

Homogenous storage, 259

I

ifstream constructor, 220

In-place versions, of algorithms, 74-75

Include files, 477-482

includes algorithm, 115, 410, 418-421

Inheritance, 260-265

inner_product algorithm, 125-126, 177-178, 427

inplace_merge algorithm, 114

Input iterator(s), 35, 49

basic description of, 50-52

classification of, 58

find algorithm and, 65

random access iterators and, 56

requirements, 296-298

InputIterator, 12, 50, 187

inserter function, 62, 314

inserter template, 62

insert function, 12, 60, 62, 70-72, 324-331

deque and, 343-345, 350

lists and, 354

maps and, 371

multimaps and, 376-377

multisets and, 363-364

sequence containers and, 128, 135-140, 143, 151

set and, 358-359

sorted associative containers and, 164-167

strings and, 470-471

vectors and, 338, 339

Insert iterators, 59-62, 316-317

Insertion, 193, 320. See also insert function; Insert iterator

lists and, 152-155, 354

maps/multimaps and, 176-181, 376-377

sorted associative containers and, 164-167

stacks and, 379

insert mode, 59

Instantiation, 8, 13-15

Interchangeability, of components, 46-48

International Standard for C++, 4

introselect algorithm, 112

introsort algorithm, 107

I/O stream classes, interacting with, 218-220

iostreams, 51-52, 218-220

istream_iterator class, 6, 63-65, 72, 304-307

istream iterators, 6, 52, 63-65, 72, 218, 304-307

Iterator(s). See also specific types

accumulate algorithm with, 41-42

adaptors, 201-204

basic description of, 3, 5, 28, 33-36, 49-72

categories, 35, 64-65, 71-72

classes, 72, 251-258, 302-307

containers and, 21

deque, 150

find algorithm and, 28

hierarchy of, 58-59

input, 35

operations, 304

output, 35

pairs, data structure holding, 235-236

range of, 49-50

random access, 36

reference guide, 295-318

requirement of more powerful, for specific algorithms, 67

sequence containers and, 129, 140, 143, 150

subtraction of, 57-58

tags, standard, 303-304

terminology for, 295-296

traits, 301-304

iterator_category class, 303-304

iterator_traits class, 254, 301-303

iterator_type, 137-138

K

Kernighan, Brian, 268, 270

key_compare function, 162-163, 173, 175, 182, 355

keys

basic description of, 161

equivalence, notion of, 163

types of, 162-163

key_type type, 162, 175

Knuth, D. E., 23, 223

L

LastNameLess(), 104

less function object type, 103

less<int>(), 103

Less-than relations, 145-146, 152, 181-182

lists and, 160

sorted associative containers and, 173, 181-182

Levy, S., 223

lexicographical order, 221

lexicographical_compare algorithm, 120-121, 146, 173

LIFO (last-in, first-out), 196

line class, 260

Linear time, 16, 20, 142

List(s)

basic description of, 152-160

common members of, 320-321

constructors, 347-348

demonstrating the find algorithm with, 28-29

destructors, 347-348

erasure and, 142, 354

input iterators and, 51-52

insert functions and, 354

insert iterators and, 61

iterator categories and, 59

nonmutating sequence algorithms and, 84

parameters for, 154

random access iterators and, 57

special operations for, 351-352

storing information in a map of, 236-237

stream iterators and, 63

list<char> class, 13, 23-24

list class, 56

list container, 127, 193, 194-197

demonstrating the merge algorithm with, 31-32

header files and, 359

searching dictionaries and, 235-242

List iterators, 66, 67

List sequence abstraction, 152-160

Literate programming style, 23, 217, 218, 220, 223

Logarithmic time, 16, 112-113

Logical operations, 434-435

lower_bound algorithm, 112-114, 170-172, 410

M

make function, 13-14, 23

make_heap algorithm, 117-119, 410, 421-423

Map(s), 25-26, 365-373

basic description of, 174-182

common members of, 320-321

constructors, 176, 368

demonstrating, 25-26

destructors, 368

insertion into, 176-181

iterators and, 71-72

special operations for, 372-373

map class, 162

map container, 127-128, 235-242, 326-330, 359

map<Key, T> container, 25

map<Key, T> object, 71-72

map<string, long> container, 25

max algorithm, 11, 119-120, 410, 423-424

max_element algorithm, 119-120, 410, 423-424

Maximum time, 15

Member function templates, 11

memcpy function, 474

memmove function, 474

Memory, 283, 453. See also Allocators

constraints, adaptation to, 107

models, 320-321

memset function, 474

merge algorithm, 6, 30-32, 36, 114-115, 410

basic description of, 351-353, 417-418

compatibility of, with containers, 48

component interchangeability and, 47

iterators and, 59, 62-64

lists and, 159

microprocessors, 280, 283

min algorithm, 119-120, 410, 423-424

min_element algorithm, 119-120, 410, 423-424

mismatch algorithm, 77, 82-85, 389, 394-395

move function, 261

mult function, 38

multfunobj operator, 187

multfun operator, 185-186

Multimap(s), 365, 374-378

basic description of, 174-182

common members of, 320-321

constructors for, 176, 374

declarations, 246-147

finding anagram groups in, 247-249

insertion into, 176-181

iterators and, 71-72

searching dictionaries and, 243-250

special operations for, 377-378

multimap class, 162

multimap container, 127-128, 326-330, 359

multimap<Key, T> container, 25

multiply class, 39

Multiset(s), 170-173, 360-365

common members of, 320-321

constructors, 361-362

destructors, 361-362, 374

erasing elements from, 168-170

special operations for, 365

multiset class, 162-174

multiset container, 127-128, 279, 326-330

multiset<Key> container, 25

Mutable iterators, 68-70, 296

Mutating sequence algorithms, 87-102, 398-399. See also reverse algorithm

copy_backward algorithm, 87-89

fill algorithm, 89-90, 398, 403

fill_n algorithm, 89-90

generate algorithm, 90-91, 398, 404

partition algorithm, 91-93, 399, 409-410

random_shuffle algorithm, 76, 93-94, 346, 399, 408-409

remove algorithm, 94-95, 351-353, 398, 404-405

replace algorithm, 54-55, 95-96, 398, 402-403

rotate algorithm, 96-97, 399, 408

swap algorithm, 97-98, 147, 174, 398, 400-401

swap_ranges algorithm, 98-99

stable_partition algorithm, 91-93

transform algorithm, 99-100, 398, 401-402

unique algorithm, 87, 100-102, 351-353, 398, 406-407

my_algorithm function, 304

my_algorithm_impl function, 304

N

negators, 43, 205, 206-208, 435

next_permutation algorithm, 121-122, 221, 425-426

Nondecreasing (ascending) order, 105-106

nonincreasing (descending) order, 105-106

Nonmutating sequence algorithms, 77-87, 389-390. See also find algorithm

adjacent_find algorithm, 77, 78-80, 231, 248, 389, 392-393

count algorithm, 77, 80-81, 172-173, 389, 393-394

equal algorithm, 77, 82-85, 389, 395-396

for_each algorithm, 77, 81-82, 389-391

mismatch algorithm, 77, 82-85, 389, 394-395

search algorithm, 65, 77, 96-97, 389, 396

not_equal_to, 81

nth_element algorithm, 110-112, 410, 414-415

Numeric algorithms, 122-126

nuweb, 217

O

Object-oriented programming, combining STL with, 259-266

Open and orthogonal structure, 46

Operation counting, 186-191

Operators

= operator, 53, 65, 35, 132-33, 255

+ operator, 29, 36-37, 125

++ operator, 29, 33, 35, 49, 51, 53, 65-66, 70, 255-256, 296

* operator, 33, 35, 125, 51, 65-66, 173, 207, 298

< operator, 30, 77, 102-103

- operator, 146-147, 152, 160, 182

== operator, 53, 104, 132-133, 145-146, 163, 173-174, 255

=> operator, 102-103

> operator, 102-103, 105

>= operator, 207

[] operator, 177, 179, 181

overloading, 38

ordering predicates, 313

ostream iterators, 53-54, 72, 289, 298, 304-309

ostream_iterator class, 6, 54, 63, 72, 289, 298, 304-309

ostream_iterator constructor, 54

output iterator(s), 35, 49, 52-54

classification of, 58

random access iterators and, 56

requirements, 298

overwrite mode, 59

P

pair, 8-9, 11, 227, 235, 456

pair<const Key, T>, 71-72

Partial specialization, 14, 147

partial_sort algorithm, 106-110, 292, 410, 412-414

partial_sum algorithm, 123-125, 429

partition algorithm, 91-93, 399, 409-410

Partitioning strategy, 107

partitions, 91-93, 107, 399, 409-410

Pascal, 223

Past-the-end-values, use of the term, 295

Permutation(s)

algorithms, 121-122

generating, 220-221, 425-426

Pointer(s). See also Function adaptors

forward iterators and, 54-55

random access iterators and, 57

sequence containers and, 129

using, as output iterators, 53

pop_back function, 140-143, 193-194, 198

pop_front function, 61, 142, 151, 196-197

pop function, 194, 199

pop_heap algorithm, 117-119, 410, 421-423

position iterator, 12

PPS iterator pair, 235-237

Predicates, 75, 91, 231-232

prev_permutation algorithm, 121-122, 425-426

print_list function, 82

Printing, database information, 275-276

Priority queue, 43, 194, 198-200, 384-385

PriorityQueueAsList class, 194

PriorityQueueAsVector class, 194

priority_queue container adaptor, 198-200, 384-385

Processors, 280, 283

ptr_fun, 209-210

Public member functions, 307, 309, 311-312, 314-317

push_back function, 60, 61, 135-140, 148-149, 153-154, 193-198

push_front function, 60, 61, 127, 148-149, 151, 153-154

push function, 194

push_heap algorithm, 117-119, 410, 421-423

Q

Quadratic time, 16, 142

queue

adaptor, 43, 198-199, 380-383

constructors, 382

priority, 43, 194, 198-200, 384-385

QueueAsDoubleList class, 194

QueueAsList class, 194

QueueAsVector class, 194

quicksort, 107

R

Random access

iterators, 36, 49, 56-58, 300-301

as more powerful, 67

sequence containers and, 137

random_shuffle algorithm, 76, 93-94, 346, 399, 408-409

Ranges, use of the term, 296

rbegin function, 201

Reachability, use of the term, 296

Reallocation, 140, 150

rectangle class, 260-261

relation_map, 270-275

remove algorithm, 94-95, 351-353, 398, 404-405

remove function, 160

remove_if algorithm, 351-353

rend function, 42-43, 201

replace algorithm, 54-55, 95-96, 398, 402-403

replace_copy algorithm, 75

report function, 252

report method, 287-288

reserve algorithm, 469

reserve function, 138-140, 149-151, 155

results method, 284, 287

Reusable components, 4

reverse algorithm, 20-24, 96, 159, 351-353

basic description of, 399, 407

bidirectional iterators and, 55-56

sequence containers and, 149, 152, 154

reverse_copy algorithm, 74-75

reverse function, 136-138

Reverse iterators, 40, 42-43, 130, 201, 203, 309-313, 336, 342, 349

reverse_iterator adaptor, 201

reverse_iterator class, 203, 310-311

reverse_iterator component, 40, 42-43, 130

rotate algorithm, 96-97, 399, 408

S

search algorithm, 65, 77, 96-97, 389, 396

screen.cpp, 477-478, 260

screen.h, 260, 477, 479, 481

screen manager, 260

search_n algorithm, 390, 397

Sequence algorithms, 87-102, 398-399. See also reverse algorithm

copy_backward algorithm, 87-89

fill algorithm, 89-90, 398, 403

fill_n algorithm, 89-90

generate algorithm, 90-91, 398, 404

partition algorithm, 91-93, 399, 409-410

random_shuffle algorithm, 76, 93-94, 346, 399, 408-409

remove algorithm, 94-95, 351-353, 398, 404-405

replace algorithm, 54-55, 95-96, 398, 402-403

rotate algorithm, 96-97, 399, 408

swap algorithm, 97-98, 147, 174, 398, 400-401

swap_ranges algorithm, 98-99

stable_partition algorithm, 91-93

transform algorithm, 99-100, 398, 401-402

unique algorithm, 87, 100-102, 351-353, 398, 406-407

Sequence container(s), 19-24, 146-147

basic description of, 127-160, 319

deque container, 127, 359

common members of, 320-321

constructing sequences with, 130-135

list container, 31-32, 127, 193, 194-197, 235-242, 359

requirements, 324-325

vector container, 127-148, 193, 194-197, 218, 237-238, 240-241, 244, 359

Set(s)

accessors and, 170-173

basic description of, 354-360

common members of, 320-321

constructors, 356

destructors, 356

erasing elements from, 168-170

insert functions and, 358-359

operations, 115-117

set class, 162-174

set container, 127-128, 326-330

set_difference algorithm, 115-117, 410, 418-421

set_intersection algorithm, 115-117, 410, 418-421

set<Key> container, 24-25

set_symmetric_difference algorithm, 115-117, 410, 418-421

set_union algorithm, 115-117, 410, 418-421

SGI Web site, 483

shape class, 260

shape.h, 479, 260

shape libraries, 260

shape.cpp, 260

SIGACT Theoretical Computer Science Genealogy page, 267-278

single-pass algorithms, 297

singular values, use of the term, 296

size dependence, 241

size function, 146, 193, 194, 196, 198-200

sort algorithm, 67, 106-110, 158-159, 281-282, 346, 351-353

basic description of, 410, 412-414

compatibility of, with containers, 48

component interchangeability and, 47-48

in-place version of, 74

iterator categories and, 59

object-oriented programming and, 265

timing, 289-292

used with a binary predicate, 76-77

sorted associative containers, 161-182, 319, 326-330

sorted structures, set operation on, 115-117

sort function, 48

sort_heap algorithm, 117-119, 410, 421-423

sorting

searching dictionaries and, 230, 244

students by date, 267-268

word pairs, with comparison objects, 230

Sorting-related algorithms

basic description of, 102-122, 410-412

comparison relations and, 102-105

stability property of, 104-105, 106

Sorting-related member functions, 158-159

sort iterator, 36

splice algorithm, 351-353

splice function, 156

Splicing, 152, 156-158, 351-353

stable_partition algorithm, 91-93

stable_sort algorithm, 106-110, 291, 410, 412-414

Stack(s)

adaptors, 43, 194-196, 378-380, 459

basic description of, 193

constructors, 380

defining, as classes, 194

empty, testing for, 193

StackAsList class, 194

StackAsVector, 194

start_baseline method, 285

start method, 286

Static variables, 189

STL (Standard Template Library)

basic description of, 3-18

combining, with object-oriented programming, 259-266

-compatible compilers, 484

defining a data structure to work with, 226-227

extensibility and, 46

open and orthogonal structure of, 46

organization of algorithms in, 73-77

other C++ libraries and, difference between, 45-48

performance guarantees, 15-18

user-level descripton of, 4

strchr function, 474

strcmp function, 473

stream iterators, 62-63

stream_input iterator, 218

Strict weak ordering, 104

String(s). See also string class

constructors, 463-466

destructors, 463-466

objects, 20-21

reference guide, 461-475

string class, 21-22, 26, 103, 218-220, 461-472

strlen function, 474

Stroustrup, Bjarne, 260

Subtraction, 57

swap algorithm, 97-98, 147, 174, 398, 400-401

swap function, 147, 152, 160, 182

swap_ranges algorithm, 98-99

T

Template(s), 6-10, 15, 266. See also Template parameters

arguments, explict specification of, 12-14

function, basic description of, 7, 10-11

insert iterators and, 60-61

partial specialization and, 147

template keyword, 9

Template parameters, 14, 64

maps/multimaps and, 175-176

sequence containers and, 150

specifying function objects with, 186-191

Time. See also Time complexity

bound, 16

constant, 16, 56, 147, 167, 296

linear, 16, 20, 142

logarithmic, 16, 112-113

maximum, 15

quadratic, 16, 142

worst-case, 15-18

Time complexity, 78, 80, 86-87, 389

accumlate algorithm and, 427

adjacent_difference algorithm and, 430

adjacent_find algorithm and, 393

binary_search algorithm and, 417

copy algorithm and, 400

equal algorithm and, 395

fill algorithm and, 403

find algorithm and, 391

find_end algorithm and, 398

find_first algorithm and, 392

for_each algorithm and, 391

generate algorithm and, 404

heap operations and, 422

inner_product algorithm and, 427

max algorithm and, 424-425

merge algorithm and, 418

min algorithm and, 424-425

mismatch algorithm and, 395

mutating sequence algorithm and, 96, 97, 99, 100

nth_element algorithm and, 415

partial_sum algorithm and, 429

partition algorithm and, 410

random_shuffle algorithm and, 409

reverse algorithm and, 407

remove algorithm and, 405

replace algorithm and, 403

rotate algorithm and, 408

search algorithm and, 396

search_n algorithm and, 397

set operations and, 421

sort algorithm and, 414

swap algorithm and, 401

transform algorithm and, 402

unique algorithm and, 407

time function, 283-284

timer class, 284-292

timer.h, 289

Timing

accurate, obstacles to, 279-280

algorithms, 279-317

top function, 194, 199

T parameter, 150, 154

transform algorithm, 99-100, 398, 401-402

trichotomy law, 102-103

tuples, 177-180

Type parameters, 8

U

unique algorithm, 87, 100-102, 351-353, 398, 406-407

unique function, 158-159

Unix, 280

upper_bound algorithm, 112-114, 170-172, 410

Upper bounds, 15-17, 112-114, 170-172, 410

utilities

comparison functions and, 455-457

reference guide for, 455-457

V

Value(s)

retrieving, container adaptors and, 193

types, use of the term, 295

value_compare, 163, 175

value_type, 129, 164, 176, 181

Vector(s)

basic description of, 22, 129-148

"code bloat" and, 265-266

common members of, 320-321

constructing sequences with, 130-135

constructors, 130-135, 334-335

containers and, 22

destructors, 334-335

demonstrating, with arrays, 27-28

deque and, 148

erasure and, 140-143

insertion and, 141

iterators and, 57, 61, 66

lists and, 153

mutating sequence algorithms and, 98

of PS objects, reading dictionaries into, 229-230

reallocation and, 140

types, 129-140

vector<char> class, 12-14

vector class, 12, 28, 30, 331-339

vector container, 127, 193, 194-197, 218, 237-238, 240-241, 244, 359

vector<T> container, 19

Virtual functions, 260-265

void type, 448

W

Weak ordering, 121

Web (tool), 223

word_pairs, 231, 238

word_pairs vector, 229, 230

word_pairs multimap, 248-249

Worst-case time, 15-18

Preface

In the five years since the first edition of STL Tutorial and Reference Guide appeared, the C++ language standard has been finalized and officially accepted, C++ compiler vendors have made great progress in bringing their compilers into compliance with the standard, and dozens of other books and magazine articles have appeared that describe and explain the standardized language and libraries. Many of these books and articles have highlighted the Standard Template Library (STL) as the most significant addition to the standard. Some hailed it, as we did in this book's first edition, as having the potential to revolutionize the way a large number of people program. The past five years have already seen much of that potential realized, with the first edition of this book playing a key role for tens of thousands of programmers. We wrote in the preface of the first edition that there are five reasons why the STL components could become some of the most widely used software in existence:

• C++ is becoming one of the most widely used programming languages (in large part due to the support it provides for building and using component libraries).
• Since STL has been incorporated into the ANSI/ISO standard for C++ and its libraries, compiler vendors are making it part of their standard distributions.
• All components in STL are generic, meaning that they are adaptable (by language-supported compile-time techniques) to many different uses.
• The generality of STL components has been achieved without sacrificing efficiency.
• The design of STL components as fine-grained, interchangeable building blocks makes them a suitable basis for further development of components for specialized areas such as databases, user interfaces, and so forth.

Changes in the Second Edition

In this new edition we have added substantially more tutorial material including expanded chapters in Part I on function objects and container, it- erator, and function adaptors, and two entirely new chapters in Part II containing substantial new examples. We have also gone through all example code and surrounding discussion, including the reference material in Part III, to bring them up to date with the final standard. (Although some ambiguities in the standard have been discovered since it was finalized, we believe that in most cases the remaining uncertainties about the meaning of STL component specifications have no important consequences for the practicing programmer. In the few cases where they might, we point them out.) We also added a new chapter in Part III describing utility components such as the pair and comparison classes, and a new appendix describing the STL-related features of the standard string class.

In this edition we have also adopted the "literate programming" style for presenting example programs and code fragments. For readers unfamiliar with this approach to simultaneous programming and documenting, a brief explanation is given in Chapter 2 and more details are presented in Chapter 12. One benefit of the literate programming approach is that coding details can be presented once and then referred to (by name and page number) many times, so readers do not have to read through the same details repeatedly. Another major benefit is that we have been able check even more thoroughly than before that all code is syntactically and logically correct, since literate programming tools make it easy to extract the code directly from the manuscript and compile and test it. A list of the compilers the code has been compiled and tested with is given in Appendix D.

Some History, from the Preface to the First Edition

Virtually all C++ programmers know that this language was originated by one person, Bjarne Stroustrup, who began thinking of how to extend the C language to support definition of classes and objects as early as 1979. So too, the architecture of STL is largely the creation of one person, Alexander Stepanov.

It is interesting that it was also in 1979, at about the same time as Stroustrup's initial research, that Alex began working out his initial ideas of generic programming and exploring their potential for revolutionizing software development. Although Dave Musser had developed and advocated some aspects of generic programming as early as 1971, it was limited to a rather specialized area of software development (computer algebra). Alex recognized the full potential for generic programming and persuaded his then-colleagues at General Electric Research and Development (including, primarily, Dave Musser and Deepak Kapur) that generic programming should be pursued as a comprehensive basis for software development. But at that time there was no real support in any programming language for generic programming. The first major language to provide such support was Ada, with its generic units feature, and by 1987 Dave and Alex had developed and published an Ada library for list processing that embodied the results of much of their research on generic programming. However, Ada had not achieved much acceptance outside the defense industry, and C++ seemed more likely to become widely used and provide good support for generic programming, even though the language was relatively immature (it did not even have templates, added only later). Another reason for turning to C++, which Alex recognized early on, was that the C/C++ model of computation, which allows very flexible access to storage (via pointers), is crucial to achieving generality without losing efficiency.

Still, much research and experimentation were needed, not just to develop individual components, but more important to develop an overall ar- chitecture for a component library based on generic programming. First at AT&T Bell Laboratories and later at Hewlett-Packard Research Labs, Alex experimented with many architectural and algorithm formulations, first in C and later in C++. Dave Musser collaborated in this research, and in 1992 Meng Lee joined Alex's project at HP and became a major contributor.

This work undoubtedly would have continued for some time as just a research project or at best would have resulted in an HP proprietary library, if Andrew Koenig of Bell Labs had not become aware of the work and asked Alex to present the main ideas at a November 1993 meeting of the ANSI/ISO committee for C++ standardization. The committee's response was overwhelmingly favorable and led to a request from Andy for a formal proposal in time for the March 1994 meeting. Despite the tremendous time pressure, Alex and Meng were able to produce a draft proposal that received preliminary approval at that meeting.

The committee had several requests for changes and extensions (some of them major), and a small group of committee members met with Alex and Meng to help work out the details. The requirements for the most significant extension (associative containers) had to be shown to be consistent by fully implementing them, a task Alex delegated to Dave Musser. It would have been quite easy for the whole enterprise to spin out of control at this point, but again Alex and Meng met the challenge and produced a proposal that received final approval at the July 1994 ANSI/ISO committee meeting. (Additional details of this history can be found in an interview Alex gave in the March 1995 issue of Dr. Dobb's Journal.)

Spreading the Word

Subsequently, the Stepanov and Lee document 17 was incorporated into the ANSI/ISO C++ draft standard (1, parts of clauses 17 through 27). It also influenced other parts of the C++ Standard Library, such as the string facilities, and some of the previously adopted standards in those areas were revised accordingly.

In spite of STL's success with the committee, there remained the question of how STL would make its way into actual availability and use. With the STL requirements part of the publicly available draft standard, compiler vendors and independent software library vendors could of course develop their own implementations and market them as separate products or as selling points for their other wares. One of the first edition's authors, Atul Saini, was among the first to recognize the commercial potential and began exploring it as a line of business for his company, Modena Software Incorporated, even before STL had been fully accepted by the committee.

The prospects for early widespread dissemination of STL were considerably improved with Hewlett-Packard's decision to make its implementation freely available on the Internet in August 1994. This implementation, developed by Stepanov, Lee, and Musser during the standardization process, became the basis of all implementations offered by compiler and library vendors today.

Also in 1994, Dave Musser and Atul Saini developed the STL++ Manual, the first comprehensive user-level documentation of STL, but they soon recognized that an even more comprehensive treatment of STL was needed, one that would have better and more complete coverage of all aspects of the library. In an attempt to meet this goal, and with much encouragement and assistance from their editor, Mike Hendrickson, they wrote the first edition of this book.

In the second edition, the two original authors are joined by Gillmer J. Derge, President and CEO of the consulting firm Toltec Software Services, Inc. He has been developing applications with C++ for more than a decade, including seven years with General Electric Corporate R&D, where he received a Whitney Award for technical achievement.

Acknowledgments for the First Edition

We gratefully acknowledge the encouragement and assistance of many people. First and foremost, Alex Stepanov and Meng Lee offered continuous encouragement and were always available to help straighten out any misconceptions we had about the design of the library. Invaluable assistance with code development and testing was provided by several Modena staff members, including Atul Gupta, Kolachala Kalyan, and Narasimhan Rampalli. Several reviewers of earlier drafts gave us much valuable feedback and helped us find ways to present the most crucial ideas more clearly. They include Mike Ballantyne, Tom Cargill, Edgar Chrisostomo, Brian Kernighan, Scott Meyers, Larry Podmolik, Kathy Stark, Steve Vinoski, and John Vlissides. Others who also made valuable suggestions include Dan Benanav, Bob Cook, Bob Ingalls, Nathan Schimke, Kedar Tupil, and Rick Wilhelm. Finally, we thank the team at Addison-Wesley for their expert editorial and production assistance: Kim Dawley, Katie Duffy, Rosa Gonzalez, Mike Hendrickson, Simone Payment, Avanda Peters, John Wait, and Pamela Yee.

Acknowledgments for the Second Edition

For assistance with this edition, we wish first of all to thank the review- ers for pointing out errors in the discussion and examples and suggesting many other improvements in the presentation. The extensive comments of Max A. Lebow, Lawrence Rauchwerger, and Jan Christiaan van Winkel were especially helpful. We also thank Deborah Lafferty, our editor, and Julie DeBaggis, who served as editor during the early planning of the second edition. Several other members of the production and marketing teams at Addison-Wesley helped in many ways, including Jacquelyn Doucette, Chanda Leary- Coutu, Curt Johnson, Jennifer Lawinski, and Marty Rabinowitz.

D.R.M.
Loudonville, NY

G.J.D.
Cohoes, NY

A.S.
Los Gatos, CA

October 2000

Table of Contents

Foreword.


Foreword to the First Edition.


Preface.

I. TUTORIAL INTRODUCTION TO STL.

II. PUTTING IT TOGETHER: EXAMPLE PROGRAMS.

III. STL REFERENCE GUIDE.

Errata

Click below for Errata related to this title:
Errata