1 of 50

Data Structures Using C++ 2E

Chapter 4

Standard Template Library (STL) I

2 of 50

Objectives

  • Learn about the Standard Template Library (STL)
  • Become familiar with the three basic components of the STL: containers, iterators, and algorithms
  • Explore how vector and deque containers are used to manipulate data in a program
  • Discover the use of iterators

Data Structures Using C++ 2E

2

3 of 50

Components of the STL

  • Program’s main objective is to manipulate data and generate results
    • Requires ability to store data, access data, and manipulate data
  • STL components
    • Containers
    • Iterators: step through container elements
    • Algorithms: manipulate data
  • Containers and iterators
    • Class templates

Data Structures Using C++ 2E

3

4 of 50

Container Types

  • STL containers categories
    • Sequence containers (sequential containers)
    • Associative containers
    • Container adapters

​

Data Structures Using C++ 2E

4

5 of 50

Sequence Containers

  • Every object has a specific position
  • Predefined sequence containers
    • vector , deque , list
  • Sequence container vector
    • Logically: same as arrays
    • Processed like arrays
  • All containers
    • Use same names for common operations
    • Have specific operations

Data Structures Using C++ 2E

5

6 of 50

Sequence Container: vector

  • Vector container
    • Stores, manages objects in a dynamic array
    • Elements accessed randomly
    • Time-consuming item insertion: middle, beginning
    • Fast item insertion: end
  • Class implementing vector container
    • vector
  • Header file containing the class vector
    • vector

Data Structures Using C++ 2E

6

7 of 50

Sequence Container: vector (cont’d.)

  • Using a vector container in a program requires the following statement:
    • #include <vector>
  • Defining a vector container object
    • Specify object type
    • Example: vector<int> intlist;
    • Example: vector<string> stringList;

Data Structures Using C++ 2E

7

8 of 50

Sequence Container: vector (cont’d.)

  • Declaring vector objects

Data Structures Using C++ 2E

8

TABLE 4-1 Various ways to declare and initialize

a vector container

9 of 50

Sequence Container: vector (cont’d.)

  • Manipulating data stored in a vector sequence container
    • Basic operations
      • Item insertion
      • Item description
      • Stepping through the elements of a vector array

Data Structures Using C++ 2E

9

10 of 50

Sequence Container: vector (cont’d.)

Data Structures Using C++ 2E

10

TABLE 4-2 Operations to access the elements of a vector container

11 of 50

Sequence Container: vector (cont’d.)

  • class vector
    • Provides various operations to process vector container elements
    • Iterator
      • Argument position in STL terminology

Data Structures Using C++ 2E

11

12 of 50

Sequence Container: vector (cont’d.)

Data Structures Using C++ 2E

12

TABLE 4-3 Various operations on a vector container

13 of 50

Sequence Container: vector (cont’d.)

Data Structures Using C++ 2E

13

TABLE 4-3 Various operations on a vector container (cont’d.)

14 of 50

Sequence Container: vector (cont’d.)

  • Function push_back
    • Adds element to end of container
    • Used when declaring vector container
      • Specific size unknown

Data Structures Using C++ 2E

14

15 of 50

Declaring an Iterator to a Vector Container

  • Process vector container like an array
    • Using array subscripting operator
  • Process vector container elements
    • Using an iterator
  • class vector: function insert
    • Insert element at a specific vector container position
    • Uses an iterator
  • class vector: function erase
    • Remove element
      • Uses an iterator

Data Structures Using C++ 2E

15

16 of 50

Declaring an Iterator to a Vector Container (cont’d.)

  • class vector contains typedef iterator
    • Declared as a public member
    • Vector container iterator
      • Declared using typedef iterator
    • Example

vector<int>::iterator intVecIter;

Data Structures Using C++ 2E

16

17 of 50

Declaring an Iterator to a Vector Container (cont’d.)

  • Requirements for using typedef iterator
    • Container name (vector)
    • Container element type
    • Scope resolution operator
  • ++intVecIter
    • Advances iterator intVecIter to next element into the container
  • *intVecIter
    • Returns element at current iterator position

