Thinking In C++. Volume 2: Practical Programming

vector

The vector container is a specialization of the vector template. A normal bool variable requires at least one byte, but since a bool only has two states, the ideal implementation of vector is such that each bool value only requires one bit. This means the iterator must be specially defined and cannot be a pointer to bool.

The bit-manipulation functions for vector are much more limited than those of bitset. The only member function that was added to those already in vector is flip( ), to invert all the bits; there is no set( ) or reset( ) as in bitset. When you use operator[ ], you get back an object of type vector::reference, which also has a flip( ) to invert that individual bit.

//: C07:VectorOfBool.cpp

// Demonstrate the vector specialization

#include

#include

#include

#include

#include

#include

using namespace std;

int main() {

  vector vb(10, true);

  vector::iterator it;

  for(it = vb.begin(); it != vb.end(); it++)

    cout << *it;

  cout << endl;

  vb.push_back(false);

  ostream_iterator out(cout, "");

  copy(vb.begin(), vb.end(), out);

  cout << endl;

  bool ab[] = { true, false, false, true, true,

    true, true, false, false, true };

  // There's a similar constructor:

  vb.assign(ab, ab + sizeof(ab)/sizeof(bool));

  copy(vb.begin(), vb.end(), out);

  cout << endl;

  vb.flip(); // Flip all bits

  copy(vb.begin(), vb.end(), out);

  cout << endl;

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

    vb[i] = 0; // (Equivalent to "false")

  vb[4] = true;

  vb[5] = 1;

  vb[7].flip(); // Invert one bit

  copy(vb.begin(), vb.end(), out);

  cout << endl;

  // Convert to a bitset:

  ostringstream os;

  copy(vb.begin(), vb.end(),

    ostream_iterator(os, ""));

  bitset<10> bs(os.str());

  cout << "Bitset:\n" << bs << endl;

} ///:~

The last part of this example takes a vector and converts it to a bitset by first turning it into a string of ones and zeros. Of course, you must know the size of the bitset at compile time. You can see that this conversion is not the kind of operation you’ll want to do on a regular basis.

The vector specialization is a "crippled" STL container in the sense that certain guarantees that other containers provide are missing. For example, with the other containers the following relationships hold:

// Let c be an STL container other than vector:

T& r = c.front();

T* p = &*c.begin();

For all other containers, the front( ) function yields an lvalue (something you can get a non-const reference to), and begin( ) must yield something you can dereference and then take the address of. Neither is possible because bits are not addressable. Both vector and bitset use a proxy class (reference, mentioned earlier) to read and set bits as necessary.

Associative containers

The set, map, multiset, and multimap are called associative containers because they associate keys with values. Well, at least maps and multimaps associate keys with values, but you can look at a set as a map that has no values, only keys (and they can in fact be implemented this way), and the same for the relationship between multiset and multimap. So, because of the structural similarity, sets and multisets are lumped in with associative containers.

The most important basic operations with associative containers are putting things in and, in the case of a set, seeing if something is in the set. In the case of a map, you want to first see if a key is in the map, and if it exists, you want the associated value for that key to be returned. Of course, there are many variations on this theme, but that’s the fundamental concept. The following example shows these basics:

//: C07:AssociativeBasics.cpp

//{-bor}

// Basic operations with sets and maps

#include

#include

#include

#include

#include

#include "Noisy.h"

using namespace std;

int main() {

  Noisy na[7];

  // Add elements via constructor:

  set ns(na, na + sizeof na/sizeof(Noisy));

  // Ordinary insertion:

  Noisy n;

  ns.insert(n);

  cout << endl;

  // Check for set membership:

  cout << "ns.count(n)= " << ns.count(n) << endl;

  if(ns.find(n) != ns.end())

    cout << "n(" << n << ") found in ns" << endl;

  // Print elements:

  copy(ns.begin(), ns.end(),

    ostream_iterator(cout, " "));

  cout << endl;

  cout << "\n-----------\n";

  map nm;

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

    nm[i]; // Automatically makes pairs

  cout << "\n-----------\n";

  for(size_t j = 0; j < nm.size(); j++)

    cout << "nm[" << j <<"] = " << nm[j] << endl;

  cout << "\n-----------\n";

  nm[10] = n;

  cout << "\n-----------\n";

  nm.insert(make_pair(47, n));

  cout << "\n-----------\n";

  cout << "\n nm.count(10)= "

    << nm.count(10) << endl;

  cout << "nm.count(11)= "

    << nm.count(11) << endl;

  map::iterator it = nm.find(6);

  if(it != nm.end())

    cout << "value:" << (*it).second

      << " found in nm at location 6" << endl;

  for(it = nm.begin(); it != nm.end(); it++)