CS 330 Lecture 26 – C++’s standard template library
Agenda
- map
- vector
- using STL to write a probababble engine
- http://www.gutenberg.org/
Code
bsearch.cpp
#include <iostream>
template<typename T>
int binarysearch(T *haystack,
T needle,
int first,
int last) {
if (first > last) return -1;
int mid = (first + last) / 2;
if (needle < haystack[mid]) {
return binarysearch<T>(haystack, needle, first, mid - 1);
} else if (needle > haystack[mid]) {
return binarysearch<T>(haystack, needle, mid + 1, last);
} else {
return mid;
}
}
int main() {
int numbers[] = {1, 3, 8, 100, 1003, 12000};
std::cout << binarysearch<int>(numbers, 12000, 0, 5) << std::endl;
std::string names[] = {"Ashlyn", "Becky", "Kevin"};
std::cout << binarysearch<std::string>(names, "Chris", 0, 2) << std::endl;
}
probababble.cpp
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;
typedef std::map<std::string, std::vector<std::string> > strvec_map_t;
void fill_map(strvec_map_t& two_words_to_chasers) {
string aquel;
string ese;
string este;
cin >> aquel >> ese;
while (cin >> este) {
string key = aquel + " " + ese;
/* cout << "key: " << key << std::endl; */
/* cout << "este: " << este << std::endl; */
/* cout << "" << std::endl; */
// append este to key list
strvec_map_t::iterator match = two_words_to_chasers.find(key);
// Did I not find the key?
if (match == two_words_to_chasers.end()) {
vector<string> chasers;
chasers.push_back(este);
pair<string, vector<string> > record;
record.first = key;
record.second = chasers;
two_words_to_chasers.insert(record);
}
// Otherwise, I found the key. Append.
else {
match->second.push_back(este);
}
aquel = ese;
ese = este;
}
/* for (strvec_map_t::iterator key = two_words_to_chasers.begin(); */
/* key != two_words_to_chasers.end(); */
/* ++key) { */
/* std::cout << "key: " << key->first << std::endl; */
/* } */
}
void generate(const strvec_map_t& two_words_to_chasers,
const string& first,
const string& second,
int nwords) {
bool hit_dead_end = false;
string aquel = first;
string ese = second;
string key = aquel + " " + ese;
nwords -= 2;
std::cout << key;
while (nwords > 0 && !hit_dead_end) {
// generate a random chaser
strvec_map_t::const_iterator match = two_words_to_chasers.find(key);
hit_dead_end = match == two_words_to_chasers.end();
if (!hit_dead_end) {
vector<string> chasers = match->second;
int random_index = (int) ((rand() / (float) RAND_MAX) * (chasers.size() - 1));
std::string este = chasers[random_index];
std::cout << " " << este;
--nwords;
aquel = ese;
ese = este;
key = aquel + " " + ese;
}
}
}
int main(int argc, char **argv) {
strvec_map_t two_words_to_chasers;
fill_map(two_words_to_chasers);
generate(two_words_to_chasers, argv[1], argv[2], atoi(argv[3]));
return 0;
}
Haiku
Simple. Powerful.
You’ll have to pick one, my friend.
Only evil is both.
You’ll have to pick one, my friend.
Only evil is both.