COMP2004
Programming Practice
2002 Summer School

Kevin Pulo
School of Information Technologies
University of Sydney

(page 1)

vector

• Simplest container, often most efficient
• Has a size and a capacity
• Insertion can cause reallocation
• Reallocation gets new storage memory
• Eg. when larger capacity needed
• Reallocation invalidates iterators
• Random Access Container
• Back Insertion Sequence

(page 2)

Bad Vector Code

void duplicate(vector &v) {
vector::const_iterator
b = v.begin(),
e = v.end();
for(; b != e; ++b)
v.push_back(*b);
}
• Not safe
• Reallocation may invalidate b and e
• Easily fixed in this case

(page 3)

Better Vector Code

• Use reserve() to allocate space
void duplicate(vector &v) {
v.reserve(v.size()*2);
vector::const_iterator
b = v.begin(),
e = v.end();
for(; b != e; ++b)
v.push_back(*b);
}

(page 4)

list

• A doubly linked list
• Reversible Container
• Front Insertion Sequence
• Back Insertion Sequence
• Insertion and splicing do not invalidate iterators
• Deletion only invalidates iterators at deleted element

(page 5)

Using List

• A list is preferred over a vector when
• Insertion from front/middle common
• Deletion at front/middle is common
• Random access is not required

(page 6)

List Example

#include
#include
#include
int main() {
list l;
string s;
while (cin >> s) l.push_front(s);
l.sort();
copy(l.begin(), l.end(),
ostream_iterator(cout, "\n"));
}

(page 7)

ostream_iterator

• Recall copy(II begin, II end, OI out)
• ostream_iterator is an output iterator for ostream objects
• Constructor:
template
ostream_iterator(ostream &os,
const char* sep = "");
• Creates an ostream_iterator object for outputting objects of type T to the ostream os separated by sep

(page 8)

Container output iterators

• What about output iterators which store items in a container?
list l;
vector v;
copy(l.begin(), l.end(), back_inserter(v));
• back_inserter(c) returns an iterator which does c.push_back()
• Requires Back Insertion Sequence
• Similarly front_inserter(c)
• Requires Front Insertion Sequence

(page 9)

istream_iterator

• What about istream input iterators?
• istream_iterator is an input iterator for istream objects
• Constructor:
template
istream_iterator(istream &is);
• Creates an istream_iterator object for inputting objects of type T from the istream is

(page 10)

istream_iterator example

int main() {
list l;
copy(istream_iterator(cin),
istream_iterator(),
back_inserter(l));
copy(l.begin(), l.end(),
ostream_iterator(cout, ", "));
cout << endl;
}
• Input: 2 63 42 1 8
• Output: 2, 63, 42, 1, 8

(page 11)

front_inserter example

int main() {
list l;
copy(istream_iterator(cin),
istream_iterator(),
front_inserter(l));
copy(l.begin(), l.end(),
ostream_iterator(cout, ", "));
cout << endl;
}
• Input: 2 63 42 1 8
• Output: 8, 1, 42, 63, 2

(page 12)

Another example

int main() {
copy(istream_iterator(cin),
istream_iterator(),
ostream_iterator(cout, "\n"));
}
• Outputs each word input on its own line

(page 13)

deque

• Double-ended queue
• Random Access Container
• Front Insertion Sequence
• Back Insertion Sequence
• Slower than vector
• Due to front insertion

(page 14)

set

• Sorted Associative Container
• Simple Associative Container
• Unique Associative Container
• Inserting does not invalidate iterators
• Deleting only invalidates iterators at deleted element

(page 15)

multiset

• Sorted Associative Container
• Simple Associative Container
• Multiple Associative Container
• Inserting does not invalidate iterators
• Deleting only invalidates iterators as deleted element

(page 16)

map

• Sorted Associative Container
• Pair Associative Container
• Unique Associative Container
• Inserting does not invalidate iterators
• Deleting only invalidates iterators at deleted element

(page 17)

multimap

• Sorted Associative Container
• Pair Associative Container
• Multiple Associative Container
• Inserting does not invalidate iterators
• Deleting only invalidates iterators at deleted element

(page 18)

Adapters

• Adapters are wrappers around a container
• Work with any container which meets requirements
• Provide more specific interfaces
• Always use them if you want only that interface
• Eg: allows them to be replaced with a faster implementation

(page 19)

stack

• Last In First Out (LIFO)
• Only insert, retrieve, delete top element
• Can use any back insertion sequence
• Defaults to using a deque
• top() returns top element
• push() insert element at top
• pop() removes top element

(page 20)

queue

• First In First Out (FIFO)
• Only add at back, retrieve from front
• Can use any front and back insertion sequence
• By default a deque is used
• front() returns front element
• push() adds element to back
• pop() removes front element

(page 21)

priority_queue

• Can only retrieve/delete top element
• Largest element always at top
• Use LessThan Comparable elements
• Use any Random Access Container
• Uses a vector by default
• top() returns top element
• push() inserts an element
• pop() removes top element

(page 22)

Overriding default containers

• Definition of queue class:
template >
class queue { ... };
• Thus these are equivalent:
• queue q;
• queue > q;
• And overriding deque is easy:
• queue > q;
• Similarly for stack, priority_queue

(page 23)

Function Objects

• Often used to supply a function to an algorithm
• Makes the algorithm more generic
• Sorting is the obvious example
• Specify the comparison operation
• The STL uses function objects a lot

(page 24)

What is a Function Object?

• Something which can be called
• ie. if foo(...) is valid then foo is a function object
• A function pointer is the simplest example
• Objects of classes can also be used
• operator() needs to be overloaded
• Using an object is more flexible
• It can maintain state
• ie. remember things, etc

(page 25)

Types of Function Objects

• Generator
• Called with no arguments
• Unary Function
• Called with one argument
• Unary Predicate
• A Unary function that returns a boolean

(page 26)

Types of Function Objects II

• Binary Function
• Called with two arguments
• Binary Predicate
• A Binary Function that returns a boolean

(page 27)

Strict Weak Ordering

• Binary Predicate
• ie. compares 2 objects, returns T/F
• f(x,x) is false
• f(x,y) implies !f(y,x)
• !f(x,y) and !f(y,x) implies x and y are equivalent (x == y)
• x and y equivalent and y and z equivalent, implies x and z equivalent
• x == y and y == z implies x == z

(page 28)

Strict Weak Ordering Ex

• Less-than binary predicate ( < ) defines a Strict Weak Ordering, since
• x < x is false
• x < y implies !(y < x)
• !(x < y) and !(y < x) implies x == y
• x == y and y == z implies x == z

(page 29)

Less-than implementation

template
struct less {
bool operator()(const T &a,
const T &b) {
return (a < b);
}
};
less comp;
int a, b;
if (comp(a, b))
cout << a << "<" << b << endl;

(page 30)

Random Number Generator

• Unary Function
• f(N) returns an integer in range [0,N)
• Every integer in [0,N) will appear an equal number of times
• The nrand() function is an example

(page 31)

STL Function Objects

• STL provides a lot of function objects
• #include to access them

• Binary functions: plus, minus, ...
• Binary predicates: logical_and, logical_or, less, greater, equal_to, ...
• Unary predicates: logical_not, ...
• Unary functions: negate, ...

(page 32)