Data Structures Using C++ 2E

17

18 of 50

Declaring an Iterator to a Vector Container (cont’d.)

  • Using an iterator into a vector container
    • Manipulating element type to be int

Data Structures Using C++ 2E

18

19 of 50

Containers and the Functions begin and end

  • begin
    • Returns position of the first element into the container
  • end
    • Returns position of the last element into the container
  • Functions have no parameters
  • class vector
    • Contains member functions used to find number of elements currently in the container

Data Structures Using C++ 2E

19

20 of 50

Containers and the Functions begin and end (cont’d.)

Data Structures Using C++ 2E

20

TABLE 4-4 Functions to determine the size of a vector container

21 of 50

Member Functions Common to All Containers

  • Examples
    • Default constructor
    • Several constructors with parameters
    • Destructor
      • Function inserting an element into a container
  • Class encapsulates data, operations on that data
    • Into a single unit
  • Every container is a class
    • Several operations directly defined for a container
    • Provided as part of class definition

Data Structures Using C++ 2E

21

22 of 50

Data Structures Using C++ 2E

22

TABLE 4-5 Member functions common to all containers

23 of 50

Data Structures Using C++ 2E

23

TABLE 4-5 Member functions common to all containers (cont’d.)

24 of 50

Member Functions Common to Sequence Containers

Data Structures Using C++ 2E

24

TABLE 4-6 Member functions common to all sequence containers

25 of 50

The copy Algorithm

  • Provides convenient way to output container elements
  • Generic STL algorithm
    • Usable with any container type and arrays
  • Does more than output container elements
    • Allows copying of elements from one place to another
  • Function template copy definition
    • Contained in header file algorithm

​

Data Structures Using C++ 2E

25

26 of 50

ostream Iterator and Function copy

  • Output container contents
    • Use a for loop and the function begin
      • Use the function end to set limit
    • Use Function copy
      • ostream iterator type specifies destination
  • Creating an iterator of type ostream
    • Specify element type iterator will output
  • Function copy
    • Can output container elements using ostream iterator
    • Directly specify ostream iterator in function copy

Data Structures Using C++ 2E

26

27 of 50

Sequence Container: deque

  • Deque: double-ended queue
  • Implemented as dynamic arrays
    • Can expand in either direction
  • Class name defining deque container
    • deque
  • Header file deque contains
    • Definition of the class deque
    • Functions to implement various operations on a deque object
  • Class deque contains several constructors

Data Structures Using C++ 2E

27

28 of 50

Sequence Container: deque (cont’d.)

Data Structures Using C++ 2E

28

TABLE 4-7 Various ways to declare a deque object

29 of 50

Sequence Container: deque (cont’d.)

Data Structures Using C++ 2E

29

TABLE 4-8 Various operations that can be performed

on a deque object

30 of 50

Iterators

  • Work like pointers
  • Point to elements of a container (sequence or associative)
  • Allow successive access to each container element
  • Two most common operations on iterators
    • ++ (increment operator)
    • * (dereferencing operator)
  • Examples

++cntItr;

*cntItr;

Data Structures Using C++ 2E

30

31 of 50

Types of Iterators

  • Input iterators
  • Output iterators
  • Forward iterators
  • Bidirectional iterators
  • Random access iterators

Data Structures Using C++ 2E

31

32 of 50

Input Iterators

  • Read access
    • Step forward element-by-element
    • Return values element-by-element
  • Provided for reading data from an input stream

Data Structures Using C++ 2E

32

33 of 50

Input Iterators (cont’d.)

Data Structures Using C++ 2E

33

TABLE 4-9 Operations on an input iterator

34 of 50

Output Iterators

  • Write access
    • Step forward element-by-element
  • Used for writing data to an output stream
  • Cannot be used to iterate over a range twice

Data Structures Using C++ 2E

