COMP2004
Programming Practice
2002 Summer School


Kevin Pulo
School of Information Technologies
University of Sydney


(page 1)


vector




(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


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




(page 5)


Using List




(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


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


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


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




(page 14)


set




(page 15)


multiset




(page 16)


map




(page 17)


multimap




(page 18)


Adapters




(page 19)


stack




(page 20)


queue




(page 21)


priority_queue




(page 22)


Overriding default containers


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




(page 24)


What is a Function Object?




(page 25)


Types of Function Objects




(page 26)


Types of Function Objects II




(page 27)


Strict Weak Ordering




(page 28)


Strict Weak Ordering Ex




(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





























(page 31)


STL Function Objects






























































































































































































































































































































































(page 32)