STL stuff

One of the advantages of using STL is that memory management is taken care of for you so "Breech Zeros" shouldn't be a concern.

Data Structures

pair

#include <utility>

pair<T1,T2> is a simple struct that allows you to pair up an object of type T1 with an object of type T2. pair pops up in various STL classes, such as map. make_pair(o1, o2) is a useful function that returns a pair with the objects o1 and o2. Unlike other STL classes, you can directly access the objects in the pair using the `first' and `second' fields. These are not method calls. Here's a silly example that uses a pair of double, and int, makes the pair and then prints out the fields.

#include <iostream>
#include <utility>

using namespace std;

int
main (void)
{
	double d;
	int i;
	pair<double, int> p;

	cin >> d >> i;
	p = make_pair (d, i);

	cout << "double: " << p.first << ", int: " << p.second << endl;
	return 0;
}

Aside from make_pair, there are a few other convenience methods defined. operator==, operator=, operator< are all defined for a pair (assuming that the underlying objects allow for those operations).
p1 < p2 is true if p1.first < p2.first or, if p1.first == p2.first && p1.second < p2.second.
False otherwise.

vector

#include <vector>

STL vector is a generic "array" type that allows you to create an array of anything. The importance of vector is that it will automatically resize itself to accommodate new items. Here's the relevant methods:

