Standard Template Library
—a tutorial
Dr. Thomas Hain
C++ Standard Library
• Language Support Library
C++ language, • Diagnostic Library
as standardized • General Utilities Library
ISO July 1998.
• Strings Library
e.g., • Localization Library
Visual C++ 6.0 • Containers Library
GNU egcs • Iterators Library
SunPro 5.0 • Algorithms Library
C++ Builder 4.0
• Numerics Library
• I/O Library
8/25/03 STL-a tutorial slide 2
What is STL?
1994 ANSI/ISO C++ Standards Committee adopted
STL as part of the Standard C++ Library.
Based on research on generic programming
and generic software libraries by
Alexander Stepanov.
Comprised of:
– composable container classes
– generic algorithms
8/25/03 STL-a tutorial slide 3
Generic programming
Use of software components that are
– widely reusable/adaptable
– algorithms are decoupled from the specific
containers (are not member functions) via
the use of iterators.
– efficient
8/25/03 STL-a tutorial slide 4
STL Components
• Containers
• Generic algorithms
• Iterators
• Function objects
• Adaptors
• Allocators
8/25/03 STL-a tutorial slide 5
Container classes
• (C arrays)
• (strings)
• bitsets
• vectors
• lists
• deques, stacks
• queues, priority queues
• sets, multisets,
• maps, multimaps
• hash_set, hash_multiset
• hash_map, hash_multimap
8/25/03 STL-a tutorial slide 6
Generic algorithms
Broad range of fundamental algorithms for the
most common kinds of data manipulations:
– searching
– sorting
– merging
– copying
– transforming
8/25/03 STL-a tutorial slide 7
Iterators
• Enable algorithms to be generic
– i.e., act on all containers
• Act as intermediaries
between algorithms and containers
• Generalize C++ pointers
• 5 categories
• Enable library to be extended
– new containers
– new algorithms
8/25/03 STL-a tutorial slide 8
ContainersIteratorsAlgorithms
Vector Iterator
Merge Iterator List
istream Iterator
8/25/03 STL-a tutorial slide 9
Iterator types
• Input & Output iterators (==, !=, *i)
– read (->)
– write
– single pass
• Forward iterator (++)
– refinement of above
– multi-pass
– const or mutable
• Bidirectional iterator (--)
• Random access iterator (+, -, +=, -=, [ ], <)
– pointer arithmetic
– subscripting
8/25/03 STL-a tutorial slide 10
i[o]stream_iterator
Copy the elements of a vector to the std output, one per line.
vector<int> v;
// fill ‘er up…
copy(v.begin(), v.end(),
ostream_iterator<int>(cout, "\n"));
Fill a vector with values read from standard input.
vector<int> v;
copy(istream_iterator<int>(cin),
istream_iterator<int>(), back_inserter(v));
8/25/03 STL-a tutorial slide 11
Container types
• Sequence Containers
– vector
– deque
– list
• Sorted Associative Containers
– set, multiset
– map, multimap
• Hashed Associative Containers (unofficial)
– hash_set, hash_multiset
– hash_map, hash_multimap
8/25/03 STL-a tutorial slide 12
Sequence Containers
vector<int, alloc> vec(10);
vector<int> vec(10, 1);
vector<int> vec(lst.begin(), lst.end());
vec.front(); //back
vec.insert(p, 3);
vec.insert(p, 3, 0); //insert 3 0’s
vec.insert(p, lst.begin(), lst.end());
vec.erase(p);
vec.erase(p, q);
vec.clear();
8/25/03 STL-a tutorial slide 13
More on Sequence Containers
bool operator==(const vector&, const vector&)
bool operator<(const vector&, const vector&)
vec.push_back(x); //vec.pop_back();
deq.push_front(x); //pop_front()
vec.size();
vec1 = vec2;
vec1.swap(vec2);
8/25/03 STL-a tutorial slide 14
Sorted Associative Containers
struct ltstr {
bool operator()(const char* s1,const char* s2)const
{ return strcmp(s1, s2) < 0; }
};
const int N = 5;
const char* a[N] = {"ep", "pr", "nu", "ar", "se"};
const char* b[N] = {"th", "ar", "fr", "pr", "is"};
set<const char*, ltstr> A(a, a + N), B(b, b + N), C;
set_union(A.begin(), A.end(), B.begin(), B.end()
, ostream_iterator<const char*>(cout, " ")
, ltstr());
set_difference(A.begin(), A.end()
, B.begin(), B.end()
, inserter(C, C.begin()), ltstr());
8/25/03 STL-a tutorial slide 15
Map / Multimap
Value type is: pair<const key_type, data_type>
map<const char*, int, ltstr> months;
months["january"] = 31; months["february"] = 28;
months["march"] = 31; months["april"] = 30;
months["may"] = 31; months["june"] = 30;
map<const char*, int, ltstr>::iterator cur
= months.find("february");
map<const char*, int, ltstr>::iterator prev = cur;
map<const char*, int, ltstr>::iterator next = cur;
++next; --prev;
cout << "Previous is " << prev->first;
cout << "Next is " << next->first;
8/25/03 STL-a tutorial slide 16
Functors
• Function objects
– an ordinary function, or a function pointer
– an object of a class that defines operator().
• Types
– Generator f()
– Unary Function / Predicate f(x)
– Binary Function / Predicate f(x,y)
• Predefined functors
– arithmetic operations plus, minus, multiplies, divides,
modulus, and negate
– comparisons equal_to, not_equal_to greater, less,
greater_equal, and less_equal
– logical operations logical_and, logical_or, and logical_not
8/25/03 STL-a tutorial slide 17
Functor example 1
Fill a vector with random numbers. In this example, the
function object is simply a function pointer.
vector<int> V(100);
generate(V.begin(), V.end(), rand);
8/25/03 STL-a tutorial slide 18
Functor example 2
Sort a vector of double by magnitude, i.e. ignoring the
elements' signs. In this example, the function object is an
object of a user-defined class.
struct less_mag
: public binary_function<double, double, bool>
{
bool operator()(double x, double y)
{ return fabs(x) < fabs(y); }
};
vector<double> V;
...
sort(V.begin(), V.end(), less_mag());
8/25/03 STL-a tutorial slide 19
Functor example 3
Find the sum of elements in a vector. In this example, the
function object is of a user-defined class that has local state.
struct adder : public unary_function<double, void>
{
adder() : sum(0) {}
double sum;
void operator()(double x) { sum += x; }
};
vector<double> V;
...
adder result = for_each(V.begin(), V.end(), adder());
8/25/03 STL-a tutorial slide 20
Functor example 4
Remove all elements from a list that are greater than
100 and less than 1000.
list<int> lst;
...
list<int>::iterator new_end
= remove_if(lst.begin(), lst.end(),
compose2(logical_and<bool>(),
bind2nd(greater<int>(), 100),
bind2nd(less<int>(), 1000)));
lst.erase(new_end, lst.end());
8/25/03 STL-a tutorial slide 21
Algorithms
Non-mutating algorithms Mutating algorithms
copy Remove
for_each
copy_n remove
find remove_if
copy_backward
find_if remove_copy
swap
adjacent_find remove_copy_if unique
iter_swap
find_first_of swap_ranges unique_copy
count transform reverse
count_if Replace reverse_copy
mismatch replace rotate
equal replace_if rotate_copy
search replace_copy random_shuffle
replace_copy_if random_sample
search_n
fill random_sample_n
find_end
fill_n partition
generate stable_partition
generate_n
8/25/03 STL-a tutorial slide 22
…more algorithms
Sorting Set operations/sorted ranges Minimum and maximum
Sort includes min
sort set_union max
stable_sort set_intersection min_element
partial_sort set_difference max_element
set_symmetric_difference lexicographical_compare
partial_sort_copy
Heap operations lexicographical_compare_3way
is_sorted
push_heap next_permutation
nth_element
pop_heap prev_permutation
Binary search
lower_bound make_heap
upper_bound sort_heap Generalized numeric algorithms
equal_range is_heap iota
binary_search accumulate
merge inner_product
inplace_merge partial_sum
adjacent_difference
power
8/25/03 STL-a tutorial slide 23
Adaptors
• Container adaptors
– create a new container by interface mapping
– queue, stack, priority queue
• Iterator adaptors
– extend the functionality of an existing iterator
– reverse iterators: reverse_iterator
– insert iterators: back_insert, insert
• Functor adaptors
– binder1st, binder2nd, ptr_fun, compose2
pointer_to_unary_function,
pointer_to_binary_function, unary_negate,
binary_negate, unary_compose, binary_compose
8/25/03 STL-a tutorial slide 24
Sample Program using STL
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
const int NUM_AVAIL_QUEST = 30;
const int NUM_TEST_QUEST = 5;
using namespace std ;
void main()
{
vector<int> questions(NUM_AVAIL_QUEST, 1);
partial_sum(questions.begin(), questions.end(), questions.begin());
random_shuffle(questions.begin(), questions.end());
copy(questions.begin(), questions.begin()+ NUM_TEST_QUEST
, ostream_iterator<int>(cout, " "));
}
8/25/03 STL-a tutorial slide 25
References
• A modest STL tutorial
(http://www.cs.brown.edu/people/jak/proglang/cpp/stltut/tut.html)
• Standard Template Library Programmer's Guide
( http://www.sgi.com/tech/stl/)
The C++ Standard Library, by Nicolai M. Josuttis.
Addison-Wesley, 1999
• STL Tutorial and Reference Guide, by David Musser and Atul Saini.
Addison-Wesley, 1996. ISBN 0-201-63398-1.
• The Standard Template Library, by P. J. Plauger, Alexander Stepanov,
Meng Lee, and David Musser. Prentice-Hall. ISBN 0-13-437633-1.
• Using the STL, by Robert Robson. Springer-Verlag, 1998.
• STL Programming from the Ground Up, by Herbert Schildt. Osborne
McGraw-Hill, 1999.
8/25/03 STL-a tutorial slide 26
