Thinking In C++. Volume 2: Practical Programming

// is only available as part of the SGI STL

// (Included with the g++ distribution)

//{-bor} You can add the header by hand

//{-msc} You can add the header by hand

//{-g++} You can add the header by hand

#include

#include

#include

#include

using namespace std;

int main(){

  hash_map hm;

  map m;

  clock_t ticks = clock();

  for(int i = 0; i < 100; i++)

    for(int j = 0; j < 1000; j++)

      m.insert(make_pair(j,j));

  cout << "map insertions: "

    << clock() - ticks << endl;

  ticks = clock();

  for(int i = 0; i < 100; i++)

    for(int j = 0; j < 1000; j++)

      hm.insert(make_pair(j,j));

  cout << "hash_map insertions: "

    << clock() - ticks << endl;

  ticks = clock();

  for(int i = 0; i < 100; i++)

    for(int j = 0; j < 1000; j++)

      m[j];

  cout << "map::operator[] lookups: "

    << clock() - ticks << endl;

  ticks = clock();

  for(int i = 0; i < 100; i++)

    for(int j = 0; j < 1000; j++)

      hm[j];

  cout << "hash_map::operator[] lookups: "

    << clock() - ticks << endl;

  ticks = clock();

  for(int i = 0; i < 100; i++)

    for(int j = 0; j < 1000; j++)

      m.find(j);

  cout << "map::find() lookups: "

    << clock() - ticks << endl;

  ticks = clock();

  for(int i = 0; i < 100; i++)

    for(int j = 0; j < 1000; j++)

      hm.find(j);

  cout << "hash_map::find() lookups: "

    << clock() - ticks << endl;

} ///:~

The performance test we ran showed a speed improvement of roughly 4:1 for the hash_map over the map in all operations (and as expected, find( ) is slightly faster than operator[ ] for lookups for both types of map). If a profiler shows a bottleneck in your map, consider a hash_map.

Non-STL containers

There are two "non-STL" containers in the standard library: bitset and valarray.[103] We say "non-STL" because neither of these containers fulfills all the requirements of STL containers. The bitset container, which we covered earlier in this chapter, packs bits into integers and does not allow direct addressing of its members. The valarray template class is a vector-like container that is optimized for efficient numeric computation. Neither container provides iterators. Although you can instantiate a valarray with nonnumeric types, it has mathematical functions that are intended to operate with numeric data, such as sin, cos, tan, and so on. Most of valarray’s functions and operators operate on a valarray as a whole, as the following example illustrates.

//: C07:Valarray1.cpp

//{-bor}

// Illustrates basic valarray functionality

#include

#include

using namespace std;

double f(double x) {

  return 2.0 * x - 1.0;

}

template

void print(const char* lbl, const valarray& a) {

  cout << lbl << ": ";

  for(size_t i = 0; i < a.size(); ++i)

    cout << a[i] << ' ';

  cout << endl;

}

int main() {

  double n[] = {1.0, 2.0, 3.0, 4.0};

  valarray v(n, sizeof n / sizeof n[0]);

  print("v", v);

  valarray sh(v.shift(1));

  print("shift 1", sh);

  valarray acc(v + sh);

  print("sum", acc);

  valarray trig(sin(v) + cos(acc));

  print("trig", trig);

  valarray p(pow(v, 3.0));

  print("3rd power", p);

  valarray app(v.apply(f));

  print("f(v)", app);

  valarray eq(v == app);

  print("v == app?", eq);

  double x = v.min();

  double y = v.max();

  double z = v.sum();

  cout << "x = " << x << ", y = " << y

    << ", z = " << z  << endl;

} ///:~

The valarray class provides a constructor that takes an array of the target type and the count of elements in the array to be used to initialize the new valarray. The shift( ) member function shifts each valarray element one position to the left (or to the right, if its argument is negative) and fills in holes with the default value for the type (zero in this case). There is also a cshift( ) member function that does a circular shift (or "rotate"). All mathematical operators and functions are overloaded to operate on valarrays, and binary operators require valarray arguments of the same type and size. The apply( ) member function, like the transform( ) algorithm, applies a function to each element, but the result is collected into a result valarray. The relational operators return suitably sized instances of valarray that indicate the result of element-by-element comparisons, such as with eq above. Most operations return a new result array, but a few, such as min( ), max( ), and sum( ), return a single scalar value for obvious reasons.

The most interesting thing you can do with valarrays is reference subsets of their elements, not only for extracting information, but for updating it. A subset of a valarray is called a slice, and certain operators use slices to do their work. The following sample program uses slices.

//: C07:Valarray2.cpp

// Illustrates slices and masks

//{-bor}

#include

#include

using namespace std;

template

void print(const char* lbl, const valarray& a) {

  cout << lbl << ": ";

  for(size_t i = 0; i < a.size(); ++i)

    cout << a[i] << ' ';

  cout << endl;

}

int main() {