CMSC202

Computer Science II

Lecture 21 -
Containers and Iterators (contd)

CMSC 202 Faculty

Based on slides by Chris Marron, Katie Gibson, and Walter Savitch

Last Class We Covered
• STL
• Standard Template Library
• Containers

• Iterators
• Purpose
• Manipulating

• Strings and Vectors

2
Any Questions from Last Time?
Review of Containers and Iterators
Containers
• A container is a holder object that stores a collection of other objects
(its elements). They are implemented as class templates, which allows
a great flexibility in the types supported as elements.

• The container manages the storage space for its elements and
provides member functions to access them, either directly or through
iterators (reference objects with similar properties to pointers).

5
From: http://www.cplusplus.com/reference/stl/
 Sequence Containers
• All sequential containers is that
Name Details the elements can be accessed
array Array class sequentially
vector Vector
• They reside in namespace std
deque Double ended queue
list List • Some only in C++ 11 (but not C+
forward_list Singly linked list (11) + 98)

6
From: http://www.cplusplus.com/reference/stl/
 Container Adaptors
• Container adaptors are not full
Name Details container classes, but classes
stack LIFO stack that provide a specific interface
queue FIFO queue relying on an object of one of
priority_queue Priority queue the container classes (such as
deque or list) to handle the
Priority queues are a elements.
type of container
adaptors, specifically
designed such that
its first element is
always the greatest
of the elements it
contains
7
From: http://www.cplusplus.com/reference/stl/
 Associative Containers
• An abstract data type composed
Name Details
of a collection of (key, value)
set Set
pairs
multiset Multiple-key Set • For sets and maps, each possible
map Map key appears at most once in the
Multimap Multiple-key Map collection

8
From: http://www.cplusplus.com/reference/stl/
STL Containers
• All containers support a few basic methods
• size()

• empty()

• clear()

• All containers are implemented as a class

9
Lists
STL Containers
• Lists
• Linked List, (not the “list” in Python)
• Sequential (elements in an order)
• Does not support random access
• Basic functions include:
• insert()
• push_back() / push_front()
• pop_back() / pop_front()
• erase()

11
Live Coding
Lec21–> list.cpp
Sets
STL Containers
• Sets
• Elements are sorted when added to the set
• Uses operator< by default
• Cannot change the value of an element once added
• No random access
• Basic functions include:
• insert()
• count()
• find()
• erase()

14
Set
• http://www.cplusplus.com/reference/set/set/

15
Set Example
int main ( )
{
set<int> iSet;
iSet.insert(4);
iSet.insert(12);
iSet.insert(7);

// this looping construct works for all containers

set<int>::const_iterator position;

for (position = iSet.begin(); position != iSet.end(); ++position)

{
cout << *position << endl;
}
return 0;
}

16
STL Containers
• Multisets
• Same as a set, but…
• Allow duplicate elements

• Elements are sorted when added to the set

• Uses operator< by default
• Cannot change the value of an element once added
• No random access
• Same basic functions as well

17
Live Coding
Lec21–> multiset.cpp
Pairs
STL Containers
• Pairs
• Connects two items into a single object
• (Sort of like a tuple in Python)
• Member variables:
• first
• second

• Pair containers are used by other containers

20
Pair
• http://www.cplusplus.com/reference/utility/pair/

21
Examples of Using Pair
• To combine an int and a string into a pair

pair<int, string> ex1( 5, "hello");

• You can then access the values in the pair using standard "dot"
notation

cout << ex1.second << endl; // "hello"

22
Examples of Using Pair
• A function template named make_pair() can be used to create
pair objects

pair<int, string> ex2 =

make_pair(7, "ciao");

• A pair can be made with any two pieces of information (doesn’t have
to be int and string)

23
Maps
STL Containers
• Maps
• Stores key/value pairs
• Sorts by key
• Key must be unique
• Key is not modifiable
• Value is modifiable

25
Map
• http://www.cplusplus.com/reference/map/map/

26
Map Example
int main ( ) {
// create an empty map using strings
// as keys and floats as values
map<string, float> stocks;

// insert some stock prices

stocks.insert( make_pair("IBM", 42.50));
stocks.insert( make_pair("XYZ", 2.50));
stocks.insert( make_pair("WX", 0.50));

// instantiate an iterator for the map

map<string, float>::iterator position;

// print all the stocks

for (position = stocks.begin(); position != stocks.end(); ++position)
cout << "( " << position->first << ", " << position->second << " )\n";

return 0;
} 27
STL Containers
• Multimaps
• Stores key/value pairs
• Sorts by key (allows duplicate keys)
• Key does not need to be unique
• Key is not modifiable
• Value is modifiable

28
Map and Multimap Functions
• Basic functions of Maps include:
• insert()
• count()
• find()
• erase()

29
Live Coding
Lec21–> multimap.cpp
Container Usage
 32
Created by David Moore and licensed CC BY-SA 3.0
 Announcements
• Prelab Quizzes (4 pts)
• Released every Friday by 10am on Blackboard
• Due every Monday by 10am on Blackboard
• Lab (6 pts)
• In Engineering building during scheduled time!
• Project 4
• Due on Thursday, November 14th at 8:59pm on GL
• Exam 3 Review
• On Wednesday, December 11th in ENGR 027 from 2-4pm
• Exam 3 (Final)
• In person on Friday, December 13th(6 – 8pm) in LH1 (Movie Theater) or MEYR 030
Next Time: Recursion 33