• C works well in some dimensions:
  • Relatively small language, small set of libraries, the C bible (Kernighan & Ritchie) is under 300 pages long, often viewed as a thin layer on top of machine code.
  • C++, in comparison, tries to do everything, much larger set of libraries, and its bible (by Stroustrup) is over 1000 pages.
• But C doesn't provide type-safe, off-the-shelf generics. The best generics it can offer are bsearch, qsort, memcpy.
  • One can argue that C makes it possible to build generic (in terms of element sizes, not element types), but that the language is really working against you.
    
  • The elements stored or otherwise manipulated by C's generics carry zero type information whatsoever beyond their size, and that's not very much.
• That's not to say C doesn't have its evangelists!
  • I know C better than any other language, and I genuinely love it.
  • Many veteran programmers know the language so well and have built so much code and so many libraries that they feel switching languages is too much of an opportunity cost.
• C++ offers many things, and many feel it tries too hard to be everything for everybody.
  • However, its support for generic programming is far superior to that provided by C. There are some drawbacks (C++ template code bloat, for example), but coding against C++ template data structures is just plain easier than coding against the C equivalents that we have to write ourselves.
  • As we move on to build larger systems and need larger data structures, I'd rather you leverage the C++ string class, the STL's binary_search algorithm, and the STL vector than have you rely on the '\0'-terminated character array, bsearch, and the brittle, error-prone void *-reliant CVector.
• Be sure to sync up against /usr/class/cs110/lecture-examples/spring-2018/ to get your own copies of all of these examples, which appear in a new subdirectory called cpp-primer.

• Consider the following:

class couple {
  friend std::ostream& operator<<(std::ostream& os, const couple& c);

 public:
  couple();
  couple(const std::string& one, const std::string& two);
  const std::string& getFirst() const;
  const std::string& getSecond() const;

 private:
  std::string first;
  std::string second;
};

• The class models pairs of individuals: a bride and groom, two lovebirds, twin sisters, BFF's, etc.
• You're familiar with the notion of a constructor, overloading, references, and public and private access modifiers.
• You're likely confused about const, friend, why I'm overloading operator<< on behalf of the couple class the way I am, and why I introduce a zero-argument constructor when the two-argument version does such a stellar job requiring a raw object be initialized with meaningful data the moment the object is born. (Oh yeah, why no destructor?)

• References are used in many places to suppress deep cloning of objects. Provided the code can't change the referenced strings, this is a win from a performance and memory resources standpoint. (As it turns out, passing immutable references to stringss instead of copies of them isn't that huge a win, but it's emblematic of the coding style we want to go with when we pass around large data structure (e.g. vectors, maps) that are best shared instead of copied).
• The two-argument constructor is provided for what I'm assuming are obvious reasons. But when you define any constructor, you lose the default zero-argument constructor, which the compiler otherwise synthesizes to perform zero-argument construction on all direct embedded objects (and to do nothing with the direct embedded primitives, like ints and pointers).
• It's almost always the right thing to provide a zero-argument constructor, so that a client can declare arrays and containers of them. If there's no zero-argument constructor (either compiler-synthesized or programmer-supplied), then you have a difficult time declaring aggregate collections of them, as with:

couple weddingParty[4];
map<string, couple> addressBook;

