C plus plus:Standard Template Library

This is a work in progress. It should probably be split over a few different pages. Everyone feel free to correct or add stuff.

Note: This should really be called Standard Library. The Standard Template Library (STL) is a similar but distinct entity from the parts of it that got included in the C++ Standard Library.

Introduction[]

The C++ language is not a simple language. In fact, many would argue it is a somewhat overcomplicated language. Nevertheless it can be used to write beautiful code. On top of that it is so widespread that example code and libraries (free ones, too) are all over the Internet.

To be able to write working programs in C++, you'll need a decent grasp of the subtleties of the language itself. That is not what this article is about, look at the C++ resource section for that. On top of understanding the language, it helps tremendously to be able to use the standard library correctly. That is what this article is about. You'd be surprised how many people program in C++ but ignore most of its features. That is not necessarily a bad way to program, but you can save yourself a lot of work by using all of the language.

A reason many people avoid the standard library are that they are worried about performance. Especially game developers often suffer from a syndrome where they do not trust any code that they can not mentally compile to assembly instructions on the spot. The conveniences of the standard library and all those templates, they think, just can't be fast. In fact, the whole standard library was designed with performance in mind, and often things will compile to code that is just as efficient as a solution you write yourself. Another very common (and somewhat related) reason not to use standard library functionality is that people refuse to use anything they did not program themselves in their programs. While it is very educational to make everything yourself at least once, if you want to be productive you'll have to start using other people's code, it is available and it is well tested.

The most important parts of the C++ standard library are its containers, iterators, the iostream classes and the algorithms. All classes and functions in the standard library are inside the namespace 'std'.

When passing non-trivial objects to functions or returning them you should get in the habit of passing by reference. This is basic C++ stuff but you really must know this to use standard containers. Do take care not to return references to local objects that will vanish when their scope exits. Also, when you do not intend to modify an object, pass it by const reference, that way temporary objects can be passed, the compiler will complain if you try to pass a temporary object by non-const reference.

All examples in this article use code without indicating any function it is in, and to make things worse I write #include at the same level too. I do this mostly to avoid unneccesary clutter and keep the code readable. This is not valid C++ though, if you want to actually compile it add an 'int main(){ ... }' function around the code (not the includes). C++ Math

I/O Streams[]

Streams provide a convenient way to do input and output. While code using streams is actually quite a bit more ugly than equivalent code using printf-like functions, the added type-safety and flexibility are worth the extra clutter in my opinion.

The bitshift operators << and >> have been overloaded to mean stream insertion and extraction. You can put objects into a stream with <<, and read them out with >>:

include <iostream>

int main() {

   // write text and number to the standard output 
   std::cout << "Hi " << 8 << '\n' << "Enter a number: ";
   int a_number; // define a varible
   std::cin >> a_number; // write input from the keybord into the varible
   std::cout << "You entered " << a_number << '\n'; // write out the result to the screen

}

As you can see, extractions and insertions can follow each other without putting the stream (std::cout) in front of every '<<' or '>>'. The trick is that a stream operation returns a reference to the stream it was performed on, and the next operation will be performed on the return value of the previous one.

The example given here is actually quite ramshackle. If you enter text that is not a number it will mess up. Streams have flags that indicate whether they are still in working order. You can check whether an operation on a stream failed with the fail() member function, and you can see whether an input stream is at the end of file with the eof() member function. The eof state will only be set after something has been read past the end of file though, so you should check it immediately after reading something and not use the output if the stream is now at end of file.

The << and >> operators work with text input and output. To do binary I/O some other functions are available. Say instream and outstream are an input and an output stream.

// put one char into an output stream outstream.put('a'); const char* data = Get_Binary_Data(); // write 20 bytes of data to the stream outstream.write(data, 20);

// get one char from an input stream char byte = instream.get() char buffer[100]; // read 100 bytes from the stream. instream.read(buffer, 100);

As you might have guessed, std::cin and std::cout are handles to the standard input and output streams. For the error stream, std::cerr exists. There are two other kinds of useful streams: file streams and string streams.

File streams[]

File streams are used to read and write files. The convenient thing about them is that they close their files when they get destructed, so you won't have to worry about that.

include <fstream>

