ECE 250 Algorithms and Data Structures
Data Structures and Containers
Douglas Wilhelm Harder
Department of Electrical and Computer Engineering
University of Waterloo
Waterloo, Ontario, Canada
Copyright © 2006-9 by Douglas Wilhelm Harder. All rights reserved.
Data Structures and Containers
Data and Collections
• In this topic, we will look objects and containers of
objects
– Operations on containers
– Operations on objects within the containers
– Types of containers:
• Object or associative containers
• Do we allow duplicate objects or require uniqueness?
– Introduction to the C++ Standard Template Library
2
Data Structures and Containers
Objects
• Data is information associated with an object
• This is generalized in the concept of an object with
– Member variables (instance variables, etc.)
– Member functions (behaviours, methods, etc.)
• This abstraction was introduced in ECE 150
• This course focuses on the efficient storage of objects
• The abstraction in C++ for an object which stores other
objects is a container
– The mechanism for storing objects is called a data structure
3
Data Structures and Containers
Data Structures and Containers
• In Laboratory 0, you looked at a simple container:
– A Box class
• Other simple data structures which may serve as
containers include:
– Arrays
– Linked lists
• In this class, we will focus more complex and more
efficient data structures
– If, by the end of this class, the first thing you think of for storing
objects is an array or linked list, the instructor has failed…
4
Data Structures and Containers
Containers
• Before we discuss specific container designs, we must
look at operations on containers
– What operations should be possible for containers?
– What can with do with objects stored?
– What operations may be appropriate for multiple containers?
5
Data Structures and Containers
Operations on Containers
• Operations on the containers may include the ability to:
– Create a container
– Destroy a container
– Make a copy of a container
– Split a container into two or more containers
– Take the union of two containers (merge)
– Determine the intersection of two containers
6
Data Structures and Containers
Operations on Stored Objects
• Given any container, we may wish to:
– Retrieve the number of objects in the container
• Determine if the container is empty
– Insert a new object
– Determine membership of an object
– Iterate through the objects within the container
– Modify an object in the container
– Remove an object from the container
• Remove all objects from the container
7
Data Structures and Containers
Other Operations
• These are basic operations...
• What about operations such as:
– Finding the “smallest” or “first” object in the container
– Partitioning the objects in the container
– Finding all objects with similar properties or characteristics
• There may be other relationships between the objects
we may need to exploit
• We will find data structures which allow us to implement
containers to optimize the necessary operations
8
Data Structures and Containers
Object/Associative Containers
• A container may simply store objects:
– Object containers
– E.g., a list of requests for web pages
• Alternatively, a container may store objects, but may also
associate that object with additional information
– Associative containers
– The object being stored is termed a key
– E.g., your UW Student ID Number is a key
• Associated with it are objects which record everything about your
time here at Waterloo
9
Data Structures and Containers
Unique or Duplicate Objects
• A container may require the objects to be unique
– UW Student ID Numbers
– UW User IDs
– Social Insurance Numbers
• A container may allow duplication of the objects being
stored
– A list of requests or attempts
• Unless otherwise stated, we will assume in this class
that all objects are unique
10
Data Structures and Containers
Sets/Multisets and Maps/Multimaps
• We will begin by introducing four containers from the C+
+ Standard Template Library (STL):
Unique Duplicate
Objects/Keys Objects/Keys
Object Container set<T> multiset<T>
Associative Container map<K, T> multimap<K, T>
11
Data Structures and Containers
The Set Container
// An example using the set<T> class
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> is;
set<int>::iterator itr;
for ( int i = 0; i < 100; ++i ) {
is.insert( i*i );
}
is.erase( 81 );
cout << "Size of ‘is’: " << is.size() << endl;
for ( itr = is.begin(); itr != is.end(); ++itr ) {
cout << *itr << ‘ ’;
}
cout << endl;
return 0;
}
12
Data Structures and Containers
The Set Container
• How could we store objects in a set?
– The set {a, b, c, d} could be represented by any of these arrays
or linked lists:
– Determining if e is stored any of these requires that all entries be
checked
– Inserting f into any of these requires that all entries/nodes be
checked
• We will see that there are many more efficient data
structures for storing unrelated objects
– Hash tables (around week 7)
13
Data Structures and Containers
Summary
• In this topic, we have begun to describe containers
– Operations on the containers
– Queries on the objects within the containers
• Different types of containers
– Object containers versus associative containers (keys)
– Unique or duplicate objects/keys
• A first look at the STL and sets
14
Data Structures and Containers
Usage Notes
• These slides are made publicly available on the web for anyone to use
• If you choose to use them, or a part thereof, for a course at another
institution, I ask only three things:
– that you inform me that you are using the slides,
– that you acknowledge my work, and
– that you alert me of any mistakes which I made or changes which you make, and
allow me the option of incorporating such changes (with an acknowledgment) in
my set of slides
Sincerely,
Douglas Wilhelm Harder, MMath
dwharder@alumni.uwaterloo.ca
15
