Overview

Topics

Libraries

• run time support (e.g. allocation, run-time type information)
• C standard library
• strings
• I/O streams
• containers and algorithms (STL) numeric computation
• regular expression
• concurrent programming
• utilities for template metaprogramming
• utilities for STL-style generic programming
• utilities for general programming
• 'smart' pointers
• special=purpose containers

Standard Library Headers and Namespace

• to access the facilities of a library requires a #include of the corresponding header
  • header names are somewhat intuitive and enclosed in <>, e.g., <string>, <vector>
• the standard library belongs to the std namespace
  • once included, the types, objects, functions in the header can be used, but have to be prefixed by with the name of the namespace and the scope resolution operator (::)
    • the :: operator appears in several other contexts as well (class scope for example)
  • one can avoid this prefix via the using directive

    using namespace std;
    				

Strings

• high-level abstraction of a string
  • contrasts with the relatively low-level C-string which is an array of characters (char [] or char *) terminated with a null ('\0') character.
    • We will cover C-strings later
• mutable — individual characters can be modified (as well as accessed) using the subscript ([]) operator (as well as other inPlace functions, e.g. clear, erase, etc)

  string s = "Hello";
  s[0] = 'J';
  		

• the class is responsible for its own memory (buffer) management

Stream I/O

• Handles character-based input and output

Output

• output defined (via insertion << operator) for all built-in types
• an insertion operator can be easily defined for any user-defined type
• the << operator is defined to permit chaining of values to output

  cout << "The number of values processed is " << numProcess << endl;
  		

  • The result (return value) of each << call is the left-hand operand (cout here) — which is thus passed to the next <<

Input

• extraction >> operator.
• type-safe
• uses call-by-reference (i.e., reference parameters) for the object being input, to permit persistent changes to the object into which the input value is place

  cin >> i;		// i is modified by the operator, so it is passed as a refeeence paramter
  		

• again, easy to define for used-defined types

Containers

• container is a class whose primary purpose is holding other objects
• rich set of containers in the Standard Template Library (STL)

vector

• growable array
• supports subscripting ([]), appending/removal from-end (push_back, pop_back), as well as general insertion, and iteration

Elements

• any type can be an element
  • this is a consequence of the containers being implemented as templates
  • … and is in contrast to Java, which does not allow a primtive type to be an element
• the containers store a copy of the value being placed … not a pointer or reference
  • this results in a compact container
  • of course the user of the container can specify a pointer (or reference) as the element type

Range (bounds)-checking

• vector's [] operator does NOT do range checking
• there's an at function that provides that functionality if so desired

list

• doubly-linked list

map and unordered_map

• map: TreeMap
• unordered_map: HashMap

• The get/put of Java's Map is replaced with []

  map<string, int> freqs;
  …
  cout << freqs["dog"];		// S.o.p(freqs.get("dog"))
  …
  freqs["cat"] = 0;				// m.put("cat", 0);
  		

• viewed as a set of pairs when iterating
  • unlike 'canoncal' Java map iteration where you call keySet

Algorithms

• In addition to providing the standard containers, many standard algorithms (for processing such containers) are provided by the STL
• Commonly-used algorithms — especially for containers
  • sort
  • unique copy
  • find
  • count
  • replace
  • …
• Many of the algorithms operate on sequences of elements within some sort of container; the sequence is represented using iterators.

Iterators

• allow the specification of these algorithms without regard to the particular structure of the container
• same basic idea as Java; semantics and implementation is quite different, however
• the C++ notion of an iterator is a bit more like a position within the sequence

Advice

• [1] Don't reinvent the wheel; use libraries; §4.1.
• Same as 1.12
• [2] When you have a choice, prefer the standard library over other libraries; §4.1.
• Standard libraries are guaranteed to be available (they're part of the standard language distribution).
• They will often (usually?) be better vetted
• [3] Do not think that the standard library is ideal for everything; §4.1.
• Otherwise there would be no other libraries (Boost)
• [4] Remember to #include the headers for the facilities you use; §4.1.2.
• Even if it compiles without including the relevant header file (i.e., some lexically earlier header included the header file)
  • If the current file needs it, don't rely on some other file providing it
  • The prior header file may be moved or removed
• [5] Remember that standard-library facilities are defined in namespace std; §4.1.2.
• That's why we typically use using namespace std;
• [6] Prefer strings over C-style strings (a char *; §2.2.5); §4.2, §4.3.2.
• C-style strings are simple arrays of characters (char []) in which the string is terminated with an ASCII 0 ('\0').
  • '\0' — like many other ASCII values — is not a printable character and thus would never appear as string data; it is thus a good candidate as a trailer value character and thus would never appear as string data; it is thus a good candidate as a trailer value
  • Thus, while most arrays are processed with a header value (the logical size of the array), C-style strings are processed using a trailer value (the '\0').
• C-style strings use 'C-era' technology — they're not memory-managed, nor do they have logic for bounds integrity
• The string class also uses operator overloading which provides a more intuitive interface to the operations (e.g. [])
• [7] iostreams are type-sensitive, type-safe, and extensible; §4.3.
• C I/O used format strings (Java's printf methods derive from this approach) which deferred typing errors to runtime.
• [8] Prefer vector, map, and unordered_map over T[] ; §4.4.
• vector and unordered_map are classes from the Standard Template Library — they handle their own capacity mamnagement (unlike the relatively low-level array type)
• [9] Know your standard containers and their trade-offs; §4.4.
• Know your tools
• [10] Use vector as your default container; §4.4.1.
• Programmers used to use the array as their 'go to' container; vector does the same thing but better
• [11] Prefer compact data structures; §4.4.1.1.
• A compact container has a copy of the value, rather than a pointer or reference. In general, this results in smaller, faster containers
• [12] If in doubt, use a range-checked vector (such as Vec); §4.4.1.2.
range (bounds) checking prevents a whole slew of errors
• [13] Use push_back() or back_inserter() to add elements to a container; §4.4.1, §4.5.
• They are implemented more efficiently than a general insert operation
• [14] Use push_back() on a vector rather than realloc() on an array; §4.5.
• vector;'s memory management is in all likelihood implemented more efficiently than your own memory management
• [15] Catch common exceptions in main(); §4.4.1.2.
• We discussed this; it's better for you to catch an exception, say something, and exit, rather than letting the exception leak through to the system.
• [16] Know your standard algorithms and prefer them over handwritten loops; §4.5.5.
• Same idea as knowing your data structures
• [17] If iterator use gets tedious, define container algorithms; §4.5.6.
• If you find yourself coding the same iteration over and over again on a container, turn it into a method for that container
• [18] You can use the range-for loop for a complete container.
• This is the same as in Java