CSCE 121 Chapter 20

« previous | Monday, November 15, 2010 | next »

Standard Template Library

Common Tasks in Programming:

• Collect Data
• Store Date in Containers
• Delete data'

We want uniform access to a huge variety of data

Iterators (Sum)

Looping over a data list

Example:

double sum(double array[], int sz) {
  double s = 0;
  for (int i = 0; i < sz; ++i) s = s + array[i];
  return s;
}

struct Node { Node* next; int data; };  // linked list

int sum(Node* first) {
  int s = 0;
  while (first) {
    s += first->data;
    first = first->next;
  }
  return s;
}

Basically,

1. Get first item
2. While not at end, add item to sum
3. get next item

STL-style

template<class Iter, class T>  // Iter should be Input_iterator; T should be something we can + and =

T sum(Iter first, Iter last, T s) {  // Think of 'Iter' as a generalized pointer to a T
  while (first != last) {
    s = s + *first;
    ++first;
    return s;
  }
}

float a[] = { 1,2,3,4,5,6,7,8,9 };
double d = 0;
d = sum(a, a+sizeof(a)/sizeof(*a), d);

Algorithms manipulate data (sort, find, search, copy, etc.)

Iterators define how algorithms access containers

Containers store data (vector, list, map, hash_map, etc.); must provide their own iterators

Sequence

Defined by two iterators: begin ("points to" first element) and end ("points to" 1 past last element)

Iterators must support the "iterator operators": ++ (next element), * (get value), == (equal to ...)

find(): The simplest Algorithm

template<class In, class T> In find(In first, In last, const T& val) {
  while (first != last && *first != val) ++ first;
  return first;
}

// usage:
vector<int> v;
// fill v
vector<int>::iterator p = find(v.begin(), v.end(), x);  // iterator class inside vector class
if (p != v.end()) { /* we found x */ }

list<string> v;
// fill v
list<string>::iterator p = find(v.begin(), v.end(), x);
if (p != v.end()) { /* we found x */ }

// generic:
container v;
// fill v
container::iterator p = find(v.begin(), v.end(), x);
if (p != v.end()) { /* we found x */ }

Iterators

"points to" (refers to, denotes, etc.) an element of a sequence

Simple Algorithm: find_if()

find first element to match a criterion or predicate

template<class In, class Pred> In find_if(In first, In last, Pred pred) {
  while (first != last && !pred(*first)) ++ first) ++first
  return first;
}

vector<int> v;
// fill v
vector<int>::iterator p = find_if(v.begin(), v.end(), Odd());

Wednesday, November 17, 2010

Predicates

Two ways to do this:

bool odd(int i) { return i%2; }   // explicit function

// OR
struct Odd {   // function object
  bool operator()(int i) const { return i%2; }
};

Benefit of using function object over explicit object:

template<class T> struct Less_than {
  T val;   // value to compare with
  Less_than(T x) : val(x) {}
  bool operator()(const T& x) const { return x < val; }
};

p = find_if(v.begin(), v.end(), Less_than(43));

// find_if calls !Less_than(*first)

vector<int>::iterator find_if(vector<int>::iterator first, vector<int>::iterator last, Less_than pred) {
  while (first != last && !pred(*first)) ++ first) ++first
  return first;
}

We can instantiate objects and overload the parentheses operator to run a "testing" function

We can pass several methods of sorting:

struct Record {
  string name;
  string addr;
  Record(string n, string a) : name(n), addr(a) {}
}

struct Cmp_by_name {
  bool operator()(const Record& a, const Record& b) const { return a.name < b.name; }
}

struct Cmp_by_addr {
  bool operator()(const Record& a, const Record& b) const { return 0 < strncmp(a.addr, b.addr, 24); }
  // strncmp() compares two strings to a certain length (3rd parameter)
}

vector<Record> vr;
// ...
sort(vr.begin(), vr.end(), Cmp_by_name());
sort(vr.begin(), vr.end(), Cmp_by_addr());

Back to vector

template<class T> class vector {
  T* elements;
  // ...
  typedef ??? iterator;   // could be range-checked object, but normally a pointer to type T
  typedef ??? const_iterator;

  iterator begin();       // points to first element
  const_iterator begin() const;
  iterator end();         // points to one past last element
  const_iterator end() const;

  iterator erase(iterator p);               // remove element pointed to by p
  iterator insert(iterator p, const T& v);  // insert new element v before p
  // ...
}

Monday, November 22, 2010

list

template<class T> class list {
  Link* elements;
  // ... same code ...
}

Traversing containers

for (int i=0; i<v.size(); ++i) { /* ... */ }                            // only for vector; sometimes complains
for (vector<int>::size_type i=0; i<v.size(); ++i) { /* ... */ }         // longer, but always correct for vectors
for (vector<int>::iterator i=v.begin(); p!=v.end(); ++p) { /* ... */ }  // always correct, even for lists and other containers