// open a file, std::ios::binary can be added as second argument for
// binary input
std::ifstream input_file("file.txt");
// this is a standard string object
std::string buffer;
// read one line from an input file
std::getline(input_file, buffer);
// an output file stream. the optional second argument can be
// std::ios::binary, std::ios::app for appending to a file, both
// (use binary or ('|') to combine them), or nothing
std::ofstream output_file("hi.txt", std::ios::app);
output_file << "Adding some text\n";

// at end of scope the files are closed

String streams[]

A string stream is a stream writing to or reading from a string. A common use for these is reading number from or writing numbers to strings.

include <sstream>

std::istringstream fifty_five("55");
int result;
fifty_five >> result;

std::ostringstream output; output << "Today's lucky number is " << 55 << '\n'; // use the str member function to get a string representation std::string message = output.str();

Formatting Streams[]

If you wish to use streams as a total replacement for *printf, you will probably wish to apply formatting to numerical data you're inserting into the streams. This is done with the <iomanip> header. The manipulators defined in that header allow you to set flags that control the base, precision and fill character for that particular stream.

Containers[]

The standard containers implement a number of common data structures as templated classes. If you do not know how templates work, go look it up first. Not all classes can safely be stored in standard containers! If a class contains any data that needs bookkeeping to construct or destroy (pointers to data that it owns for example), you must make sure the class has a proper copy constructor, assignment operator and destructor.

Note that containers that allow subscripting start at 0 the same way normal arrays do.

Strings[]

C-style, null-terminated character arrays never were a lot of fun, and with C++ strings they become something that you can mostly avoid dealing with.

// You have to have the word 'foo' in every programming tutorial. std::string text("foo"); // The same goes for 'bar'. Note the easy concatenation. text += "bar"; // This will only work if there is a standard string object on one // side of the '+' : "ab" + "cd" is incorrect since it tries to add pointers

// Find returns the index of the first occurence of a substring, starting // at the position indicated with the second argument (defaults to 0). If // the substring is not found it returns string::npos (which you can also // access as text.npos, if you find that clearer ). int find_b = text.find("b"); // This finds the first occurence of any of the characters that occur in // the argument. find_d = text.find_first_of("Bb");

// You can get a C-style string representation by using c_str(), // which returns a char const *. // File streams cannot take a std::string as a filename in C++03, which // is a defect that will be remedies in the next standard revision. std::ifstream foobar_file(text.c_str());

Vector[]

Vector is the simplest of the standard containers. It is basically a dynamic array, an array that can grow and shrink. This means that you can efficiently access any element in a vector. Adding stuff to the end, effectively making it bigger, is more expensive - sometimes the vector will have to be reallocated and its contents will have to be copied.

include <vector>
include <iostream>

// An empty vector of integers:
std::vector<int> test;
// Add five to the end:
test.push_back(5);
// You can access vector element like array elements:
std::cout << test[0] << std::endl;
// The member function at also accesses elements, it also checks
// bounds, which makes it safer. the size member function gives the
// number of elements in the vector.
std::cout << test.at(0) << ' ' << test.size() << std::endl;
// Back returns a reference to the last element in the vector.
int i = test.back();
// Pop_back removes the last element, the vector is now empty again.
test.pop_back();

// The constructor of vector takes two (optional) arguments, the // initial size of the vector and the value to which the initial // elements should be initialized. std::vector<int> two(8, i); // vector elements can be assigned to two[4] = 57;

std::vector is extremely fast for random access to individual members (like v[10]), because all elements are stored in one big block, but it can take long (in comparison to alternatives) to add elements to the vector, because if the current block isn't big enough to hold all elements, the memory has to be reallocated. This causes another problem: If you use a pointer to a vector-element like this: std::vector<char> v(256, '\0'); std::strncpy( &v[0], "Hello World!", v.size()-1 ); you have to be aware that the pointer is only valid until an element is added or removed to/from the vector. It might still work (memory is not reallocated every time the vector changes), but you can't rely on that. This can cause bugs that are extremely hard to track down. Best don't store pointers to vector-elements at all. Keep in mind that every call to "push_back", "insert", "reserve", or "resize" on a vector that results in a capacity increase invalidates all pointers into its memory and all C_plus_plus:Standard_Template_Library#Iterators. Fortunately, a vector will never shrink, so functions that release elements don't cause these problems.

