The C++ Standard Library

Michael, who is president of ObjectCraft and a columnist for The C++Report, chairs the Library Working Group of the ANSIX3J16. He can be contacted at [email protected].

Library Overview

The essential structure of the C++ Standard Library can be represented by Figure 1. Each of the ten categories provide definitions for the following types of Standard entities: macros, values, types, templates, classes (and structs), functions (including operators), and objects. Since many of the nonmember functions operate upon instances of the specified classes, the collection of such functions and their associated class is often referred to as a "component."

The Language Support components are required by certain parts of the C++ language, such as dynamic-memory allocation and exception processing. The Diagnostics category includes the definition of the standard exceptions thrown by other library components, providing support for uniform error reporting by the library. General Utilities components are used by other standard-library components (including the memory allocator used throughout the STL components) but can also be used directly by C++ programs.

The Strings category provides basic text representation and manipulation, while Localization components provide locale-dependent formatting facilities.

The Containers, Iterators, and Algorithms categories incorporate the essential elements of the STL library. The Numerics category includes the STL generalized numeric algorithms, complex numbers, and support for array-based (n-at-a-time) computations. The Input/Output category is the largest, and it contains the iostream's components.

The C++ Standard Library also provides the facilities of the amended ISO Standard C library, suitably adjusted to ensure static type safety. The components of this library are referenced, as needed, from the various categories.

Headers

As with C, a C++ program gains access to standard-library facilities by #includeing the appropriate header(s). The C++ Standard defines 68 headers. These additional headers are the result of reconciling two conflicting goals: C++ namespace organization, and compatibility with existing C++ source code. Table 1 lists the 32 new C++ headers.

In Standard C++, all library entities (except preprocessor macros) are defined within the namespace std. In C, all library entities are defined in the global namespace. To retain the advantages of an organized namespace, yet preserve the meaning of existing C library #include directives, the facilities of the Standard C Library are provided in additional headers; see Table 2.

The contents of each header cname are essentially the same as the corresponding C header name.h, as specified in the ISO C standard. In the C++ Standard Library, however, these declarations and definitions are within the scope of the std namespace.

Therefore, the C++ Standard Library also supports the 18 name.h (C header) forms. Each of these headers #includes the corresponding cname header and the appropriate using declarations in order to place all of its declarations and definitions into the global namespace.

Thus, a C++ program can be ported quickly from its C version, as shown in Listing One. Conversely, the program could be written as a C++ program that is meticulous about its namespaces; see Listing Two.

These programs illustrate some of the most common tasks performed in C and C++ programs: handling string text to and from files in secondary storage. The C++ Standard Library provides components that simplify these tasks.

Strings and iostreams

Consider the relatively straightforward programming task of displaying the contents of a text file. Listing Three uses the facilities of the Standard C library to open the file named in its command-line argument, read the file a line at a time, and print out each line on the standard output (preceded by the number of characters in the line). The essential part of this program involves only four lines: those containing fopen(), feof(), fgets(), and printf(). The rest is error handling and recovery. Given a simple text file (such as a daily "to-do" list), the program produces the output in Listing Four. Listing Five performs the same task, using the string and iostream components from the C++ Standard Library. It is noticeably shorter, mostly because the iostream components encapsulate much of the file-related error checking. iostreams are the preferred mechanism for C++ program input and output. The components in the C++ Standard Library (such as strings, locales, and complex numbers) overload the >> and << operators to provide formatted input and output using iostreams. The Standard iostreams are much the same as those that C++ developers have been using for the past ten years. Table 3 summarizes only the components provided in the standard headers <iosfwd>, <iostream>, <ios>, <streambuf>, <istream>, <ostream>, <iomanip>, <sstream>, and <fstream>.

The iostream facilities have been generalized to accommodate both char- and wchar_t-based character sequences (and others). The older C library facilities are also available, in <cstdio> (for chars) and <cwchar> (for wchar_ts).

