Advanced Programming II Class Notes

Lecture Notes for Advanced Programming II

27 March 2003 - Eliminating loops, special edition

Tableau Equivalence

Two tableaus are equal if
- they both have the same number of piles, and
- the ith pile in each tableau are the same.

Assuming pile equality, tableau equality has a straightforward implementation.

bool tableau::
operator == (const tableau & t) const {

  if (pile_cnt() != t.pile_cnt())
    return false;

  piles_citer
    i = piles.begin(),
    j = t.piles.begin();

  while (i != piles.end())
    if (*i++ != *j++)
      return false;

  return true;
  }

Eliminating the Loop

How can we replace the loop

while i != piles.end()
  if *i++ != *j++
    return false

with a generic algorithm?

This loop is tricky because it traverses two sequences, not one.
Has the STL let us down? Can we not replace this loop with a generic algorithm?

Generalized Numeric Algorithms

Generalized numeric algorithms compute values over data sequences.
- Compute the sum of values in a data sequence.
  accumulate()
- Compute the dot product of two data sequences.
  inner_product()
- Compute the prefix sums of a sequence.
  partial_sum()
- Compute the differences between adjacent values in a sequence.
  adjacent_difference()
These are defined in the <numeric> header.
Notice the std::inner_product() algorithm works over two data sequences.

The Inner Product

The inner product (also known as the dot product) is a mathematical quantity defined over n-coordinate vectors.
The inner product of two vectors is the product of the sum corresponding coordinates in each vector.
The std::inner_product() generalized numeric algorithm computes the inner product over two data sequence.
- That looks promising.

`std::inner_product()`

The std::inner_product() accepts two data sequences and returns the inner product of the two sequences.
```
double ip = 
  std::inner_product(
    v.begin(), v.end(),
    u.begin(), 
    i);
```
- i is the initial value of the inner product.
std::inner_product() is generalized because addition and multiplication can be replaced by other binary operations.
- Other binary operators such as equality == and logical and &&.

Tableau Equality Revisited

Two tableaus T₁ and T₂ are equal if they both have the same number of piles and
- T₁'s first pile is equal to T₂'s first pile and
- T₁'s second pile is equal to T₂'s second pile and
- T₁'s third pile is equal to T₂'s third pile and
- and so on.
In other words, pile equality is the inner product of two tableaus with
- Addition replaced by equality.
- Multiplication replaced by logical and.

The Loop Banished

The loop

while i != piles.end()
  if *i++ != *j++
    return false

return true;

can be replaced with a redefined version of std::inner_product() to give

bool tableau::
operator == (const tableau & t) const {

  return
    (pile_cnt() == t.pile_cnt()) and
    std::inner_product(
      piles.begin(), piles.end(),
      t.piles.begin(),
      true,
      std::logical_and<bool>(),
      std::equal_to<pile>());
  }

Discussion

Is this really a win?
Yes:
- No more loops, no more explicit iterators.
No:
- std::inner_product() always takes O(n) time.
  - The while loop could end early (but has O(n) worst-case behavior).
- All that code.
  - Yes, but - hey - it's C++.
- People may find it too weird.
  - Hang around with smarter people.
- std::equal() does the job with less fuss.
```
return
  (pile_cnt() == t.pile_cnt()) and
  std::equal(piles.begin(), piles.end(),
             t.piles.begin())
```

Points to Remember

Replace loops with generic algorithms.
Make your meaning as clear as you possibly can.
- Favor std::equal() over std::inner_product().
Know what the STL can do for you.
- Know what you can do the the STL.
Don't forget the generalized numeric algorithms.
- They're obscure but powerful.
The std::inner_product() generalized numeric algorithm can operate over two source data sequences.
Use the STL-defined operator functors to avoid having to create your own operator functions.

This page last modified on 3 April 2003.