34

35 of 50

Output Iterators (cont’d.)

Data Structures Using C++ 2E

35

TABLE 4-10 Operations on an output iterator

36 of 50

Forward Iterators

  • Combination of
    • All of input iterators functionality and almost all output iterators functionality
  • Can refer to same element in same collection
    • Can process same element more than once

Data Structures Using C++ 2E

36

37 of 50

Forward Iterators (cont’d.)

Data Structures Using C++ 2E

37

TABLE 4-11 Operations on a forward iterator

38 of 50

Bidirectional Iterators

  • Forward iterators that can also iterate backward over the elements
  • Operations defined for forward iterators applicable to bidirectional Iterators
  • To step backward
    • Decrement operations also defined for biDirectionalIterator
  • Can be used only with containers of type:
    • vector, deque, list, set, multiset, map, and multimap

Data Structures Using C++ 2E

38

39 of 50

Bidirectional Iterators (cont’d.)

Data Structures Using C++ 2E

39

TABLE 4-12 Additional operations on a bidirectional iterator

40 of 50

Random Access Iterators

  • Bidirectional iterators that can randomly process container elements
  • Can be used with containers of type:
    • vector , deque , string, and arrays
  • Operations defined for bidirectional iterators applicable to random access iterators

Data Structures Using C++ 2E

40

41 of 50

Random Access Iterators (cont’d.)

Data Structures Using C++ 2E

41

TABLE 4-13 Additional operations on a random access iterator

42 of 50

Iterators (cont’d.)

  • typedef iterator
    • Every container (sequence or associative) contains a typedef iterator
    • Iterator into a container declared using typedef iterator
    • Must use appropriate container name, container element type, scope resolution operator

Data Structures Using C++ 2E

42

43 of 50

Iterators (cont’d.)

  • typedef const_iterator
    • Modify container elements using an iterator into a container and dereferencing operator (*)
    • Prevents iterator from modifying elements of container declared as constant
    • Every container contains typedef const_iterator
    • Read-only iterator

Data Structures Using C++ 2E

43

44 of 50

Iterators (cont’d.)

  • typedef reverse_iterator
    • Every container contains typedef reverse_iterator
    • Used to iterate through the elements of a container in reverse

Data Structures Using C++ 2E

44

45 of 50

Iterators (cont’d.)

  • typedef const_reverse iterator
    • Read-only iterator
    • Used to iterate through elements of a container in reverse
    • Required if
      • Container declared as const
      • Need to iterate through the elements of the container in reverse

Data Structures Using C++ 2E

45

46 of 50

Iterators (cont’d.)

Data Structures Using C++ 2E

46

TABLE 4-14 Various typedefs common to all containers

47 of 50

Stream Iterators

  • istream_iterator
    • Used to input data into a program from an input stream
    • class istream_iterator
      • Contains definition of an input stream iterator
    • General syntax to use an istream iterator

​

Data Structures Using C++ 2E

47

48 of 50

Stream Iterators (cont’d.)

  • ostream iterators
    • Used to output data from a program into an output stream
    • class ostream_iterator
      • Contains definition of an output stream iterator
    • General syntax to use an ostream iterator

Data Structures Using C++ 2E

48

49 of 50

Summary

  • STL
    • Provides class templates
      • Process lists, stacks, and queues
    • Three main components
      • Containers, iterators, and algorithms
    • STL containers: class templates
  • Iterators
    • Step through the elements of a container
  • Algorithms
    • Manipulate elements in a container

Data Structures Using C++ 2E

49

50 of 50

Summary (cont’d.)

  • Main categories of containers
    • Sequence containers, associative containers, container adapters
  • Three predefined sequence containers
    • vector, deque, and list
  • copy algorithm
    • Copies elements in a given range to another place
  • Function copy, using an ostream iterator
    • Can output the elements of a container
  • Five categories of iterators: input, output, forward, bidirectional, random access iterator

Data Structures Using C++ 2E

50