• There's no destructor, because the compiler-synthesized one (which does member-wise destruction on all direct embedded objects) is all we need. In general, you don't write code if the compiler otherwise gives you precisely the same thing.
• The friend keyword marks operator<< as a function that's privileged enough that it can directly access the couple object's private data. The friend keyword should always be used sparingly, but in this case it's appropriate, because operator<< is being implemented as part of the couple class, and there's less of a compelling reason to force the overloaded operator<< function to be a client of the couple class when it's actually being implemented on behalf of couple.
• Note that getFirst and getSecond are marked as const methods, which means their implementations promise to treat the objects they manipulate as read-only (and the compiler is sure to holler if you try to change the objects when you're not supposed to).

• Virtually everything is one line, save for the implementation of operator<<

couple::couple() {}
couple::couple(const string& one, const string& two) : first(one), second(two) {}

const string& couple::getFirst() const { return first; }
const string& couple::getSecond() const { return second; }

ostream& operator<<(ostream& os, const couple& c) { // note this is a function!!!
  os << c.first << " and " << c.second;
  return os;
}

• The initialization list specifies exactly how first and second should be constructed from scratch.
• Prior courses that want to push memory details to the back burner encourage you to omit the initialization list altogether and instead assign first and second to be set equal to one and two, respectively.
  • But by omitting the initialization list, you're just telling the compiler you'd prefer first and second each be defaultly constructed to the empty string (via the zero-agument constructors), and then reassigned to be memory-independent but otherwise logical copies of one and two.
  • There's no reason to build data members up only to bring them down and rebuild them up again into something different. It makes more sense to build them up once to be what they need to be right away. That's why the initialization list is so awesome.

• The zero-argument version (which we provide because we'd otherwise lose it entirely as a result of explicitly providing a two-argument version) omits the initialization list. But that means that the two embedded strings should just be zero-arg constructed into empty strings (which makes sense here). Since there's nothing else to do, there's no other code between the curly braces.

• The couple class stated quite clearly that this particular operator<< is its friend.
• Note the implementation directly accesses the first and second fields! That's what comes with C++ friendship.

• Client program:

int main(int argc, char *argv[]) {
  couple hosts("Colleen", "Joe");
  assert(hosts.getFirst() == "Colleen");
  assert(hosts.getSecond() == "Joe");
  couple guests[kNumCouples]; // works only because we provide a zero-argument constructor
  assert(guests[0].getFirst().empty());

  guests[0] = couple("Robin", "Jamie");
  guests[1] = couple("April", "Chris");
  guests[2] = couple("Jennifer", "Andrew");
  cout << "Dinner party guest list: " << endl;
  cout << "Hosts:  " << hosts << endl;
  for (const couple& c: guests) { // C++11 for loop  works because context provides array length
    cout << "Guests: " << c << endl;
  }

  cout << endl;
  cout << "We're serving duck!" << endl;
  return 0;
}    

• Program output:

myth22> ./dinner-party 
Dinner party guest list: 
Hosts:  Colleen and Joe
Guests: Robin and Jamie
Guests: April and Chris
Guests: Jennifer and Andrew

We're serving duck!
myth22>

• Features of interest:
  • You can declare an array of couples, but only because we provided a zero-argument constructor. Had we not, the array declaration wouldn't compile, because g++ wouldn't know how to initialize its couple members.
  • Note the new for loop syntax, courtesy of C++11. We'll see this works with STL containers as well. #hotness
  • Understand that couple::operator= is being called three times as well. This is also auto-generated by the compiler, and the default is to do memberwise operator= on all embedded fields. And because the string class gets its operator= method right, the couple class gets its operator= right as well.
    • Astute remark: Strive to design classes that avoid dynamic memory allocation, because if you do, it's very likely that the class's default copy constructor and its operator= method will just do the right thing.
    • In fact, I don't forsee a situation in this course where I will require you to implement a copy constructor or an operator= method, because all classes you and I implement will layer on top of non-pointer primitives and direct embedded objects.

• Course is about building systems, not about programming language trivia.
• I promise to make construction, destruction, and reassignment of objects as intuitive as possible.
• You should understand where each of the different memory management directives are used during the execution of a heavily-OO C++ program.
• If you want a free, online resource to learn about C++ memory management, you might check this site.
  • Both textbooks can be downloaded for free.
  • We used the first textbook some 15 years ago when we taught a C++ service course as CS193D (which hasn't been taught in forever, since our CS106B curriculum teaches C++ now).

• My assumption is that you've used template containers before, e.g. CS106B Vector template, or the STL vector.
• Even if you've implemented a template before, there are features and nuances worth discussing so you understand just how beautifully designed and clever the STL is.

• We'll define our own find template so we can discuss how and why it works.
  • Understand, however, that find is already a C++ STL built-in.
    
  • We'll generally choose to use a library version instead of hand rolling our own.
    
  • This is the one time where we'll benefit from writing it out ourselves, just so we can analyze it and learn how it works.
• Check this out:

template <typename Iterator, typename T>
Iterator find(Iterator begin, Iterator end, const T& elem) {
  Iterator curr = begin;
  while (curr != end && *curr != elem) {
    ++curr;
  }
  return curr;
}    

• And iterator is either a pointer, or something that behaves like a pointer in that it responds to operator*, operator++, and so forth, to the extent needed by the implementation.
• The implementation doesn't commit to any choices for Iterator or T, as they're simply placeholders for types that will eventually be supplied by a specific call (or inferred from the arguments supplied at the call site).
• elem is the item we're searching for; begin and end define the addresses that bookend the range of items to be searched.
  • begin functions as the start iterator, meaning that it's the first pointer/iterator to be manipulated as part of execution.
  • end is really a past-the-end pointer/iterator. It serves as a sentinel value that, if reached, should prompt the search to give up and express failure.
• Note that whatever Iterator turns out to be, it must play well with operator*, operator!=, and operator++ (and that's rarely a problem if the iterator is a traditional pointer type). Otherwise, the expansion of the template on the selected types won't compile.
• T and Iterator must be somewhat related, in that an instance of T must be comparable (in the != sense) to whatever a dereferenced Iterator identifies. Otherwise, the expansion of the template on the selected types won't compile.
• Convention: rather than returning NULL to express failure, STL algorithms typically return the supplied end iterator to express failure. They otherwise return the iterator that addresses the item of iterest (and, in the case of our find, the item that matches the one we're looking for).

• Considering the following, which uses find to search int, double, and C++ string arrays:

int main(int argc, char *argv[]) {
  int numbers[] = {3, 1, 5, 8, 9, 5};
  assert(find(numbers, numbers + 6, 3) == numbers);
  assert(find(numbers, numbers + 6, 9) == numbers + 4);
  assert(find(numbers, numbers + 6, 5) == numbers + 2);
  assert(find(numbers, numbers + 6, 7) == numbers + 6);
  assert(find(numbers + 1, numbers + 3, 3) == numbers + 3);

  double gpas[] = {3.5, 3.1, 3.6, 3.2, 1.7, 3.0, 2.8, 3.1, 3.22};
  assert(find(gpas, gpas + 9, 3.6) == gpas + 2);
  assert(find(gpas, gpas + 9, 3.22) == gpas + 8);
  assert(find(gpas, gpas + 9, 1.1) == gpas + 9);
  assert(find(gpas + 4, gpas + 5, 1.7) == gpas + 4);

  string friends[] = {"Scott", "Jon", "Arlene", "David", "Tim", "Shana", "James", "Lisa"};
  assert(find(friends, friends + 8, "Shana") == friends + 5);

  cout << "Made it to the end without asserting." << endl;
  return 0;
}

• Fact: the find template is expanded into three different, type-specific versions, and all three versions operates as if we ourselves typed out all three, by hand, as overloaded versions of the same function. (The code bloat aspect of what happens here is one main criticism of the C++ template approach).
• It's instructive to understand how operator++ and operator!= work within each of the three expansions, and we'll make some observations about two or maybe even all three of them.

• Here's a unit test program illustrating just a small fraction of the common algoritms provided when you #include <algorithm>.
• All of the STL algorithms that appear below are documented at http://en.cppreference.com/w/cpp/algorithm.

static bool isEven(int number) { return number % 2 == 0; }
static bool isGreaterThan(int one, int two) { return one > two; }
static void assertIsOdd(int number) { assert(!isEven(number)); }

int main(int argc, char *argv[]) {
  int numbers[] = {11, 7, 19, 3, 17, 5, 2, 13};
  int *found = find(numbers, numbers + 8, 17);
  assert(found == numbers + 4 && *found == 17);

  found = find_if(numbers, numbers + 8, isEven);
  assert(found == numbers + 6 && *found == 2);

  assert(accumulate(numbers, numbers + 8, 0) == 77);

  sort(numbers, numbers + 8);
  assert(is_sorted(numbers, numbers + 8));
  assert(binary_search(numbers, numbers + 8, 11));
  assert(!binary_search(numbers, numbers + 8, 12));

  for_each(numbers + 1, numbers + 8, assertIsOdd);

  found = find(numbers, numbers + 8, 19);
  assert(found == numbers + 7 && *found == 19);

  found = lower_bound(numbers, numbers + 8, 17);
  assert(found == numbers + 6 && *found == 17);
  found = lower_bound(numbers, numbers + 8, 14);
  assert(found == numbers + 6 && *found == 17);

  reverse(numbers, numbers + 8);
  assert(is_sorted(numbers, numbers + 8, isGreaterThan));

  cout << "Made it to the end without asserting." << endl;
  return 0;
}    

• object-oriented, growable, shrinkable, sequential container designed to emulate all that's good about traditional arrays.
• The growable and shrinkable part is a huge bonus, because it manages all aspects of resizing and memory management so the data structure is always just as long as it needs to be. #winning

static const int kNumbers[] = {2, 3, 5, 7, 11, 13, 17, 21, 23, 27, 29, 31};
static const int kCount = sizeof(kNumbers)/sizeof(kNumbers[0]);

• The above just defines some globals that act more or less as data sources. The array is intentionally sorted, and you'll note that most (but by design, not all) are prime numbers. We use the array constant to initialize the vector below.
• The main function below continues over several pages so that I can introduce the STL iterator concept in stages.

int main(int argc, char *argv[]) {
  vector<int> primes(kNumbers, kNumbers + kCount);
  primes.push_back(37);
  primes.push_back(41);

  vector<int>::const_iterator curr = primes.cbegin();
  assert(*curr == 2);
  ++curr; // prefix form is standard in STL-oriented C++
  assert(*curr == 3);
  assert(is_sorted(primes.cbegin(), primes.cend()));

• The two-argument constructor used above initializes the raw memory of a vector to be one that contains a copy of the sequence of items in between the two supplied pointer arguments.
• push_back appends a new item to the end.
• Note the call to vector<int>::cbegin(), which returns a vector<int>::const_iterator that addresses the leading item of the vector<int>. Because it's a vector<int>::const_iterator (as opposed to a vector<int>::iterator, which is what vector<int>:begin() returns), one can't change the item it addresses.
• Iterators are the glue that allow the STL algorithms to operate on sequences of data held in STL containers.
  • Core definition: An iterator is a pointer, or it is a data type—usually a class—that behaves like a pointer.
  • Iterators are able to imitate the behavior of pointers because they overload operator*, operator++, operator==, and so on.
  • *curr above is really a call to curr.operator*(), which returns a read-only reference to the vector<int> item it addresses.
  • ++curr above is reframed as a call to curr.operator++(), which advances the iterator itself to address the next item in the sequence.
• vector<int>::cend() also returns a vector<int>::const_iterator, which functions as the past-the-end iterator that marks the end of the data sequence.

• Let's call find to confirm that 14 isn't recorded as a prime number, but that 7 is.

  // linear search  
  assert(find(primes.cbegin(), primes.cend(), 14) == primes.cend());
  assert(find(primes.cbegin(), primes.cend(), 7) != primes.cend());
  assert(find(primes.cbegin(), primes.cend(), 7) == primes.cbegin() + 3);

• find will return the supplied past-the-end iterator to express failure.
• vector iterators actually support operator+(int) as well, so we can not only confirm the 3 is present, but we can confirm that the 7 is the 4^th item in the sequence.
• Iterators aren't required to overload every single operator compatible with true pointers, but they'll typically overload any that can be implemented to run in O(1) time.
• Since vectors are backed by arrays, we shouldn't be surprised that its iterators overload virtually every possible operator. (Iterators for the STL forward_list, list, set, and map, however, do not overload every possible operator, because some of them can't be implemented efficiently).

  // binary_search
  assert(binary_search(primes.cbegin(), primes.cend(), 41));
  assert(!binary_search(primes.cbegin(), primes.cend(), 33));
  assert(!binary_search(primes.cbegin() + 1, primes.cend() - 1, 41));   

• Because the primes sequence is sorted, we can expect the STL binary_search to properly divide-and-conquer the vector to confirm or refute the presence of a particular number, and to do so in logarithmic time.

• The insert and erase operations are iterator-oriented, in that they rely on iterators to identify insertion and deletion points.
• Note the use of the auto keyword, which can be used as a placeholder for a type that can be easily inferred by the compiler, but it too much of a hassle to type out in full. (The auto keyword was just introduced in C++11, and the thousands of C++ programmers who know about it are thrilled).
• Note that the the first five lines below are framed in terms of begin and end (as opposed to cbegin and cend), because we need to modify the vector through the iterator produced by the call to lower_bound.

  auto found = lower_bound(primes.begin(), primes.end(), 19);
  assert(found == primes.begin() + 7 && *found == 21); // insert that 19 before the 21 to maintain sorted order
  auto iter = primes.insert(found, 19); // return value addresses the item just inserted
  assert(*iter == 19);
  primes.erase(iter + 1); // reach one beyond the 19 to the 21 and delete it

• Since we've done surgery on the vector, make sure it's what we want. (Note we're using cbegin and cend again, since is_sorted and binary_search are read-only algorithms).

  assert(is_sorted(primes.cbegin(), primes.cend()));
  assert(binary_search(primes.cbegin(), primes.cend(), 19));
  assert(!binary_search(primes.cbegin(), primes.cend(), 21));

• We supply not one, but three ways to iterate over the vector of prime numbers.

  printPrimesOne(primes);
  printPrimesTwo(primes);
  printPrimesThree(primes);

  cout << endl;
  cout << "Made it to the end without asserting." << endl;
  return 0;
}

• The first way is obvious, although it does advertise the fact that the vector class itself overloads operator[](int) to return a reference to an item at a particular index.

static void printPrimesOne(const vector<int>& v) {
  cout << "Vector contents (take 1): " << endl << endl;
  for (size_t i = 0; i < v.size(); i++) {
    cout << "  " << setw(2) << (i + 1) << ".) " << v[i] << endl;
  }
  cout << endl;
}    

• The second way is the more hip C++11 way to reach every element.

static void printPrimesTwo(const vector<int>& v) {
  cout << "Vector contents (take 2): " << endl << endl;
  size_t label = 1;
  for (int prime: v) {
    cout << "  " << setw(2) << label << ".) " << prime << endl;
    label++;
  }
  cout << endl;
}

• The third way is, admittedly, contrived just so I can introduce the notion of a block (aka an anonymous function, available to us courtesy of C++11).

static void printPrimesThree(const vector<int>& v) {
  cout << "Vector contents (take 3): " << endl << endl;
  size_t label = 1;
  for_each(v.begin(), v.end(), [&label](int prime) -> void {
    cout << "  " << setw(2) << label << ".) " << prime << endl;
    label++;
  });
}    

• Note that the third argument is an on-the-fly, anonymous function definition that uses the notion of a capture (e.g. the [&label]) so that state from the surrounding context can be made available and shared with the anonymous function.
  • The & of &index informs g++ that index should be captured by reference. Had we not captured index by reference (e.g. by value, using [index]), then the outer index would be copied, and the copy (as opposed to the original) would be ++'ed.
  • You're not required to capture anything (e.g. you can just type []).
  • You can capture multiple items as well (e.g. [value1, &value2, this]).
  • You can also tell the anonymous function's return type is void, because the function prototype says that's what the int argument is transformed into (e.g. -> void)

• Our one large example ingests all words from a plain-text version of a large novel, compile all information of interest into a map<string, size_t>, generate some statistics, and then allow us to query the index for information about words we're curious about. The program that follows appears over the next few slides.

int main(int argc, char *argv[]) {
  if (argc != 2) {
    cerr << "Usage: " << argv[0] << " <text-file>" << endl;
    return kWrongArgumentCount;
  }

  ifstream infile(argv[1]);
  if (infile.fail()) {
    cerr << "File named \"" << argv[1] << "\" couldn't be opened." << endl;
    return kFileNotAccessible;
  }

  map<string, size_t> m;
  StreamTokenizer st(infile, kDelimiters);
  while (st.hasMoreTokens()) {
    string str = toLowerCase(st.nextToken());
    m[str]++;
  }

  cout << "Ingested all of \"" << argv[1] << "\"." << endl;
  cout << "Discovered " << m.size() << " unique words." << endl;

• There is a healthy amount of error checking up front, as there should be.
• I made use of a custom StreamTokenizer class that imitates the Java StringTokenizer class.
• The m[str]++; is much more involved that you might think, because it's not clear what happens when str isn't even in the map yet.
  • If str is already present as a key, m[str]++; produces a reference to its companion size_t and levies the ++ directly against the size_t at the other end of that reference. Restated, the size_t within the map is promoted by one.
  • If str isn't present, it's silently inserted, attached to a 0, and then a reference to that 0 is surfaced so it can be ++'ed.

• map sorts string keys so that neighboring strings in the inorder serialization respect string::operator<
• That fact makes it exceptionally easy to construct a parallel vector of pair<string, size_t>, which is how each word/frequency pair is packaged inside the map.
  • The benefit of constructing a parallel, sorted vector is that we can call lower_bound on it (since the vector's iterators play well with operator+ and operator-, but the map's iterators do not.

  vector<pair<string, size_t>> alphabeticallySortedWords(m.cbegin(), m.cend());
  printLeadingWords("Leading words, sorted alphabetically", alphabeticallySortedWords, 15);
  vector<pair<string, size_t>> frequentlyOccurringWords(alphabeticallySortedWords);
  auto compfn = [](const pair<string, size_t>& one, const pair<string, size_t>& two) -> bool {
    return
    (one.second > two.second) ||
    (one.second == two.second && one.first < two.first);
  };
  sort(frequentlyOccurringWords.begin(), frequentlyOccurringWords.end(), compfn);
  printLeadingWords("Leading words, sorted by frequency", frequentlyOccurringWords, 15);    

• We also construct a second vector<pair<string, size_t>>
• Note the definition of a local variable (the type of which is inferred using the auto keyword) initialized to an on-the-fly block that can be used in a few places. C++11 ftw.

• Program uses map<string, int>::find, lower_bound, and the same anonymous function we defined above.

  while (true) {
    cout << "Enter a word [or just hit enter to quit]: ";
    string word;
    getline(cin, word);
    word = toLowerCase(trim(word));
    if (word.empty()) break;
    auto found = m.find(word);
    if (found == m.end()) {
      cout << "The word \"" << word << "\" isn't present. #facepalm" << endl;
    } else {
      cout << "The word \"" << word << "\" is present and appears this many times: " 
           << found->second << " [with frequency rank: ";
      const pair<string, size_t>& match = *found;
      auto found = lower_bound(frequentlyOccurringWords.cbegin(),
                               frequentlyOccurringWords.cend(), match, compfn);
      size_t rank = found - frequentlyOccurringWords.cbegin() + 1;
      cout << rank << "]" << endl;
    }
  }

  return 0;
}    

• map<string, int>::find returns a iterator to the relevant pair within the map if a match is found, but otherwise returns the map's end iterator.
• trim and toLowerCase are utilities I provide for you (e.g. they're not built-in C++ functions, even though they should be).

• Here it is:

static void printLeadingWords(const string& header,
                              const vector<pair<string, size_t>>& words, size_t count) {
  cout << header << ":" << endl;
  cout << endl;
  auto curr = words.cbegin();
  for (size_t i = 1; i <= count && curr != words.cend(); i++, ++curr) {
    cout << "  " << setw(2) << i << ".) " << curr->first 
         << " [count: " << curr->second << "]" << endl;
  }
  cout << endl;
}