The C++ Standard Library also provides components for manipulating sequences of characters, where characters may be of type char, wchar_t, or of a type defined in a C++ program. It provides both the C++ string classes and null-terminated sequence utilities from the C library. Table 4 summarizes the string components from the standard header <string>.

The library provides a basic_string template, which defines the semantics of strings. The string and wstring types are predefined template instantiations (of basic_string<char> and basic_string<wchar_t>, respectively) provided by the library.

The older C library facilities are also available, provided by the standard headers <cctype>, <cwctype>, <cstring>, <cwchar>, and the multibyte conversions from <cstdlib>.

Containers, Iterators, and Algorithms

A more interesting application involving to-do lists might sort them according to certain criteria. It would be handy to first read the list in from the file and then keep it around in memory. The C++ program in Listing Six uses the most obvious representation: a simple list of strings.

This program uses two more components from the C++ Standard Library: an instance of the list template to hold the strings describing things to do, and an iterator type to step through the list and print each item.

Lists are just one component that C++ programs may use to organize collections of information. Table 5 summarizes the standard sequences and associative containers. The < and == relations are defined so that these containers can be used with the standard iterator and algorithm components. A C++ program may define additional container components. With suitably defined relational operations, they can also be used with the standard iterator and algorithm components.

Iterators are the "glue" between the standard containers and the algorithms that operate upon them. Table 6 summarizes the components for iterator tags, predefined iterators, stream iterators, and streambuf iterators from the standard header <iterator>.

C++ programs are not restricted to using the specific predefined iterator components. For example, pointers and pointer arithmetic can be used as iterators over many sequences. The standard algorithms work equally well with both kinds of iterators. Table 7 lists the algorithm components from the standard header <algorithm>.

Listing Seven uses iterators to invoke the standard sort() algorithm on the to-do list. Since sort() requires random access to the elements to be sorted, this version of the program uses a vector instead of a list. The rest of the program is the same as before. This program uses the default ordering relation on strings (operator<) to sort the to-do list. While this works well as a default, it is subject to the vagaries of local string representation. For example, Listing Eight shows how this program can be led into making a mistake when the input has some unfortunate spaces (in the default ASCII collation, spaces sort before other characters).

The next version of the program takes a more comprehensive approach to prioritizing to-do items. In addition to a numerical ranking, each item can have a due date. Listing Nine contains the necessary scaffolding.

With these definitions in place, it requires very little change to support relatively sophisticated to-do-list processing. Listing Ten is essentially the same as the previous version, requiring only the substitution of the new representation of the items on the list.

Given the correct handling of date input and ordering (via struct when), the program will now correctly sort the to-do list items. Listing Eleven shows the result, sorting by date and ordinal priority within each date.

The final version of this program is only slightly more clever. Rather than waiting until it reads all the to-do items to explicitly sort the list, it sorts the list as it reads each item. Listing Twelve uses a self-organizing data structure, the standard priority_queue, to keep the list sorted.

Conclusion

Figure 1: The major functional areas of the C++Standard Library.

Table 1: C++ Standard Library headers.

<algorithm>     <new>
<bitset>        <numeric>
<complex>       <ostream>
<deque>         <queue>
<exception>     <set>
<fstream>       <sstream>
<functional>    <stack>
<iomanip>       <stdexcept>
<ios>           <streambuf>
<iosfwd>        <string>
<iostream>      <typeinfo>
<istream>       <utility>
<iterator>      <valarray>
<limits>        <vector>
<list>          <set>
<locale>        <sstream>
<map>           <stack>
<memory>        <stdexcept>

<cassert>
<cctype>
<cerrno>
<cfloat>
<ciso646>
<climits>
<clocale>
<cmath>
<csetjmp>
<csignal>
<cstdarg>
<cstddef>
<cstdio>
<cstdlib>
<cstring>
<ctime>
<cwchar>
<cwctype>
<cmath>
<csetjmp>
<csignal>
<cstdarg>
<cstddef>
<cstdio>
<cstdlib>
<cstring

