Transcript Overview of Containers

Data Structures: CSCI 362 – Overview of STL Container Classes
Overview of Containers

Standard Template Language (STL) organizes its classes into 3 categories

Sequence Containers
 Arrays and Vectors (provides index access to data)
 List/ sequence
 Deque (can move either end, but not middle)

Adapter Containers
 Stacks (last in, first out)
 Queue (first in, first out)
 Priority Queue (deletion returns the largest/smallest value

Associative Containers
 Set and Multiset/ bag (elements are the information – ordering is by content)
 Map/ Multimap (key-data relationship; associative pairs)

All the container classes are templated and what the container does and
how it works is independent of elements it contains
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
What are Containers?

A Container is a data structure whose main purpose is to store and retrieve
a large number of values

Containers are abstract data types (ADTs) that hold values. They don't
change the content – only hold it so that it can be retrieved later.

These data structure permits storage and retrieval of data items
independent of content. The two fundamental operations of any container
are:
 Put(C,x): Insert a new data item x into the container C.
 Get(C): Retrieve the next item from the container C.
Different types of containers support different retrieval orders, based on insertion
order or position.

Items in Containers are referred to by special objects called: iterators.
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
What are Containers?

The STL consists of 10 container classes categorized according to the
ordering of the elements and the different types of operations that access
the data
 Sequence Containers: store data by position in linear order, 1st, 2nd, 3rd, etc.
 Associative Containers: store elements by key e.g. name, ssn, part numbers
etc. A program accesses an element in an associative container by its key,
which may bear no relationship to the location of the element in the container
 Adaptor Containers: contain other containers as their underlying storage
structure.
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Containers
Sequence Containers
Adapter Containers
Associative Containers
Vector
Stack
Set, Multiset
Deque
Queue
Map, Mutltimap
List
Priority Queue
Trees
Hash
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Sequence Containers – Vector

We talked about this already??

A vector is a generalized array that
stores a collection of elements of the
same data type

Similar to an array – a vector allows
access to its elements by using an
index in the range from 0 to n-1, where
n is the size of the vector

Unlike an array – a vector has
operations that allow collection of the
elements to grow dynamically at the
rear of the sequence to meet the
runtime needs of an application

vector v (with 5 elements)
7
4 9
3
1
v.resize (8); (grow to 8 elements)
7
4
9
3
1
0
0
0
v.resize (3); (shrink to 3 elements)
7
4
9
What is the disadvantage of insertion
or deletion within the interior of the
sequence??
Allows direct access to its elements
through the index
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Sequence Containers - Lists


A list is a data structure that stores elements by position
Each item in the list has both a value and a memory address (pointer) that identifies
the next item in the sequence
Value 1
Pointer to V2

Value n
Disadvantage: unlike a vector, a list is not a direct-access structure


Value 2
Pointer to V3
In order to access a specific data value in the list, it is necessary to search from position 1
and follow the pointers from element to element until the data value is located
Advantage: unlike a vector, a list is able to add a remove items efficiently at any
position in the sequence

Insertion requires 2 updates – ideal for applications that require sequential access to data
while also requiring frequent insertion and deletion of elements
3
front
Dr. Nazli Mollah
Inserting
Before
into a List ContainerAfter
6
3
12
4
front
12

6
4
lecture notes 15
adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Associative Containers – Stacks & Queues

Associative containers store elements by key – in what application is this useful??

Ex: name, social security number, or part number.

A program accesses an element in an associative container by its key, which may
bear no relationship to the location of the element in the container.

Containers are typically most useful when they will contain only a limited number of
items and when the retrieval order is predefined or irrelevant. The most popular type
of containers are:

Stacks: Supports retrieval in last in, first out order (LIFO). Stacks are simple to
implement, and very efficient. Indeed, stacks are probably the right container to use
when the retrieval order doesn't matter at all, as when processing batch jobs. The put
and get operations for stacks are usually called push and pop.

Queues: Supports retrieval in first in, first out order (FIFO). FIFO may seem the
fairest way to control waiting times. However, for many applications, data items have
infinite patience. Queues are trickier to implement than stacks and are appropriate
only for applications (like certain simulations) where the order is important. The put
and get operations for queues are usually called enqueue and dequeue.

Stacks ad Queues cab ve implemented using either arrays or linked lists
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Associative Containers – Stacks & Queues

Both stacks and queues are storage containers that restrict how elements
enter and leave a sequence
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Stack Containers
A stack allows access at only one end of the sequence, called the top
C
C
A
Push A
Dr. Nazli Mollah
top
B
A
Push B
(a)
top
top
Push C
B
A
B
A
Pop C
B
top
A
top
Pop B
(b)
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Queue Containers
A queue is a container that allows access only at the
front and rear of the sequence.
A
B
C
Insert
Dr. Nazli Mollah
B
D
E
A
rear
front
C
D
Delete
lecture notes adapted from
Data Structures with C++ using STL
E
Data Structures: CSCI 362 – Overview of STL Container Classes
Priority Queue Containers
A priority queue is a storage structure that has restricted
access operations similar to a stack or queue.
Elements can enter the priority queue in any order. Once
in the container, a delete operation removes the largest
(or smallest) value.
Value = 8
18
13
3
15
27
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Associative Containers – Maps/ Multimaps
A set is a collection of unique values, called keys or set members.
Set A
5
1
3
27
Dr. Nazli Mollah
Set B
15
Buick
BMW
Ford
Jaguar
Honda
Jeep
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Associative Containers – Sets/ Multisets
A map is a storage structure that implements a key-value relationship.
Index
Part#
Price
A29-468
D7B-916
4.95
M irage
D7B-916
W91-A83
12.50
Calloway
W91-A83
A29-468
8.75
M artin
Dr. Nazli Mollah
Vendor
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Stacks





Further Stack Analogies
Pushing/ Popping a Stack
Class Stack
Mutlibase
Uncoupling Stack
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Stacks

A sequence of items which are accessible only at the top
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Stack - LIFO

Since pop removes the item last pushed into the stack – it is a Last In First out
LIFO ordering container
C
B
B
B
A
A
A
A
A
A
Push A
Push B
Push C
Pop C
Pop B
Push D
Dr. Nazli Mollah
D
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
CLASS Stack
CLASS stack
stack();
Create an empty stack
CLASS stack
Constructor
<stack>
Operations
<stack>
bool empty(); const
Check whether the stack is empty. Return true if it is
empty and false otherwise.
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
CLASS Stack
CLASS stack
<stack>
Operations
void pop();
Remove the item from the top of the stack.
Precondition:
The stack is not empty.
Postcondition: Either the stack is empty or
the stack has a new topmost
item from a previous push.
void push(const T& item);
Insert the argument item at the top of the stack.
Postcondition: The stack has a new item at
the top.
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
CLASS Stack
CLASS stack
Operations
<stack>
int size() const;
Return the number of items on the stack.
T& top() const;
Return a reference to the value of the item at the
top of the stack.
Precondition: The stack is not empty.
const T& top() const;
Constant version of top().
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Using a Stack to Create a Hex Number
A
'F'
F
431 % 16 = 15
431 / 16 = 26
1
1
'1'
'1'
A
A
'A'
'A'
'A'
'F'
F
'F'
F
F
'F'
26 % 16 = 10
26 / 16 = 1
1 % 16 = 1
1 / 16 = 0
A'A'
F
'F'
Pop '1'
numStr = "1"
Push Digit Characters
F
'F'
Pop 'A'
Pop 'F'
numStr = "1A" numStr = "1AF"
Pop Digit Characters
Refer to Multi-base program 7-1, page 334
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Uncoupling Stack Elements
A
B
Train Before Uncoupling E
E
C
D
Refer to code on page 337 using “target”
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Uncoupling Stack Elements
A
Uncouple E. Move to side track
B
C
D
E
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Uncoupling Stack Elements
Uncouple D. Move to side track
A
B
C
D
E
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Uncoupling Stack Elements
Uncouple C Move aside
A
B
C
D
E
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Uncoupling Stack Elements
Attach D to end of train
A
B
D
C
E
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Uncoupling Stack Elements
A
Dr. Nazli Mollah
Attach E to end of train
B
D
E
C
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Uncoupling using “target”
pop
3
target
e
1
d
2
2
push
c
b
a
stack s
Dr. Nazli Mollah
pop
d
1
d
e
tmpStk
e
b
a
stack s
Refer to code on page 337 using
“target”
lecture
notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Arguments
int n
Return Address
RetLoc or RetLoc2
Activation Record
System Stack
In main():
call fact(4)
In fact(4):
call fact(3)
Dr. Nazli Mollah
Argument
4
Return
RetLoc1
Argument
3
Return
RetLoc2
Argument
4
Return
RetLoc1
lecture notes adapted from
Data Structures with C++ using STL
Structures: CSCI 362 – Overview of STL Container Classes
RPN (Reverse Data
Polish
Notation) expression 2 3 +
Scan of Expression and Action Current operandStack
1. Identify 2 as an operand.
Push integer 2 on the stack.
2
2. Identify 3 as an operand.
Push integer 3 on the stack.
3
3. Identify + as an operator
Begin the process of evaluating +.
3
2
2
4. getOperands() pops stack
twice and assigns 3 to
right and 2 to left.
operandStack empty
5. compute() evaluates left + right
and returns the value 5. Return
value is pushed on the stack.
29Dr. Nazli Mollah
Main Index
Contents
5
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Infix Expression Rules
The figure below gives input precedence, stack precedence, and
rank used for the operators +, -, *, /, %, and ^, along with the
parentheses. Except for the exponential operator ^, the other
binary operators are left-associative and have equal input and
stack precedence.
Precedence
Symbol
Input
precedence
+ * / %
^
(
)
1
2
4
5
0
30Dr. Nazli Mollah
Stack
precedence
1
2
3
-1
0
Main Index
Contents
Rank
-1
-1
-1
0
0
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Summary Slide 1
§- Stack
- Storage Structure with insert (push) and erase (pop)
operations occur at one end, called the top of the
stack.
- The last element in is the first element out of the
stack, so a stack is a LIFO structure.
31Dr. Nazli Mollah
Main Index
Contents
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Summary Slide 2
§- Recursion
- The system maintains a stack of activation records
that specify:
1) the function arguments
2) the local variables/objects
3) the return address
- The system pushes an activation record when
calling a function and pops it when returning.
32Dr. Nazli Mollah
Main Index
Contents
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Summary Slide 3
§- Postfix/RPN Expression Notation
- places the operator after its operands
- easy to evaluate using a single stack to hold
operands.
- The rules:
1) Immediately push an operand onto the stack.
2) For a binary operator, pop the stack twice, perform the
operation, and push the result onto the stack.
3)
At the end a single value remains on the stack. This is
the value of the expression.
33Dr. Nazli Mollah
Main Index
Contents
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Overview of STL Container Classes
Summary Slide 4
§- Infix notation
- A binary operator appears between its operands.
- More complex than postfix, because it requires the
use of operator precedence and parentheses.
- In addition, some operators are left-associative, and
a few are right-associative.
34Dr. Nazli Mollah
Main Index
Contents
lecture notes adapted from
Data Structures with C++ using STL