List[]

List implements doubly-linked lists. These are more efficient than vectors when elements have to be added and removed in the middle of the list. If you're wondering how linked lists work, the linked list article has a description.

include <list>

std::list<int> test;
// Like with vector, you can push and pop stuff on the back of the
// list, but you can do the same on the front.
test.push_back(4);
test.push_front(3);
test.pop_front();

// Get the current size (1) test.size();

Lists get much more versatile once you understand iterators; we'll get back to them later.

Note that lists would require O(n) complexity to implement operator[], so it not offered.

Maps[]

Maps are used to associate objects of one type with objects of another type. For example you want to map integers to strings. Sometimes containers of this type are called associative arrays.

include <map>
include <iostream>

std::map<int, std::string> test;
// If you access an element that has not yet been set, the default
// constructor of the 'target' type is called to create a value, in
// this case an empty string is found.
std::cout << test[8] << '\n';
// You can assign like this:
test[2] = "string two";
// Now test[2] contains a value.
std::cout << test[2] << '\n';

// All containers support size() test.size();

Iterators[]

Iterators appear in many programming languages as a convenient way to traverse some kind of collection or range. They take an important place in the C++ standard library as a way to traverse containers or streams. You can do other fancy stuff with them, but this article will only concern itself with 'forward iterators' and their most common uses.

If you are familiar with plain-C programming style, you probably know the method of using a pointer to traverse an array.

include <iostream>

int array[30];
// Fill array somehow
int* end_of_array = array + 30;
for (int* current = array; current != end_of_array; ++current)

 std::cout << *current << '\n';

The iterators in the standard library work much the same way, you get an end and a beginning of a collection, and starting from the beginning you increment the iterator until you arrive at the end.

include <vector>
include <iostream>

std::vector<int> array(30);
// fill array
std::vector<int>::iterator end_of_array = array.end();
for (std::vector<int>::iterator current = array.begin(); current != end_of_array; ++current)

 std::cout << *current << '\n';

In fact, iterators in vectors or strings could be implemented as plain pointers in your version of the standard library. Iterators in other containers, like lists and maps, have to be smarter. They are objects which have their '++', '*' (dereference) and '->' operator overloaded to behave this way, and behind the scenes they do what is necessary to go to the next element or fetch an element. If you replace the vector with a map in the previous example the loop should still work.

Besides using them to traverse a container iterators can also be used to indicate a position in a container. To insert things in the middle of a list you first obtain an iterator to the position where you want to insert the element (an iterator pointing to the element before which you want to insert something), and then do my_list.insert(my_iterator, my_value) to insert the element. In the same way, my_list.erase(my_iterator) erases the element to which my_iterator is pointing (note that you can not use the iterator after erasing it). See find in the algorithms section for a convenient way of getting iterators pointing to specific elements in containers.

Iterators in maps are a little odd, they do not point to values but to std::pair objects, which contain a key and a value. Pairs are structs with a first and a second field, in this case the key is in my_iterator->first and the value is in my_iterator->second.

Algorithms[]

In the <algorithm> header a number of useful utility functions, ranging from the trivial to the complex, are defined.

include <algorithm>

int x = std::max(5, 6), y = std::min(8, 1);
std::swap(x, y);
std::vector<int> bigvector;
// ... some code filling bigvector with lots of stuff ...
std::vector<int>::iterator iter = std::find(bigvector.begin(), bigvector.end(), 5);

// iter will equal bigvector.end() if the element is not found, // otherwise it will point to the first 5 in the vector. if( iter != bigvector.end() ) { //value was found } else { //value was not found }

Min, max and swap are convenient because they are template functions, they work on any type that has the neccessary operations defined.

Find is somewhat easier than iterating through a container yourself, but the ugly syntax surrounding iterators does kind of hamper it. If you typedef your containers (for example int_vec instead of std::vector<int>, this gets somewhat better. Containers that keep elements in some kind of order (std::set and std::map for example) have a member function find which is more efficient.

The algorithm header contains a lot more functions, many of them doing something convenient with containers, but they are usually not very intuitive to use.