(a)
basic_ios
ios_traits
basic_streambuf
basic_istream
basic_ostream
basic_stringbuf
basic_istringstream
basic_ostringstream
basic_filebuf
basic_ifstream
basic_ofstream
(b)
ios_base
(c)
ios
wios
streambuf
istream
wistream
wstreambuf
ostream
wostream
stringbuf
istringstream
wistringstream
wstringbuf
ostringstream
wostringstream
filebuf
ifstream
wifstream
wfilebuf
ofstream
wofstream
(d)
cin
cout
win
cerr
clog
wout
werr
wlog

(a)     basic_string
(b)     string
        wstring
(c)     Construct, copy, assign
(d)     begin(), end()
        rbegin(), rend()
(e)     empty(), size(), length()
        max_size(), capacity()
        resize(), reserve()
(f)     at(), operator[]
        c_str(), data()
(g)     append(), operator+=
        assign(), insert()
        remove(), replace()
        copy(), swap()
(h)     find()
        rfind()
        find_first_of()
        find_last_of()
        find_first_not_of()
        find_last_not_of()
        compare()
        getline()

Header    Component(s)

<bitset>  bitset
<deque>   deque
<list>    list
<map>     map, multimap
<queue>   queue, priority_queue
<set>     set, multiset
<stack>   stack
<vector>  vector, vector<bool>

(a)
istream_iterator

back_insert_iterator

ostream_iterator

front_insert_iterator

reverse_bidirectional_iterator

insert_iterator

reverse_iterator

istreambuf_iterator

ostreambuf_iterator
(b)
bidirectional_iterator

input_iterator

forward_iterator

random_access_iterator

adjacent_find
pop_heap
binary_search
prev_permutation
copy
push_heap
copy_backward
random_shuffle
count
remove
count_if
remove_copy
equal
remove_copy_if
equ-al_range
remove_if
fill
replace
fill_n
replace_copy
find
replace_copy_if
find_if
replace_if
for_each
reverse
generate
reverse_copy
generate_n
rotate
includes
rotate_copy
inplace_merge
search
lexicographical_compare
set_difference
lower_bound
set_intersection
make_heap
set_symmetric_difference
max
set_union
max_element
sort
merge
sort_heap
min
stable_partition
min_element
stable_sort
mismatch
swap
next_permutation
swap_ranges
nth_element
transform
partial_sort
unique
partial_sort_copy
unique_copy
partition
upper_bound

Listing One

#include <string.h> // C library functions
#include <stdio.h>  // are in the global namespace
int main()
{
  char h[] = "hello, ";
  char w[] = "world\n";
  char hw[sizeof h + sizeof w];
  strcpy(hw, h);    // catenate strings
  strcat(hw, " ");
  strcat(hw, w);
  printf(hw);   // output
  return 0;
}

Listing Two

#include <cstring>  // same C library functions
#include <cstdio>   // in namespace std
int main()
{
  char h[] = "hello,";
  char w[] = "world\n";
  char hw[sizeof h + sizeof w];
  std::strcpy(hw, h);
  std::strcat(hw, " ");
  std::strcat(hw, w);
  std::printf(hw);
  return 0;
}

Listing Three

#include <string.h>
#include <stdio.h>
#include <stdlib.h> // for EXIT_FAILURE
int main(int argc, char* argv[])    // copy file to stdout
{
  FILE* file = fopen(argv[1], "r");
  char errbuf[80];  // just in case
  if (!file) {
    sprintf(errbuf, "%s no good", argv[1]);
    perror(errbuf);
    return EXIT_FAILURE;
  }
  while ( !feof(file) ) {
    char line[256]; // hopefully large enough
    char* ok = fgets(line, sizeof line, file);
    if (!ok) {
      sprintf(errbuf, "read error on %s", argv[1]);
      perror(errbuf);
      return EXIT_FAILURE;
    }
    printf("[%2d]\t%s", strlen(line), line);    // has '\n' already
  }
  return 0;
}

Listing Four

[18]    End the arms race
[ 6]    Floss

Listing Five

