<$BlogRSDUrl$>

Thursday, July 13, 2006

STL


INTRO
-----------

Containers
----------
onedimensional array of T §16.3
doublylinked list of T §17.2.2
doubleended queue of T §17.2.3
queue of T §17.3.2
stack of T §17.3.1
associative array of T §17.4.1
set of T §17.4.3
array of booleans §17.5.3

The associative containers map and set can be found in and respectively
The priority_queue is declared in .


General Utilities
-----------------
operators and pairs §17.1.4, §17.4.1.2
function objects §18.4
allocators for containers §19.4.4
Cstyle date and time §s.20.5

The header also contains the auto_ptr template that is primarily used to smooth the
interaction between pointers and exceptions.

Iterators
----------
iterators and iterator support
Iterators provide the mechanism to make standard algorithms generic over the standard containers and similar types (§2.7.2,

Algorithms
----------
general algorithms
bsearch() qsort()

A typical general algorithm can be applied to any sequence (§3.8, §18.3) of any type of elements.
The C standard library functions bsearch() and qsort() apply to builtin arrays with elements of
types without userdefined copy constructors and destructors only (§7.7).

Diagnostics
-----------
exception class §14.10
standard exceptions §14.10
assert macro §24.3.7.2
Cstyle error handling

Strings
-------
string of T Chapter 20
character classification §20.4.2
widecharacter classification §20.4.2
Cstyle string functions §20.4.1
Cstyle widecharacter string functions §20.4
Cstyle string functions

The header declares the strlen(), strcpy(), etc., family of functions. The
declares atof() and atoi() that convert Cstyle strings to numeric values.

Input/Output
---------------

forward declarations of I/O facilities §21.1
standard iostream objects and operations §21.2.1
iostream bases §21.2.1
stream buffers §21.6
input stream template §21.3.1
output stream template §21.2.1
manipulators §21.4.6.2
streams to/from strings §21.5.3
character classification functions §20.4.2
streams to/from files §21.5.1
printf() family of I/O §21.8
printf()­style I/O of wide characters §21.8

Manipulators are objects used to manipulate the state of a stream (e.g., changing the format of
floatingpoint output) by applying them to the stream.

Localization
-------------
represent cultural differences §21.7
represent cultural differences Cstyle

Language Support
-------------------
numeric limits §22.2
Cstyle numeric scalarlimit macros §22.2.1
Cstyle numeric floatingpoint limit macros §22.2.1
dynamic memory management §16.1.3
runtime type identification support §15.4.1
exceptionhandling support §14.10
C library language support §6.2.1
variablelength function argument lists §7.6
Cstyle stack unwinding §s.18.7
program termination §9.4.1.1
system clock §s.18.7
Cstyle signal handling §s.18.7

Numerics
---------
< complex> complex numbers and operations §22.5
< valarray> numeric vectors and operations §22.4
< numeric> generalized numeric operations §22.6
< cmath> standard mathematical functions §22.3
< cstdlib> Cstyle random numbers

For historical reasons, abs(), fabs(), and div() are found in rather than in
with the rest of the mathematical functions (§22.3).

The base() function returns an iterator corresponding to the reverse iter.

The members front() and back() return references to the first and last element, respectively.
They are most useful where these elements are known to exist and in code where these elements are
of particular interest. A vector used as a stack (§16.3.5) is an obvious example. Note that front()
returns a reference to the element to which begin() returns an iterator. I often think of front() as
the first element and begin() as a pointer to the first element. The correspondence between
back() and end() is less simple: back() is the last element and end() points to the lastplusone
element position.

If a type does not have a default constructor, it is not possible to create a vector with elements
of that type without explicitly providing the value of each element. For Example :-

class Num{ / / infinite precision
public:
Num(long) ;
// no default constructor
};

vector v1(1000) ; / / error: no default Num
vector v2(1000,Num(0)) ; / / ok


class Num{ / / infinite precision
public:
Num(long) ;
/ / no default constructor
/ / ...
};
vector v1(1000) ; / / error: no default Num
vector v2(1000,Num(0)) ; / / ok

class Num{ / / infinite precision
public:
Num(long) ;
/ / no default constructor
/ / ...
};
vector v1(1000) ; / / error: no default Num
vector v2(1000,Num(0)) ; / / ok

The copy constructor and the copyassignment operators copy the elements of a vector. For a
vector with many elements, that can be an expensive operation, so vectors are typically passed by
reference.

vector v(10,´x´) ; / / v.size()==10, each element has the value ’x’
v.assign(5,´a´) ; / / v.size()==5, each element has the value ’a’

When an algorithm returns an iterator, that iterator is of
the same type as one of its inputs. In particular, an algorithm’s arguments control whether it
returns a const_ iterator or a nonconst
iterator. For example:
void f(list& li, const list& ls)
{
list: :iterator p = find(li.begin() ,li.end() ,42) ;
list: :const_ iterator q = find(ls.begin() ,ls.end() ,"Ring") ;
}


Non Modifying Algos
-----------------------
for_each() Do operation for each element in a sequence.
find() Find first occurrence of a value in a sequence.
find_if() Find first match of a predicate in a sequence.
find_first_of() Find a value from one sequence in another.
adjacent_find() Find an adjacent pair of values.
count() Count occurrences of a value in a sequence.
count_if() Count matches of a predicate in a sequence.
mismatch() Find the first elements for which two sequences differ.
equal() True if the elements of two sequences are pairwise equal.
search() Find the first occurrence of a sequence as a subsequence.
find_end() Find the last occurrence of a sequence as a subsequence.
search_n() Find the nth occurrence of a value in a sequence. _


Modifying Algos
-------------------
transform() Apply an operation to every element in a sequence.
copy() Copy a sequence starting with its first element.
copy_backward() Copy a sequence starting with its last element.
swap() Swap two elements.
iter_swap() Swap two elements pointed to by iterators.
swap_ranges() Swap elements of two sequences.
replace() Replace elements with a given value.
replace_if() Replace elements matching a predicate.
replace_copy() Copy sequence replacing elements with a given value.
replace_copy_if() Copy sequence replacing elements matching a predicate.
fill() Replace every element with a given value.
fill_n() Replace first n elements with a given value.
generate() Replace every element with the result of an operation.
remove_copy() Copy a sequence removing elements with a given value.
remove_copy_if() Copy a sequence removing elements matching a predicate.
unique() Remove equal adjacent elements.
unique_copy() Copy a sequence removing equal adjacent elements.
reverse() Reverse the order of elements.
reverse_copy() Copy a sequence into reverse order.
rotate() Rotate elements.
rotate_copy() Copy a sequence into a rotated sequence.
random_shuffle() Move elements into a uniform distribution.
generate_n() Replace first n elements with the result of an operation.
remove() Remove elements with a given value.
remove_if() Remove elements matching a predicate.

Sorted Sequences
-----------------
sort() Sort with good average efficiency.
stable_sort() Sort maintaining order of equal elements.
partial_sort() Get the first part of sequence into order.
partial_sort_copy() Copy getting the first part of output into order.
nth_element() Put the nth element in its proper place.
lower_bound() Find the first occurrence of a value.
upper_bound() Find the first element larger than a value.
equal_range() Find a subsequence with a given value.
binary_search() Is a given value in a sorted sequence?
merge() Merge two sorted sequences.
inplace_merge() Merge two consecutive sorted subsequences.
partition() Place elements matching a predicate first.
stable_partition() Place elements matching a predicate first,preserving relative order.

Set Algorithms
---------------
includes() True if a sequence is a subsequence of another.
set_union() Construct a sorted union.
set_intersection() Construct a sorted intersection.
set_difference() Construct a sorted sequence of elements in the first but not the second sequence.
set_symmetric_difference() Construct a sorted sequence of elements in one but not both sequences.


Heap Operations
---------------
make_heap() Make sequence ready to be used as a heap.
push_heap() Add element to heap.
pop_heap() Remove element from heap.
sort_heap() Sort the heap.


Minimum and Maximum
---------------------
min() Smaller of two values.
max() Larger of two values.
min_element() Smallest value in sequence.
max_element() Largest value in sequence.
lexicographical_ compare() Lexicographically first of two sequences. _

Permutations
------------
next_permutation() Next permutation in lexicographical order.
prev_permutation() Previous permutation in lexicographical order. _


In the description of algorithms, the template parameter names are significant. In, Out, For, Bi,
and Ran mean input iterator, output iterator, forward iterator, bidirectional iterator, and randomaccess
iterator, respectively (§19.2.1). Pred means unary predicate, BinPred means binary predicate
(§18.4.2), Cmp means a comparison function (§17.1.4.1, §18.7.1), Op means unary operation,
and BinOp means binary operation (§18.4).

§18.4.4.1 A binder allows a twoargument
function object to be used as a singleargument
function by binding one argument to a value.
§18.4.4.2 A member function adapter allows a member function to be used as an argument to
algorithms.
§18.4.4.3 A pointer to function adapter allows a pointer to function to be used as an argument
to algorithms.
§18.4.4.4 A negater allows us to express the opposite of a predicate.


Collectively, these function objects are referred to as adapters. These adapters all have a common
structure relying on the function object bases unary_ function and binary_ function (§18.4.1). For
each of these adapters, a helper function is provided to take a function object as an argument and
return a suitable function object. When invoked by its operator()(), that function object will
perform the desired action. That is, an adapter is a simple form of a higherorder
function: it takes
a function argument and produces a new function from it:




Predicate??


Map??

This page is powered by Blogger. Isn't yours?