CSCE 121 Chapter 21

Happy Thanksgiving!!!

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

STL Algorithms

Accumulate

A more generalized Sum:

template<class In, class T, class BinOp> T accumulate(In first, In last, T init, BinOp op) {
  while (first!=last) {
    init = op(init, *first);    // means “init op *first”
    ++first;
  }
  return init;
}

Usage: product

double product = accumulate(ld.begin(), ld.end(), 1.0, multiplies<double>());

Inner Product

Concept

$v_{1}=\left\{a,b,c,d,e\right\},\quad v_{2}=\left\{f,g,h,i,j\right\}$

inner_product(v₁, v₂) = af + bg + ch + di + ej

Generalized code to provide operations

template<class In, class In2, class T, class BinOp, class BinOp2> T inner_product(In first, In last, In2 first2, T init, BinOp op, BinOp2 op2) {
  while(first!=last) {
    init  = op(init, op2(*first, *first2));
    ++first;
    ++first2;
  }
  return init;
}

Map

FINALLY! A PHP-style array (Ruby-style Hash)

Stored as an ordered, balanced binary tree

balanced

same depth on each side of root node

ordered

stuff on left of root node are (alphabetically/sorted) before root node, stuff on right of root are sorted after root

Object Code

template<class Key, class Value> class map {
  // ...

  typedef pair<Key,Value> value_type;              // a map deals in (Key,Value) pairs
  typedef ??? iterator;                            // probably pointer to tree node
  typedef ??? const_iterator;

  iterator begin();                                // points to first element
  iterator end();                                  // points to one beyond the last element

  Value& operator[](const Key&);

  iterator find(const Key& k);                     // is there an entry for k?

  void erase(iterator p);                          // remove element pointed to by p
  pair<iterator, bool> insert(const value_type&);  // insert new pair before p

  // ...
};

Usage

int main() {
  map<string,int> words;        // keep (word,frequency) pairs
  string s;
  while (cin>>s) ++words[s];    // note: words subscripted by string; words[s] returns int&; int values initialized to 0
  typedef map<string,int>::const_iterator  Iter;
  for (Iter  p = words.begin(); p != words.end(); ++p)
    cout << p->first << ": " << p->second << "\n";
}

// Init stock map 'dow'

double alcoa_pice = dow["AAA"];
double boeing_price = dow["BO"];

if (dow.find("INTC") != dow.end())
  cout << "Intel is in the Dow"

// calculate Dow Jones index
<syntaxhighlight lang="cpp">double value_product(const pair<string, double>& a, const pair<string, double>& b) {
  return a.second * b.second
}

double dj_index = inner_product(
    dow.begin(), dow.end(),                             // all companies in index
    dow_weight.begin(),                                 // their weights
    0.0,                                                // initial value
    plus<double>(),                                     // add (as usual)
    value_product                                       // extract values and weights
  );                                                    // and multiply; then sum

In General...

STL Containers and Pseudocontainers

Sequence

vector, list, deque

Associative

map, set, multimap, multiset (multi- allows for duplicates)

Pseudocontainers

array, string, stack, queue, priority_queue

soon-to-be (C++0x)

unordered_map (hash table), unordered_set

STL-Style Algorithms

• Take 1+ sequences (usually pairs of iterators
• Take 1+ operations

Useful standard algorithms

r = find(b,e,v)

r points to first occurrence of v in [b,e)

r = find_if(b,e,p)

r points to first element in [b,e) so that p(x) is true

x = count(b,e,v)

x is number of occurrences of v in [b,e)

x = count_if(b,e,p)

x is number of elements in [b,e) that satisfy p(x)

sort(b,e)

sort [b,e) using <

sort(b,e,p)

sort [b,e) using p(x)

copy(b,e,b2)

copy [b,e) to [b2, b2+(e-b))

Important: doesn't check space

unique_copy(b,e,b2)

merge(b,e,b2,e2,r)

r = equal_range(b,e,v)

equal(b,e,b2)

Example: Quick Dictionary

Takes an input file and outputs an alphabetical, non-duplicated list of words separated by newlines ("\n"). This was our 3rd homework assignment, and it took many lines of code to do the same thing.

int main() {
  string from, to
  cin >> from >> to;
  ifstream is(from.c_str());
  ofstream os(to.c_str());

  istream_iterator<string> ii(is);
  istream_iterator<string> eos;
  ostream_iterator<string> oo(os, "\n");

  set<string> b(ii, eos);
  copy(b.begin(), b.end(), oo);
}