#include <string>
#include <fstream>
#include <iomanip>  // for setw
int main(int argc, char* argv[])    // copy file to cout
{
  using namespace std;
  ifstream in(argv[1]);
  while (in.good()) {
    string line;
    if (getline(in, line))
      cout << '[' << setw(2) << line.size()<< ']' << '\t' << line << endl;
  }
  return 0;
}

Listing Six

#include <string>
#include <fstream>
#include <list>
int main(int argc, char* argv[])

{
  using namespace std;
  ifstream in(argv[1]);
  typedef list<string> ToDo_List;
  ToDo_List to_do;
  while (in.good()) {
    string buf;  getline(in, buf);  to_do.push_back(buf);
  }
  typedef ToDo_List::iterator iter;
  for (iter i = to_do.begin(); i != to_do.end(); ++i)
    cout << *i << endl;
  return 0;
}

Listing Seven

#include <string>
#include <fstream>
#include <vector>   // for random access via operator[]
#include <algorithm>    // for sort()
int main(int argc, char* argv[])
{
  using namespace std;
  ifstream in(argv[1]);
  typedef vector<string> ToDo_List;
  ToDo_List to_do;
  while (in.good()) {
    string buf;  getline(in, buf);  to_do.push_back(buf);
  }
  typedef ToDo_List::iterator iter;
  for (iter i = to_do.begin(); i != to_do.end(); ++i)
    cout << *i << endl;
  sort(to_do.begin(), to_do.end());
  cout << "\nSorted:" << endl;
  for (iter j = to_do.begin(); j != to_do.end(); ++j)
    cout << *j << endl;
  return 0;
}

Listing Eight

Input:
1. End the arms race
 2. Floss
Output:
 2. Floss
1. End the arms race

Listing Nine

// todo.h
#ifndef TODO_H
#define TODO_H
#include <string>
#include <iosfwd>   // for istream&, ostream&
struct when {
  int month;    // range 1..12
  int day;      // range 1..31
};
struct to_do {
  when        date;
  int         priority;
  std::string what;
};
int operator<(const to_do& td1, const to_do& td2);
int operator>(const to_do& td1, const to_do& td2);
std::istream& operator>>(std::istream& in,  to_do& td);
std::ostream& operator<<(std::ostream& out, const to_do& td);
#endif

Listing Ten

#include <string>
#include <fstream>
#include <vector>
#include <algorithm>    // for sort()
#include "todo.h"
int main(int argc, char* argv[])
{
  using namespace std;
  ifstream in(argv[1]);
  typedef vector<to_do> ToDo_List;
  ToDo_List td;
  while (in.good()) {
    to_do buf;  in >> buf;  td.push_back(buf);
  }
  typedef ToDo_List::iterator iter;
  for (iter i = td.begin(); i != td.end(); ++i)
    cout << *i << endl;
  sort(td.begin(), td.end());
  cout << "\nSorted:" << endl;
  for (iter j = td.begin(); j != td.end(); ++j)
    cout << *j << endl;
  return 0;
}

Listing Eleven

Input:
Mar 31  3  Get April Fool's jokes
Mar 31  1  Pick up laundry
Jun  3  2  Dentist appointment
Jan  1  1  Stop the arms race
Jun  2  1  Floss
Output:
Jan  1  1  Stop the arms race
Mar 31  1  Pick up laundry
Mar 31  3  Get April Fool's jokes
Jun  2  1  Floss
Jun  3  2  Dentist appointment

Listing Twelve

#include <string>
#include <fstream>
#include <vector>
#include <queue>    // for priority_queue
#include <functional>   // for greater
#include "todo.h"
int main(int argc, char* argv[])
{
  using namespace std;
  ifstream in(argv[1]);
  typedef
    priority_queue< vector<to_do>, greater<to_do> >
      ToDo_List;
  ToDo_List td;
  while (in.good()) {
    to_do buf;  in >> buf;
    td.push(buf);   // sorts as it stores
  }
  while (td.size()) {   // get each item, in sorted order:
    cout << td.top() << endl;
    td.pop();
  }
  return 0;
}
DDJ