• push_back (elt) -- puts a new element at the end of the vector. The vector will resize itself automatically to provide space for the new item.
• pop_back () -- take off the last element.
• back () -- returns the last element in the vector.
• front () -- returns the first element in the vector.
• size () -- tells you how many valid elements are currently in the vector.
• resize (n) -- changes the size of the vector to n. This can truncate data in the vector (i.e., if you do len = v.size () ; v.resize (0); v.resize (len); then don't expect the original data to still be there in the vector).
• operator[] -- accesses a particular element in the vector. The index must be between 0 and size () - 1, inclusive. vector does not perform bounds checking. Also note that this method will not allocate more space for a new element.
• empty() -- returns true if the vector has size 0.
• clear () -- erases all elements in the vector.
• begin () -- return an iterator to first element (see below).
• end () -- return an iterator to just past the last element (see below).

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int
main (void)
{
	vector<pair<int, int>  > pairs;
	pair<int, int> tmp;
	int i;

	while (cin >> tmp.first >> tmp.second) {
		pairs.push_back (tmp);
	}

	/* that while loop can alternatively be done like:
	 int a, b;
	 while (cin >> a >> b)
	        pairs.push_back (make_pair (a, b));
	*/

	for (i = 0; i < pairs.size (); i++) {
		cout << pairs [i].first 
		   << " " << pairs [i].second << endl;
	}

	pairs.resize (0);   //gratuitous resize call...

	return 0;
}

string

#include <string>

string provides your typical character array storage but frees you from dealing with the null terminator and storage issues. string acts like vector<char> (it's a bit more complicated than that, but you get the idea).

• size() -- returns the # of characters in the string
• length() -- same as size()
• empty() -- returns true if the string is empty (could also do == "")
• operator[idx] -- returns character at position idx
• c_str () -- returns a null terminated string with the same contents as the string.
• push_back (ch) -- put the character ch on the end of the string.
• clear () -- deletes the contents of the string (same as resize (0))
• =, +, +=, ==, !=, <, <=, >, >= -- string operators. + concatenates two strings together. The others perform the appropriate comparisons between two strings (on a character by character basis).
• resize (n) -- changes the size of the string to n.
• find (str, pos) -- finds the first occurrence of the string str in *this starting from index pos (pos is optional; if left out, it defaults to 0). Returns the index where you can find str.
• find (ch, pos) -- same as above, but finds the first occurence of the character ch.
• substr (pos, len) -- returns a string that is the substring (of len characters) starting at position pos.
• >> -- the extraction operator can be used to grab strings from input. It will only read up to the first whitespace character.
• begin () -- return iterator to first element (see below).
• end () -- return iterator to just past the last element (see below).

Others:
getline (in, str) -- this isn't a member function of the string class, but rather is "external" to it. This reads off everything (including spaces) from the input stream up to the end of a line. The line is stored in str. The end of line character is not stored in the string, but is removed from the input.

Here's a cheesy example that reads in elements of the form (number,text) and parses them. The elements are separated by spaces.

#include <iostream>
#include <string>

using namespace std;


int
main (void)
{
	int num, s, len;
	string inp, foo;

	while (cin >> inp) {
		s = 1;
		len = 0;

		while (s + len < inp.size () && inp [s + len] != ',')
			len++;
		
		foo = inp.substr (s, len);
		s += len + 1;
		num = atoi (foo.c_str ());
		len = inp.size () - 1 - s;

		foo = inp.substr (s, len);

		cout << "num = " << num << " rest = " 
		     << foo << endl;
	}

	return 0;
}

Iterators

Iterators are "generalized pointers". They provide a generic way of walking a given STL data structure. STL classes, except for the adaptor classes (stack, queue, priority_queue), have a begin () and end () method to provide iterators to you.

The begin () method returns an iterator to the first element. The end () method returns an iterator to just past the end of the data structure. This is important. You can dereference the iterator from begin (), but not from end () because end () doesn't point to any valid data. This is why all algorithms using the iterators operate on a range of iterators starting, and including, the first iterator and going up, but not including the last iterator.

Iterators allow you to walk through a particular data structure. All iterators define the operator++ method to walk forward one element. Most of the STL classes also provide iterators with operator-- defined to go backwards one element. Note the qualification "most". Some classes only provide forward iterators to go forward (slist) and have no way of going backwards. Applying operator-- to the begin () iterator, or operator++ to the end () iterator is undefined. A few classes (such as vector) provide random access iterators which allow you to perform operator+, operator-, operator[] to directly access an element beginning from a particular iterator without having to access the elements in between (this is essentially pointer arithmetic).

Note that when using operator++ or operator-- you should always use the prefix versions (e.g. ++it as opposed to it++). This is for efficiency reasons. The postfix version of the operators will generate a useless copy of the iterator (which may be expensive for a particular implementation).

Iterators are pointers to the data in the object, so you must first dereference the iterator to get at the data.

You declare an iterator by giving the class name (including templated arguments) followed by "::iterator".

Classes that provide iterators also allow for inserting and deleting elements into an object of that class using iterators. The methods are called insert and erase, respectively. You should try to avoid using them for vector as the operations are O(n). In other classes, these operations run much faster (e.g., O(1) for list).

An important issue when using iterators is knowing when the iterators are invalidated (e.g. no longer pointing to correct data). This varies from class to class. In vector, for instance, calling push_back, insert etc. may invalidate iterators. In the list class, however, iterators are valid so long as you don't actually erase the element an iterator is pointing to. If you're not sure when an iterator for a given class is invalidated, then assume any insertion, or deletion operation will invalidate the iterators you currently have. (moral of the story is that, when using iterators to walk through your data structure, you should finish the walk through before doing anything else)

Iterators are very important for calling generic algorithm implementations (such as sort). Such algorithms are passed only the iterators as their arguments.

Here's a cheesy example that reads in 10 numbers into a vector, and then walks the vector using iterators, as opposed to simply stepping through with a for loop:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int
main (void)
{
	int i, f;
	vector<int> nums;

	for (i = 0; i < 10; i++) {
		cin >> f;
		nums.push_back (f);
	}

	vector<int>::iterator cur;

	cur = nums.begin ();

	while (cur != nums.end ()) {
		cout << *cur << " ";
		++cur;
	}

	cout << endl;

	return 0;
}

Functors (or Function Objects)

Functors (or function objects) are objects that have operator() defined. You can treat such objects as if they were a function. Here's an example that creates an object to add one to whatever value you apply it to:

#include <iostream>

using namespace std;

template <typename T>
struct add_one_t {
	T operator () (const T w)
	{
		return (w + static_cast<T> (1));
	}
};

int
main (void)
{
	add_one_t<double> a1;
	double d;

	while (cin >> d)
		cout << a1 (d) << endl;

	return 0;
}

In the STL, functors are often used to provide predicates to determine ordering. Classes such as map and set need to have operator< defined on the objects they store. If the object you're using do not have a defined operator< (or if you want to change the sense of operator<), then you must provide a functor that handles the operation.

Technically, functors you write for use with STL should inherit from the appropriate base functor (unary_function or binary_function) so that the appropriate traits are setup correctly. We'll skip this discussion, however, because in programming competitions, it takes extra time to type in those characters and you get no real benefit.

Certain functors are already defined for you. Some of the useful ones:

#include <functional>

• plus (x,y) -- x + y
• minus (x,y) -- x - y
• multiplies (x,y) -- x * y
• divides (x, y) -- x / y (note that integer division will be performed if the two arguments are integers).
• modulus (x, y) -- x % y
• negate (x) -- -x
• greater (x, y) -- returns true if x > y
• less (x, y) -- true if x < y
• greater_equal (x, y) -- true if x >= y
• less_equal (x, y) -- true if x <= y

map

#include <map>

map rocks! It's a red-black tree that allows you to associate any data type with any other data type. You get to reference the elements as you would arrays. Furthermore, inserting and deleting are really fast (log (N)). All this makes map phenomenally important for competitions.

Declare a map by:

map<key_type, data_type> name;

where key_type and data_type are the types of the keys and data, respectively. key_type must have operator< defined for it. If it doesn't (such as for char*, or structs) then you must provide a functor to handle it (more later).

Relevant methods:

• size() -- returns the size of the map.
• empty () -- returns true if the map has no elements.
• clear () -- erases all elements in the map.
• operator[key] -- looks key up in the map and returns the associated data. Note that if you try to access an element in the map that isn't already in the map, it will be added, and be given default values (either the default constructor for an object, or just 0s in all the bits).
• begin () -- returns an iterator to the first element of the map.
• end() -- returns an iterator to just past the last element.
• insert(elt) -- inserts elt into the map. Note that elt is of type pair<key_type,data_type>. This is equivalent to using operator[elt.first] = elt.second

Internally, map stores the keys and data items as pairs, ordered by the key. A dereference of an iterator, therefore, gives you an object of type pair<key_type,data_type>. Note this also means that walking the map with iterators will give you the elements of the map sorted into ascending order by the key (this is equivalent to a heap sort). This can be a useful tidbit to remember.

Iterators for map are not invalidated by inserts and deletes.

Here's an example that reads in 10 words, counts the number of times they appear in the input, and then waits for the user to input 2 more words and say how many times they appeared in the first 10. Iterators are then used to step through all the elements and print them out. Note that if you run this, enter 10 words, and then ask for 2 more words that weren't included in the first set, you will see them as "0" times. This is because, as mentioned above, if you access the map with a key that doesn't already exist, the key is added with a default value:

#include <iostream>
#include <map>
#include <string>

using namespace std;

int
main (void)
{
	string inp;
	map<string, int> counts;
	int i;

	for (i  = 0; i < 10; i++) {
		cin >> inp;
		counts [inp]++;
	}

	for (i = 0; i < 2; i++) {
		cin >> inp;

		cout << inp << " appeared " << counts [inp]
		     << " times." << endl;
	}

	map<string, int>::iterator cur;

	cur = counts.begin ();

	while (cur != counts.end ()) {
		cout << (*cur).first << " " 
		      << (*cur).second << endl;
		++cur;
	}

	return 0;
}

As said above, the map requires the use of the < operator to maintain the ordering in the map. If the objects you're storing in the map do not have a < operator associated, or it doesn't do what you want, then you must define a functor to pass to the map declaration to provide the needed < operator. For example, the string < operator is case sensitive. If you want to do case insensitive comparisons, then you need to provide a functor. Here's the example from above, but with a functor provided to do case insensitive searches:

#include <iostream>
#include <map>
#include <string>

using namespace std;

struct comp_insens_struct {
	bool operator () (const string &a, const string &b)
	{
		int r;

		r = strcasecmp (a.c_str (), b.c_str ());

		if (r < 0)
			return true;
		else
			return false;
	}
};

int
main (void)
{
	string inp;
	map<string, int, comp_insens_struct> counts;
	int i;

	for (i  = 0; i < 10; i++) {
		cin >> inp;
		counts [inp]++;
	}

	for (i = 0; i < 2; i++) {
		cin >> inp;

		cout << inp << " appeared " 
		     << counts [inp] << " times." << endl;
	}

	map<string, int, comp_insens_struct>::iterator cur;

	cur = counts.begin ();

	while (cur != counts.end ()) {
		cout << (*cur).first << " " 
		     << (*cur).second << endl;
		++cur;
	}

	return 0;
}

If you wanted to reverse the sense of sorting in the map (e.g. sort in descending order instead of ascending order), you could pass the greater functor to the map.

set

#include <set>

Bleh. I'm ambivalent about set for programming competitions. I mention it only for completeness. set provides an object "roughly" corresponding to a mathematical set. Elements added to a set object can only appear in the set once. The reason I don't like set that much is all its functionality (and more) appears in map. The only way to add things to a set is to call insert (which you can do with map). There is no operator[]. Furthermore, generic algorithms that you would think you need a set for (set_difference, set_union, etc) are not defined for the set class; they're defined for any range of iterators whose data has been put into sorted order. So there's not much reason to use set. A map<key_type,int> or map<key_type,bool> would do just as well and may be more convenient to use.

deque

#include <deque>

A deque (pronounced "deck") is a double ended queue. It acts alot like a vector, in that operator[] is O(1), and insertion and deletion at the back are also O(1). The difference is that a deque also supports efficient (O(1)) insertion and deletion at the front. (a vector only supports O(1) insertion and deletion at the back). For some reason, deque doesn't seem to gain as much attention as the other STL classes, even though it's very useful and efficient. Deque is the default underlying class for the adaptor class stack and queue (see below).

Relevant methods:

• push_back (elt) -- puts a new element at the end of the deque. The deque will resize itself automatically to provide space for the new item.
• pop_back () -- take off the last element.
• back () -- returns the last element in the deque.
• push_front (elt) -- inserts a new element at the beginning of the deque. The deque will resize itself if needed to provide space.
• pop_front () -- removes the first element from the deque.
• front () -- returns the first element in the deque.
• size () -- tells you how many valid elements are currently in the deque.
• resize (n) -- changes the size of the deque to n.
• operator[] -- accesses a particular element in the deque. The index must be between 0 and size () - 1, inclusive. deque does not perform bounds checking. Also note that this method will not allocate more space for a new element.
• empty() -- returns true if the deque has size 0.
• clear () -- erases all elements in the deque.
• begin () -- return an iterator to first element.
• end () -- return an iterator to just past the last element.

Be aware that, as with vector, operations that do insertion or deletion may invalidate iterators. Also, inserting something into the middle of the deque (with insert) is a O(N) operation.

Here's an example of using a deque to create a palindrome from any string (note that it's not the minimal palindrome):

#include <iostream>
#include <deque>
#include <string>

using namespace std;

int
main (void)
{
	deque<char> palin;
	int i;
	string inp;

	while (getline (cin, inp)) {
	        palin.resize (0);

		for (i = 0; i < inp.size (); i++) {
			palin.push_front (inp [i]);
			palin.push_back (inp [i]);
		}
		for (i = 0; i < palin.size (); i++) 
			cout << palin [i];

		/* or, with iterators:
		deque<char>::iterator cur;
		
		cur = palin.begin ();

		while (cur != palin.end ()) {
		        cout << *cur;
			++cur;
		}
		*/

		cout << endl;
	}

	return 0;
}

list

#include <list>

A doubly linked list. list supports efficient (O(1)) insertion and removal at the front and back. There is no way of accessing the middle elements without traversing all the elements in front (or behind) them.

An important property of list is that iterators are NOT invalidated by insertion and deletion. Furthermore, elements can be inserted into the list anywhere in O(1) time (although you first have to find that position, which may not be O(1)).

Relevant methods:

• push_front (elt) -- puts element on the front of the list.
• pop_front () -- takes off the first element in the list.
• front () -- returns the first element in the list.
• push_back (elt) -- adds element to the back of the list.
• pop_back () -- removes the last element in the list.
• back () -- returns the last element in the list.
• size () -- returns the number of elements in the list. Note that you should probably NEVER call this method. There is no guarantee that size will be O (1). In fact, it could be O(N) depending on the implementation. (vector and deque will return the size in O(1).)
• empty () -- returns true if the list has no elements.
• clear () -- erases all elements in the list.
• insert (it, elt) -- inserts elt prior to the position given by the iterator it. Note that, unlike other classes, this is an O(1) operation.
• erase (it) -- erases the element at the position given by the iterator it.

Interestingly, list also provides some member functions that perform certain algorithms. These versions are more efficient than performing the generic versions on the list, or are the only version available (the generic sort requires random access iterators, which list does not provide). Remember, these are member functions:

• unique () -- removes all but the first element in every consecutive group of elements that are equal (so the list must be sorted to remove all the duplicates).
• sort () -- an O (N log N) sort. Note that unlike the generic sort (see below), this sort is stable and preserves the order of "equal" items.
• reverse() -- reverses the elements in the list. All iterators will point to the same data after the reverse is performed (this isn't true of the generic reverse (see below)).

Note that any list operation (except erase) will not invalidate iterators. However, the relationships among the iterators may be different (e.g. after reverse member method is called, the previous and next "siblings" of a given iterator will have changed).

Here's an example of using list to (again) create a palindrome from a given string (albeit not the minimal palindrome).

#include <list>
#include <iostream>
#include <string>

using namespace std;

int
main (void)
{
	list<char> palin;
	list<char>::iterator cur;
	int i;
	string inp;

	while (getline (cin, inp)) {
		palin.clear ();

		for (i = 0; i < inp.size (); i++) {
			palin.push_front (inp [i]);
			palin.push_back (inp [i]);
		}

		cur = palin.begin ();

		while (cur != palin.end ()) {
			cout << *cur;
			++cur;
		}

		cout << endl;
	}

	return 0;
}

slist

#include <slist>

slist is a singly linked list. It's similar to list (so much so that I won't bother listing the methods -- they're mostly the same). The difference is that slist does not provide bidirectional iterators. You can only move forward with the iterators of slist. The reason for 2 different list classes is that slist may be more efficient if all you need is a singly linked list. This is an SGI extension and may not be present in all versions of the STL.

The very important difference between list and slist result in the following:

1. There are no push_back, pop_back or back methods for slist.
2. insert and erase should NEVER be called for slist. insert inserts an item in front of the iterator passed to it. There's no way to find this position in an slist object without first going through all the elements in front of it. Similarly, erase returns an iterator to the position just before the one that was erased. Again, this is a linear operation in slist.
3. The slist class defines insert_after and erase_after operations to make up for the problem with insert and erase.

stack

#include <stack>

A generic stack class for use. It's usually more convenient to use this class as opposed to implementing a stack using the appropriate vector operations. Note that stack is adaptor class (its operations are defined as wrappers to the appropriate deque methods). As such, it does not support iterators.

Relevant methods:

• push (elt) -- stick a new element on top of the stack.
• pop () -- removes the most recently pushed element. Note that this does NOT return the element. It just takes the element off. Don't pop an empty stack.
• top () -- Returns the top element off the stack. This doesn't remove the top element. You need pop for that.
• empty() -- returns true if the stack is empty
• size() -- returns the size of the stack.

A cheesy example that reads in words and sees if each word is a palindrome or not. Note that this is an entirely too stupid a way of doing this, but as an example, it's ok (there's a reverse method in the algorithm header that will reverse any given data through its iterators).

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int
main (void)
{
	int i;
	string inp, rev;
	stack<char> ch_stack;

//	ch_stack.pop (); // stupid.  this is Bad Karma and will result
			 // in an unstable stack if you pop an empty stack
			 // (or, more likely, core dump)

	while (cin >> inp) {
		for (i = 0; i < inp.size (); i++) {
			ch_stack.push (inp [i]);
		}

		rev.resize (0);

		while (!ch_stack.empty ()) {
			rev.push_back (ch_stack.top ());
			ch_stack.pop ();
		}

		if (inp == rev)
			cout << "Palindrome" << endl;
		else
			cout << "Not a palindrome" << endl;
	}

	return 0;
}

queue

#include <queue>

A generic queue class to use. This is adaptor class (the underlying class is a deque) and does not support iterators.

• push (elt) -- add a new element to the back of the queue
• pop () -- take off the front of the queue. As with stack, this does NOT return the element. Don't pop an empty queue.
• front () -- returns the first member of the queue (least recently added). Does not remove it.
• back () -- returns the last member of the queue (most recently added).
• empty () -- returns true if the queue is empty
• size () -- returns size of the queue.

Cheesy example that reads elements in, and prints them in the same order.

#include <iostream>
#include <queue>

int
main (void)
{
	queue<int> q;
	int i;

	while (!cin.eof ()) {
		cin >> i;

		if (cin.eof ())
			break;
		
		q.push (i);
	}

	cout << "Size = " << q.size () << endl
	     << "Front elt = " << q.front () << endl
	     << "Last elt = " << q.back () << endl;

	while (!q.empty ()) {
		cout << q.front () << endl;
		q.pop ();
	}

	return 0;
}

Generic Algorithms

In addition to canned implementations of data structures, the STL also provides several useful generic algorithms. The most commonly used ones are listed here. There's a bunch more.

swap

#include <algorithm>

swap (a, b) swaps the elements a and b. This is a very generic version of swapping elements that uses 2 assignment operations and 1 copy constructor invocation. There may be a more efficient method of swapping elements for a given object (a specialized swap is defined for all the container classes like vector, deque and list).

sort

#include <algorithm>

Sort provides an efficient (N log N) sorting algorithm. operator< is used to sort the elements into ascending order. If you want descending order, or if the data stored in the object does not have a default < operator, then you must provide a functor to handle it.

Here's an example that reads in a bunch of numbers and sorts them into descending and ascending order.

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

int
main (void)
{
	vector<int> v;
	int foo, i;

	while (cin >> foo)		
		v.push_back (foo);
	
	sort (v.begin (), v.end ());
	cout << "In ascending order:";

	for (i = 0; i < v.size (); i++) 
		cout << " " << v [i];

	cout << endl;

	sort (v.begin (), v.end (), greater<int> ());

	cout << "In descending order:";

	for (i = 0; i < v.size (); i++) 
		cout << " " << v [i];

	cout << endl;

	return 0;
}

A quick note about the functor used. greater is defined in functional as a functor that takes 2 arguments and returns true if the first is larger than the second. Note how it's passed to the sort call: greater<int>(). You have to instantiate the class and pass the object to the routine. This is different than how one would use greater with, say, map. When passing functors as templated arguments, you don't have to instantiate the functor because the class will take care of that. When passing functors to functions you have to instantiate them first.

stable_sort

#include <algorithm>

One (slight) disadvantage to using sort is that it is not stable, i.e., relative orderings among equal elements are not preserved. For instance, suppose you're sorting a vector of structs that have 3 members, an integer, and 2 strings. You could have data like this:

   10, foo, bar
   15, gi, joe
   10, bar, foo
   1000, bugs, bunny

If you sort that vector and use only the integer as the key for the sort, the results could be:

   10, foo, bar
   10, bar, foo
   15, gi, joe
   1000, bugs, bunny

or

   10, bar, foo
   10, foo, bar
   15, gi, joe
   1000, bugs, bunny

Either one is possible with sort since it's not stable. A stable sort would give the first answer (maintaining the relative order of the elements with the integer).

This isn't usually a big deal. You could get around it by changing the sort routine to use the other members as secondary keys. There are instances where this is not desirable (or possible for that matter). In those cases, there is a stable_sort function defined. It has the same arguments as sort does. One important note, though, is that stable_sort has a different (and more expensive) time complexity so you only want to use it if you have to.

is_sorted

#include <algorithm>

is_sorted returns true if the range of iterators passed to it are in ascending order. You can override the sense of "ascending" by passing a functor as the 3rd argument.

find

#include <algorithm>

find (first, last, val) returns an iterator that points to val if val is found within the range [first, last). Returns last if no such value is found.

unique

#include <algorithm>

unique (first, last) "removes" consecutive duplicates. unique does NOT resize any data structure. Instead, it returns an iterator, it, such that the range [first, it) is unique. All the duplicate elements have been moved into the range [it, last). You can provide a 3rd argument to change the sense of "equal".

Here's an example that uses unique on a vector of values and then prints out all the values just to show that it doesn't remove them:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int
main (void)
{
	vector<int> v;
	vector<int>::iterator it, cur;
	int i, foo;

	while (cin >> foo) 
		v.push_back (foo);

	sort (v.begin (), v.end ());
	it = unique (v.begin (), v.end ());
	cur = v.begin ();

	cout << "the unique elements are:";

	while (cur != it) {
		cout << " " << *cur;
		++cur;
	}

	cout << endl;

	cout << "All the elements are:";

	for (i = 0; i < v.size (); i++)
		cout << " " << v [i];

	cout << endl;
	
	return 0;
}

reverse

#include <algorithm>

reverse (first, last) reverses all the elements in the range [first, last) by using swap. Note that reverse changes the data items, not the iterators.

min, max

#include <algorithm>

min (x,y) returns either x or y, whichever one is smaller. max does the same thing, but returns the larger element. Both can take a 3rd argument that is a predicate functor that determines operator<. Note that the comparisons are done using only <

min_element, max_element

#include <algorithm>

min_element (first, last) returns an iterator pointing to the smallest element in the range [first, last) (max_element does the same except returns the largest element). Both return the first such element. Both can take a functor as the 3rd argument to change the sense of the comparisons.

next_permutation, prev_permutation

#include <algorithm>

These may be useful in competitions. next_permutation (first, last) arranges that data in the range [first, last) such that they form the next lexicographically largest permutation. prev_permutation returns the previous permutation. Both return true if such a permutation is found, false otherwise.

Here's an example that reads in a string and prints out all the permutations.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int
main (void)
{
	string inp;
	
	while (getline (cin, inp)) {
		sort (inp.begin (), inp.end ());

		cout << "the permutations of " << inp << " are: " << endl;

		do {
			cout << " " << inp << endl;
		} while (next_permutation (inp.begin (), inp.end ()));
	}
	
	return 0;
}

Other info