This is part 2 of the 3-part Exercise 7-0. Click here to see the other parts.

Exercise 7-0 (Part 2 / 3)

Use associative arrays to find all the lines that refer to each word in the input. As per S7.3/126.

Solution

Section 7.3 (Page 126) introduces a method to find all the lines that refer to each word in the input, with the aid of associative arrays. This is so called a “Cross Reference Table”. See the text book for detail description.

Special Note on Line Number

Note that the cross-reference program (xref) as presented by the author of the book uses line 1 to represent the first line (instead of line 0). Likewise, line 2 to represent the second line (instead of line 1). i.e. the line number is always “one more” in comparison to our index system in which index 0 represents the first item.

But then I guess it makes sense as in most editor (like Microsoft Word), whenever we search for a line, it makes more sense from a human perspective that line 1 represents the first line, etc.

Just something to bear in mind – as it is likely that we switch between using 0 or 1 to represent the first line, depending on the problem / application that we are facing.

The Project

Here wrap up the project showing all the source and header files Used.

Source File List

• main.cpp
• split.cpp
• xref.cpp

Header File List

• split.h
• xref.h

Source Files

main.cpp

#include <iostream>   // std::cin, std::cout, std::endl
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include "xref.h"     // xref

using std::cin;
using std::cout;
using std::endl;
using std::map;
using std::string;
using std::vector;

// Find all the lines that refer to each word in the input
// (S7.3/128)
int main()
{
  // Call xref using split by default.
  map<string, vector<int> > ret = xref(cin);

  // Write the results.
  for (map<string, vector<int> >::const_iterator it = ret.begin();
       it != ret.end(); ++it) {

    // Write the word
    cout << it->first << " occurs on line(s): ";

    // Followed by one or more line numbers.
    vector<int>::const_iterator line_it = it->second.begin();
    cout << *line_it;   // write the first line number

    ++line_it;
    // Write the rest of the line numbers, if any.
    while (line_it != it->second.end()) {
      cout << ", " << *line_it;
      ++line_it;
    }
    // Write a new line to separate each word from the next.
    cout << endl;
  }

  return 0;
}

split.cpp

#include <string>    // string
#include <vector>    // vector
#include <cctype>    // isspace
#include <algorithm>  // find_if

using std::vector;
using std::string;
using std::isspace;
using std::find_if;

// true if the argument is whitespace, false otherwise
// (S6.1.1/103)
bool space(char c)
{
  return isspace(c);
}

// false if the argument is whitespace, true otherwise
// (S6.1.1/103)
bool not_space(char c)
{
  return !isspace(c);
}

// Scan a line and split into words. Return a vector that contains these words.
// (S6.1.1/103)
vector<string> split(const string& str)
{
  typedef string::const_iterator iter;
  vector<string> ret;

  iter i = str.begin();
  while (i != str.end()) {

    // Ignore leading blanks
    i = find_if(i, str.end(), not_space);

    // Find end of next word
    iter j = find_if(i, str.end(), space);

    // Copy the characters in ([i, j)
    if (i != str.end())
      ret.push_back(string(i, j));

    // Re-initialize
    i = j;
  }
  return ret;
}

xref.cpp

#include <iostream>   // std::cin, std::istream
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include "split.h"    // split

using std::cin;
using std::map;
using std::string;
using std::vector;
using std::istream;

// Find all the lines that refer to each word in the input
// (S7.3/126)
map<string, vector<int> >
xref(istream& in, vector<string> find_words(const string&) = split)
{
  string line;
  int line_number = 0;
  map<string, vector<int> > ret;  // map string to vector<int>

  // Read the next line
  while (getline(in, line)) {
    ++line_number;

    // Break the input line into words
    vector<string> words = find_words(line);

    // remember that each word occurs on the current line
    for (vector<string>::const_iterator it = words.begin();
         it != words.end(); ++it)
      ret[*it].push_back(line_number);
  }

  return ret;
}

Header Files

split.h

#ifndef GUARD_SPLIT_H
#define GUARD_SPLIT_H

#include <vector>
#include <string>

std::vector<std::string> split(const std::string&);

#endif // GUARD_SPLIT_H

xref.h

#ifndef GUARD_XREF_H
#define GUARD_XREF_H

// xref.h

#include <iostream>   // std::istream
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include "split.h"      // split

std::map<std::string, std::vector<int> >
xref(std::istream&,
     std::vector<std::string> find_words(const std::string&) = split);

#endif // GUARD_XREF_H

Test Program

I now submit some words to the console input upon running the program. The program quickly identify the line numbers (that each word resides) and display results as expected.

apple orange banana
orange orange
apple banana
mango
^Z
apple occurs on line(s): 1, 3
banana occurs on line(s): 1, 3
mango occurs on line(s): 4
orange occurs on line(s): 1, 2, 2

Reference

Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000