Accelerated C++ Chapter 07

どもです。
ぼちぼちと。

メモ

• associative array
  • key-value pair
• pair
  • first, second
• map の各要素は pair
• std::rand() % n
  • 欠点1: n が小さい場合，規則性のある列が生成される。
    • (例) n = 2 の場合，0と1が交互に出現するとか。
      • これは「ランダム」ではない。
  • 欠点2: n が大きい値だと，ある数が他の数よりも多く出現する確率があがる。
    • (例) RAND_MAX=32767, n=20000 とすると，
      • [0, 20000) => [0, 20000)
      • [20000, 32767) => [0, 12767)
      • となり，[0, 12767) の値が出現しやすくなる。
  • どうするか?
    • [0, RAND_MAX] を n 個のグループに分けて，
    • rand() の結果がどのグループに所属するかを求めて乱数とする。

Exercises

Exercise 7-9 は挑戦せず。他のは，長い，簡単，面倒臭いなどの理由により略。

Exercise 7-1

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

static bool cmp(const map<string, int>::const_iterator& lhs,
         const map<string, int>::const_iterator& rhs)
{
  return lhs->second < rhs->second;
}

int main()
{
  string s;
  map<string, int> counters;
  while (cin >> s) {
    ++counters[s];
  }

  vector<map<string, int>::const_iterator> itvec;
  for (map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it) {
    itvec.push_back(it);
  }

  sort(itvec.begin(), itvec.end(), cmp);
  for (vector<map<string, int>::const_iterator>::const_iterator it = itvec.begin();
       it != itvec.end(); ++it) {
    cout << (*it)->first << "\t" << (*it)->second << endl;
  }

  return 0;
}

Exercise 7-3

#include <iostream>
#include <algorithm>
#include <iterator>
#include <map>
#include <vector>
#include <string>
#include <cctype>
#include <cassert>

using namespace std;

vector<string> split(const string& s)
{
  vector<string> ret;
  string::const_iterator it = s.begin();
  while (it != s.end()) {
    while (it != s.end() && isspace(*it)) {
      ++it;
    }
    string::const_iterator beg = it;
    while (it != s.end() && !isspace(*it)) {
      ++it;
    }
    // *it is now space or end
    if (beg != it) {
      ret.push_back(string(beg, it));
    }
  }
  return ret;
}

map<string, vector<int> >
xref(istream& is, vector<string> find_words(const string&) = split)
{
  map<string, vector<int> > ret;

  string line;
  int linenum = 0;
  while (getline(is, line)) {
    ++linenum;
    vector<string> svec = find_words(line);
    for (vector<string>::const_iterator iter = svec.begin(); iter != svec.end(); ++iter) {
      map<string, vector<int> >::const_iterator i = ret.find(*iter);
      if (i == ret.end()) {
        // *iter は初出
        ret[*iter].push_back(linenum);
      }
      else {
        const vector<int>& v = i->second;
        vector<int>::const_iterator j = find(v.begin(), v.end(), linenum);
        if (j == v.end()) {
          // この linenum では初出
          ret[*iter].push_back(linenum);
        }
      }
    }
  }

  return ret;
}

int main()
{
  map<string, vector<int> > ret = xref(cin);

  for (map<string, vector<int> >::const_iterator iter = ret.begin(); iter != ret.end(); ++iter) {
    cout << "\"" << iter->first << "\"" << " occurs on line: ";
    copy(iter->second.begin(), iter->second.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
  }
  return 0;
}

Exercise 7-6

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <stdexcept>
#include <cstdlib>
#include <iterator>

using namespace std;

typedef vector<string> Rule;
typedef vector<Rule> Rule_Collection;
typedef map<string, Rule_Collection> Grammar;

bool bracketed(const string& w)
{
  return w.size() > 1 && w[0] == '<' && w[w.size() - 1] == '>';
}

int nrand(int n)
{
  const int bucket_size = RAND_MAX / n;
  int r = -1;
  for (;;) {
    r = rand() / bucket_size;
    if (r < n) {
      return r;
    }
  }
}

vector<string> split(const string& s)
{
  vector<string> ret;
  string::const_iterator it = s.begin();
  while (it != s.end()) {
    while (it != s.end() && isspace(*it)) {
      ++it;
    }
    string::const_iterator beg = it;
    while (it != s.end() && !isspace(*it)) {
      ++it;
    }
    // *it is now space or end
    if (beg != it) {
      ret.push_back(string(beg, it));
    }
  }
  return ret;
}

Grammar read_grammar(istream& is)
{
  string line;
  Grammar ret;
  while (getline(is, line)) {
    vector<string> vec = split(line);
    if (!vec.empty()) {
      ret[vec[0]].push_back(Rule(vec.begin() + 1, vec.end()));
    }
  }

  return ret;
}

vector<string> gen_sentence(const Grammar& g)
{
  vector<string> ret, rules;
  rules.push_back("<sentence>");

  while (!rules.empty()) {
    string rule_string = rules.back();
    rules.pop_back();
    if (!bracketed(rule_string)) {
      ret.push_back(rule_string);
    }
    else {
      // This is another rule
      Grammar::const_iterator i = g.find(rule_string);
      if (i == g.end()) { throw logic_error("empty rule"); }
      const Rule_Collection& c = i->second;
      const Rule& r = c[nrand(c.size())];
      // Push a chosen rule onto stack
      copy(r.rbegin(), r.rend(), back_inserter(rules));
    }
  }
  return ret;
}

int main()
{
  srand(time(NULL));
  Grammar g = read_grammar(cin);
  vector<string> sentence = gen_sentence(g);

  if (sentence.empty()) {
    cout << "sentence is empty!" << endl;
    return 1;
  }
  copy(sentence.begin(), sentence.end(), ostream_iterator<string>(cout, " "));
  cout << endl;

  return 0;
}

Accelerated C++: Practical Programming by Example (C++ In-Depth Series)

posted with amazlet at 11.03.17

Andrew Koenig Barbara E. Moo
Addison-Wesley Professional
売り上げランキング: 89531

Amazon.co.jp で詳細を見る