ccplusplus.com: February 2014

Wednesday, February 19, 2014

stl auxiliary function

auxiliary iterator functions C++ : Standard Template Library Tutorial, ccplusplus.com

Auxiliary Iterator Functions

The C++ standard library provides three auxiliary functions for iterators: advance(), distance(), and iter_swap(). The first two give all iterators some abilities usually only provided for random access iterators: to step more than one element forward (or backward) and to process the difference between iterators. The third auxiliary function allows you to swap the values of two iterators.

Stepping Iterators Using `advance()`

The function advance() increments the position of an iterator passed as the argument. Thus, it lets the iterator step forward (or backward) more than one element:

Lets the input iterator pos step n elements forward (or backward).
For bidirectional and random access iterators n may be negative to step backward.
Dist is a template type. Normally, it must be an integral type because operations such as <, ++, --, and comparisons with 0 are called.
Note that advance() does not check whether it crosses the end() of a sequence (it can't check because iterators in general do not know the containers on which they operate). Thus, calling this function might result in undefined behavior because calling operator ++ for the end of a sequence is not defined.

Due to the use of iterator traits, the function always uses the best implementation, depending on the iterator category. For random access iterators, it simply calls pos+=n. Thus, for such iterators advance() has constant complexity. For all other iterators, it calls ++pos n times (or --pos, if n is negative). Thus, for all other iterator categories advance() has linear complexity.

To be able to change container and iterator types, you should use advance() rather than operator +=. However, in doing so be aware that you risk unintended worse performance. This is because you don't recognize that the performance is worsening when you use other containers that don't provide random access iterators (bad runtime is the reason why operator += is provided only for random access iterators). Note also that advance() does not return anything. Operator += returns the new position, so it might be part of a larger expression. Here is an example of the use of advance():

In this program, advance() lets the iterator pos step three elements forward and one element backward. Thus, the output is as follows:

Another way to use advance() is to ignore some input for iterators that read from an input stream.

Processing Iterator Distance Using `distance()`

The distance() function is provided to process the difference between two iterators:

Returns the distance between the input iterators pos1 and pos2.
Both iterators have to refer to elements of the same container.
If the iterators are not random access iterators, pos2 must be reachable from pos1; that is, it must have the same position or a later position.
The return type, Dist, is the difference type according to the iterator type:

iterator_traits<InputIterator>::difference_type

By using iterator tags, this function uses the best implementation according to the iterator category. For random access iterators, it simply returns pos2-pos1. Thus, for such iterators distance() has constant complexity. For all other iterator categories, pos1 is incremented until it reaches pos2 and the number of incrementations is returned. Thus, for all other iterator categories distance() has linear complexity. Therefore, distance() has bad performance for other than random access iterators. You should consider avoiding it.

The following example demonstrates its use:

find() assigns the position of the element with value 5 to pos. distance() uses this position to process the difference between this position and the beginning. The output of the program is as follows:

To be able to change iterator and container types, you should use distance() instead of operator-. However, if you use distance() you don't recognize that the performance is getting worse when you switch from random access iterators to other iterators.

To process the difference between two iterators that are not random access iterators, you must be careful. The first iterator must refer to an element that is not after the element of the second iterator. Otherwise, the behavior is undefined. If you don't know which iterator position comes first, you have to process the distance between both iterators to the beginning of the container and process the difference of these distances. However, you must then know to which container the iterators refer. If you don't, you have no chance of processing the difference of the two iterators without running into undefined behavior.

In older versions of the STL, the signature of distance() was different. Instead of the difference being returned, it was added to a third argument. This version was very inconvenient because you could not use the difference directly in an expression. If you are using an old version, you should define this simple workaround:

Here, the return type does not depend on the iterator; it is hard coded as long. Type long normally should be big enough to fit all possible values, however this is not guaranteed.

Swapping Iterator Values Using `iter_swap()`

The following simple auxiliary function is provided to swap the values to which two iterators refer:

Swaps the values to which iterators pos1 and pos2 refer.
The iterators don't need to have the same type. However, the values must be assignable.

Here is a simple example

The output of the program is as follows:

Note that this program normally does not work if you use a vector as a container. This is because ++coll.begin() and --coll.end() yield temporary pointers.

-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

-----------------------------------------------------------------

auxiliary iterator functions c++

auxiliary iterator functions C++ : Standard Template Library Tutorial, ccplusplus.com

Auxiliary Iterator Functions

Stepping Iterators Using `advance()`

The function advance() increments the position of an iterator passed as the argument. Thus, it lets the iterator step forward (or backward) more than one element:

Lets the input iterator pos step n elements forward (or backward).
For bidirectional and random access iterators n may be negative to step backward.
Dist is a template type. Normally, it must be an integral type because operations such as <, ++, --, and comparisons with 0 are called.
Note that advance() does not check whether it crosses the end() of a sequence (it can't check because iterators in general do not know the containers on which they operate). Thus, calling this function might result in undefined behavior because calling operator ++ for the end of a sequence is not defined.

In this program, advance() lets the iterator pos step three elements forward and one element backward. Thus, the output is as follows:

Another way to use advance() is to ignore some input for iterators that read from an input stream.

Processing Iterator Distance Using `distance()`

The distance() function is provided to process the difference between two iterators:

Returns the distance between the input iterators pos1 and pos2.
Both iterators have to refer to elements of the same container.
If the iterators are not random access iterators, pos2 must be reachable from pos1; that is, it must have the same position or a later position.
The return type, Dist, is the difference type according to the iterator type:

iterator_traits<InputIterator>::difference_type

The following example demonstrates its use:

Here, the return type does not depend on the iterator; it is hard coded as long. Type long normally should be big enough to fit all possible values, however this is not guaranteed.

Swapping Iterator Values Using `iter_swap()`

The following simple auxiliary function is provided to swap the values to which two iterators refer:

Swaps the values to which iterators pos1 and pos2 refer.
The iterators don't need to have the same type. However, the values must be assignable.

Here is a simple example

The output of the program is as follows:

Note that this program normally does not work if you use a vector as a container. This is because ++coll.begin() and --coll.end() yield temporary pointers.

-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

-----------------------------------------------------------------

iterator category c++

Iterator Categories C++ : Standard Template Library Tutorial, ccplusplus.com

Iterator Categories

Iterators are objects that can iterate over elements of a sequence. They do this via a common interface that is adapted from ordinary pointers. Iterators follow the concept of pure abstraction: Anything that behaves like an iterator is an iterator. However, iterators have different abilities. These abilities are important because some algorithms require special iterator abilities. For example, sorting algorithms require iterators that can perform random access because otherwise the run-time would be poor. For this reason, iterators have different categories (figure below). The abilities of these categories are listed in table below, and discussed in the following coming posts.

Figure:- Iterator Categories

Table:- Abilities of Iterator Categories
Iterator Category	Ability	Providers
Input iterator	Reads forward	istream
Output iterator	Writes forward	ostream, inserter
Forward iterator	Reads and writes forward
Bidirectional iterator	Reads and writes forward and backward	list, set, multiset, map, multimap
Random access iterator	Reads and writes with random access	vector, deque string, array

Input Iterators

Input iterators can only step forward element-by-element with read access. Thus, they return values elementwise. Table below lists the operations of input iterators.

Note that input iterators can read elements only once. Thus, if you copy an input iterator and let the original and the copy read forward, they might iterate over different values.

Almost all iterators have the abilities of input iterators. However, usually they can have more. A typical example of a pure input iterator is an iterator that reads from the standard input (typically the keyboard). The same value can't be read twice. After a word is read from an input stream (out of the input buffer), the next read access returns another word.

Two input iterators are equal if they occupy the same position. However, as stated previously, this does not mean that they return the same value on element access.

Table:- Operations of Input Iterators
Expression	Effect
*iter	Provides read access to the actual element
iter ->member	Provides read access to a member (if any) of the actual element
++iter	Steps forward (returns new position)
iter++	Steps forward (returns old position)
Iter1 == iter2	Returns whether two iterators are equal
Iter1 != iter2	Returns whether two iterators are not equal
TYPE(iter)	Copies iterator (copy constructor)

You should always prefer the preincrement operator over the postincrement operator because it might perform better. This is because the preincrement operator does not have to return an old value that must be stored in a temporary object. So, for any iterator pos (and any abstract data type), you should prefer

rather than

The same applies to decrement operators, as long as they are defined (they aren't for input iterators).

Output Iterators

Output iterators are the counterparts of input iterators. They can only step forward with write access. Thus, you can assign new values only element-by-element. You can't use an output iterator to iterate twice over the same range. The goal is to write a value into a "black hole" (whatever that means). So, if you write something for the second time at the same position into the same black hole, it is not guaranteed that you will overwrite a previous value. Table below lists the valid operations for output iterators. The only valid use of operator * is on the left side of an assignment statement.

Table:- Operations of Output Iterators
Expression	Effect
*iter = value	Writes value to where the iterator refers
++iter	Steps forward (returns new position)
iter++	Steps forward (returns old position)
TYPE (iter)	Copies iterator (copy constructor)

Note that no comparison operations are required for output iterators. You can't check whether an output iterator is valid or whether a "writing" was successful. The only thing you can do is to write, and write, and write values.

Usually iterators can read and write values. So, as for input iterators, almost all iterators also have the abilities of output iterators. A typical example of a pure output iterator is an iterator that writes to the standard output (for example, to the screen or a printer). If you use two output iterators to write to the screen, the second word follows the first rather than overwriting it. Another typical example of output iterators are inserters. Inserters are iterators that insert values into containers. If you assign a value, you insert it. If you then write a second value, you don't overwrite the first value; you just also insert it.

Forward Iterators

Forward iterators are combinations of input and output iterators. They have all the abilities of input iterators and most of those of output iterators. Table below summarizes the operations of forward iterators.

Table :- Operations of Forward Iterators
Expression	Effect
*iter	Provides access to the actual element
iter-> member	Provides access to a member of the actual element
++iter	Steps forward (returns new position)
iter++	Steps forward (returns old position)
iter1 == iter2	Returns whether two iterators are equal
iter1 != iter2	Returns whether two iterators are not equal
TYPE()	Creates iterator (default constructor)
TYPE(iter)	Copies iterator (copy constructor)
iter1 = iter2	Assigns an iterator

Unlike input iterators and output iterators, forward iterators can refer to the same element in the same collection and process the same element more than once. You might wonder why a forward iterator does not have all of the abilities of an output iterator. One restriction applies that prohibits valid code for output iterators from being valid for forward iterators:

For output iterators, writing data without checking for the end of a sequence is correct. In fact, you can't compare an output iterator with an end iterator because output iterators do not have to provide a comparison operation. Thus, the following loop is correct for output iterator pos:

//OK for output iterators //ERROR for forward iterators while (true) { *pos = foo(); ++pos; }
For forward iterators, you must ensure that it is correct to dereference (access the data) before you do this. Thus, the previous loop is not correct for forward iterators. This is because it would result in dereferencing the end() of a collection, which results in undefined behavior. For forward iterators, the loop must be changed in the following manner:

//OK for forward iterators //IMPOSSIBLE for output iterators while (pos != coll.end()) { *pos = foo(); ++pos; }

This loop does not compile for output iterators because operator ! = is not defined for them.

Bidirectional Iterators

Bidirectional iterators are forward iterators that provide the additional ability to iterate backward over the elements. Thus, they provide the decrement operator to step backward (table below).

Table :- Additional Operations of Bidirectional Iterators
Expression	Effect
-- iter	Steps backward (returns new position)
iter--	Steps backward (returns old position)

Random Access Iterators

Random access iterators are bidirectional iterators that can perform random access. Thus, they provide operators for "iterator arithmetic" (in accordance with the "pointer arithmetic" of ordinary pointers). That is, they can add and subtract offsets, process differences, and compare iterators with relational operators such as < and >. Table lists the additional operations of random access iterators.

Random access iterators are provided by the following objects and types:

Containers with random access (vector, deque)
Strings (string, wstring)
Ordinary arrays (pointers)

Table:- Additional Operations of Random Access Iterators
Expression	Effect
iter[n]	Provides access to the element that has index n
iter+=n	Steps n elements forward (or backward, if n is negative)
iter-=n	Steps n elements backward (or forward, if n is negative)
iter+n	Returns the iterator of the nth next element
n+iter	Returns the iterator of the nth next element
iter-n	Returns the iterator of the nth previous element
iter1-iter2	Returns the distance between iter1 and iter2
iter1<iter2	Returns whether iter1 is before iter2
iter1>iter2	Returns whether iter1 is after iter2
iter1<=iter2	Returns whether iter1 is not after iter2
iter1>=iter2	Returns whether iter1 is not before iter2

The following program demonstrates the special abilities of random access iterators:

#include <vector>
 #include <iostream>
 using namespace std;

int main()
 {
 vector<int> coll;

//insert elements from -3 to 9
 for (int i=-3; i<=9; ++i) {
 coll.push_back (i);
 }

/* print number of elements by processing the distance between beginning and end
 * - NOTE: uses operator -for iterators
 */
 cout << "number/distance: " << coll.end()-coll.begin() << endl;

/* print all elements
 * - NOTE: uses operator < instead of operator ! =
 */
 vector<int>::iterator pos;
 for (pos=coll.begin(); pos<coll.end(); ++pos) {
 cout << *pos << ' '; 
 }
 cout << endl;

/* print all elements
 * - NOTE: uses operator [ ] instead of operator *
 */
 for (int i=0; i<coll.size(); ++i) {
 cout << coll.begin() [i] << ' ';
 }
 cout << endl;

/* print every second element
 * - NOTE: uses operator +=
 */
 for (pos = coll.begin(); pos < coll.end()-1; pos += 2) {
 cout << *pos << ' ';
 }
 cout << endl;
 }

The output of the program is as follows:

This example won't work with lists, sets, and maps because all operations that are marked with NOTE: are provided only for random access iterators. In particular, keep in mind that you can use operator < as an end criterion in loops for random access iterators only.

Note that in the last loop the expression

requires that coll contains at least one element. If the collection was empty, coll.end() -1 would be the position before coll.begin(). The comparison might still work; but, strictly speaking, moving an iterator to before the beginning results in undefined behavior. Similarly, the expression pos += 2 might result in undefined behavior if it moves the iterator beyond the end() of the collection. Therefore, changing the final loop to the following is very dangerous because it results in undefined behavior if the collection contains an even number of elements (figure below):

Figure :- Incrementing Iterators by More than One Element

The Increment and Decrement Problem of Vector Iterators

The use of the increment and decrement operators of iterators includes a strange problem. In general, you can increment and decrement temporary iterators. However, for vectors and strings, you typically can't. Consider the following vector example:

Typically, the compilation of sort() fails. However, if you use, for example, a deque rather than a vector, it will compile. It might compile even with vectors, depending on the implementation of class vector.

The reason for this strange problem lies in the fact that vector iterators are typically implemented as ordinary pointers. And for all fundamental data types, such as pointers, you are not allowed to modify temporary values. For structures and classes, however, it is allowed. Thus, if the iterator is implemented as an ordinary pointer, the compilation fails; if implemented as a class, it succeeds. It always works with deques, lists, sets, and maps because you can't implement iterators as ordinary pointers for them. But for vectors, whether it works depends on the implementation. Usually, ordinary pointers are used. But if, for example, you use a "safe version" of the STL, the iterators are implemented as classes. To make your code portable you should not code as the previous example, using vectors. Instead, you should use an auxiliary object:

The problem is not as bad as it sounds. You can't get unexpected behavior because it is detected at compile time. But it is tricky enough to spend time solving it. This problem also applies to strings. String iterators are usually also implemented as ordinary character pointers, although this is not required.

-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

-----------------------------------------------------------------

Saturday, February 15, 2014

welcome to ccplusplus.com

We are a fast growing company aimed to provide an intelligent and cleaner Technology Solution, a solution that anyone can feel and think. We at ccplusplus are always involved in designing, developing and  providing a better software solution that can be used in any of the area or the field which are governed or not governed by us.

Aiming to spread the Information Technology we are not just limited to software development but we wish to spread our technology as far as we can to each hand. We called this a "Human Being Technology" a technology that can be used and understand by any of the human who has never used or understand the software and its capability.

If we summarize our self, ccplusplus is primarily involved in the following areas of expertise,

Software Solutions
Consultancy Services
Global eLearning Solutions
Education Support

We are team of dedicated engineers who has a passion to develop and innovate. We are not just software engineers, we are the engineers who are passion-ed to change the future of the software !!!!

ccplusplus welcome's all for any kind of suggestions and improvement, we value each of them and seeking to learn from them.

To know us more about our skills please visit us.

Please write to us to let us serve you in a better way.

Thursday, February 13, 2014

Header Files for Iterators

All containers define their own iterator types, so you don't need a special header file for using iterators of containers. However, there are several definitions for special iterators, such as reverse iterators. These are introduced by the <iterator> header file, although you don't need to include this file in your program often. It is needed by containers to define their reverse iterator types and thus it is included by them.

Wednesday, February 12, 2014

Container Types and Members in Detail

Templates Parameter : Standard Template Library Tutorial, ccplusplus.com

Container Types and Members in Detail

This post discusses the different STL containers and presents all of the operations that STL containers provide. The types and members are grouped by functionality. For each type and operation this section describes the signature, the behavior, and the container types that provide it. Possible containers are vector, deques, lists, sets, multisets, maps, multimaps, and strings. In the following subsections, container means the container type that provides the member.

Type Definitions

container::value_type

The type of elements.
For sets and multisets, it is constant.
For maps and multimaps, it is pair <const key-type, value-type>
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::reference

The type of element references.
Typically: container::value_type&.
For vector<bool>, it is an auxiliary class.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::const_reference

The type of constant element references.
Typically: const container::value_type&.
For vector<bool>, it is bool.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::iterator

The type of iterators.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::const_iterator

The type of constant iterators.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::reverse_iterator

The type of reverse iterators.
Provided by vectors, deques, lists, sets, multisets, maps, and multimaps.

container::const_reverse_iterator

The type of constant reverse iterators.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::size_type

The unsigned integral type for size values.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::difference_type

The signed integral type for difference values.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::key_type

The type of the key of the elements for associative containers.
For sets and multisets, it is equivalent to value_type.
Provided by sets, multisets, maps, and multimaps.

container::mapped_type

The type of the value of the elements of associative containers.
Provided by maps and multimaps.

container::key_compare

The type of the comparison criterion of associative containers.
Provided by sets, multisets, maps, and multimaps.

container::value_compare

The type of the comparison criterion for the whole element type.
For sets and multisets, it is equivalent to key_compare.
For maps and multimaps, it is an auxiliary class for a comparison criterion that compares only the key part of two elements.
Provided by sets, multisets, maps, and multimaps.

container::allocator_type

The type of the allocator.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Create, Copy, and Destroy Operations

Containers provide the following constructors and destructors. Also, most constructors allow you to pass an allocator as an additional argument.

container::container ()

The default constructor.
Creates a new empty container.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

explicit container::container (const CompFunc& op)

Creates a new empty container with op used as the sorting criterion.
The sorting criterion must define a "strict weak ordering".
Provided by sets, multisets, maps, and multimaps.

explicit container::container (const container&, c)

The copy constructor.
Creates a new container as a copy of the existing container c.
Calls the copy constructor for every element in c.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

explicit container::container (size_type num)

Creates a container with num elements.
The elements are created with their default constructor.
Provided by vectors, deques, and lists.

container::container (size_type num, const T& value)

Creates a container with num elements.
The elements are created as copies of value.
T is the type of the container elements.
For strings, value is not passed by reference.
Provided by vectors, deques, lists, and strings.

container::container (InputIterator beg, InputIterator end)

Creates a container that is initialized by all elements of the range [beg,end).
This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::container (InputIterator beg, InputIterator end, const CompFunc& op)

Creates a container that has the sorting criterion op and is initialized by all elements of the range [beg,end).
This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
The sorting criterion must define a "strict weak ordering".
Provided by sets, multisets, maps, and multimaps.

container::^~container ()

The destructor.
Removes all elements and frees the memory.
Calls the destructor for every element.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Nonmodifying Operations

Size Operations

size_type container::size () const

Returns the actual number of elements.
To check whether the container is empty (contains no elements), you should use empty() because it may be faster.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

bool container::empty () const

Returns whether the container is empty (contains no elements).
It is equivalent to container:: size()==0, but it may be faster (especially for lists).
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

size_type container::max_size () const

Returns the maximum number of elements a container may contain.
This is a technical value that may depend on the memory model of the container. In particular, because vectors usually use one memory segment, this value may be less than for other containers.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Capacity Operations
size_type container::capacity () const

Returns the number of elements the container may contain without reallocation.
Provided by vectors and strings.

void container::reserve (size_type num)

Reserves internal memory for at least num elements.
If num is less than the actual capacity, this call has no effect on vectors and is a nonbinding shrink request for strings.
To shrink the capacity of vectors.
Each reallocation invalidates all references, pointers, and iterators, and takes some time. Thus reserve() can increase speed and keep references, pointers, and iterators valid.
Provided by vectors and strings.

Comparison Operations
bool comparison (const container& c1, const container&, c2)

Returns the result of the comparison of two containers of same type.
comparison might be any of the following:

operator == operator != operator < operator > operator <= operator >=
Two containers are equal if they have the same number of elements and contain the same elements in the same order (all comparisons of two corresponding elements have to yield true).
To check whether a container is less than another container, the containers are compared lexicographically.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Special Nonmodifying Operations for Associative Containers

The member functions mentioned here are special implementations of corresponding ST. They provide better performance because they rely on the fact that the elements of associative containers are sorted. In fact, they provide logarithmic complexity instead of linear complexity. For example, to search for one of 1,000 elements, no more than ten comparisons on average are needed.

size_type container::count (const T& value) const

Returns the number of elements that are equal to value.
This is the special version of the count() algorithm.
T is the type of the sorted value:
- For sets and multisets, it is the type of the elements.
- For maps and multimaps, it is the type of the keys.
Complexity: linear.
Provided by sets, multisets, maps, and multimaps.

iterator container::find (const T& value)
const_iterator container::find (const T& value) const

Both return the position of the first element that has a value equal to value.
They return end() if no element is found.
These are the special versions of the find() algorithm.
T is the type of the sorted value:
- For sets and multisets, it is the type of the elements.
- For maps and multimaps, it is the type of the keys.
Complexity: logarithmic.
Provided by sets, multisets, maps, and multimaps.

iterator container::lower_bound (const T& value)
const_iterator container::lower_bound (const T& value) const

Both return the first position where a copy of value would get inserted according to the sorting criterion.
They return end() if no such element is found.
The return value is the position of the first element that has a value less than or equal to value (which might be end()).
These are the special versions of the lower_bound() algorithm.
T is the type of the sorted value:
- For sets and multisets, it is the type of the elements.
- For maps and multimaps, it is the type of the keys.
Complexity: logarithmic.
Provided by sets, multisets, maps, and multimaps.

iterator container::upper_bound (const T& value)
const_iterator container::upper_bound (const T& value) const

Both return the last position where a copy of value would get inserted according to the sorting criterion.
They return end() if no such element is found.
The return value is the position of the first element that has a value greater than value (which might be end()).
These are the special versions of the upper_bound() algorithm.
T is the type of the sorted value:
- For sets and multisets, it is the type of the elements.
- For maps and multimaps, it is the type of the keys.
Complexity: logarithmic.
Provided by sets, multisets, maps, and multimaps.

pair<iterator,iterator> container::equal_range (const T& value)
pair<const_iterator,const_iterator> container::equal_range (const T& value) const

Both return a pair with the first and last positions where a copy of value would get inserted according to the sorting criterion.
The return value is the range of elements equal to value.

They are equivalent to:

   make_pair (lower_bound(value),upper_bound(value))

These are the special versions of the equal_range() algorithm.
T is the type of the sorted value:
- For sets and multisets, it is the type of the elements.
- For maps and multimaps, it is the type of the keys.
Complexity: logarithmic.
Provided by sets, multisets, maps, and multimaps.

key_compare container::key_comp ()

Returns the comparison criterion.
Provided by sets, multisets, maps, and multimaps.

value_compare container::value_comp ()

Returns the object that is used as the comparison criterion.
For sets and multisets, it is equivalent to key_comp ().
For maps and multimaps, it is an auxiliary class for a comparison criterion that compares only the key part of two elements.
Provided by sets, multisets, maps, and multimaps.

Assignments

container& container::operator= (const container& c)

Assigns all elements of c; that is, it replaces all existing elements with copies of the elements of c.
The operator may call the assignment operator for elements that have been overwritten, the copy constructor for appended elements, and the destructor of the element type for removed elements.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

void container::assign (size_type num, const T& value)

Assigns num occurrences of value; that is, it replaces all existing elements by num copies of value.
T has to be the element type.
Provided by vectors, deques, lists, and strings.

void container::assign (InputIterator beg, Inputlterator end)

Assigns all elements of the range [beg,end); that is, it replaces all existing elements with copies of the elements of [beg,end).
This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
Provided by vectors, deques, lists, and strings.

void container::swap (container& c)

Swaps the contents with c.
Both containers swap
- their elements and
- their sorting criterion if any.
This function has a constant complexity. You should always prefer it over an assignment when you no longer need the assigned object.
For associative containers, the function may only throw if copying or assigning the comparison criterion may throw. For all other containers, the function does not throw.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

void swap (container& c1, container&, c2)

It is equivalent to c1. swap(c2) (see the previous description).
For associative containers, the function may only throw if copying or assigning the comparison criterion may throw. For all other containers, the function does not throw.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Direct Element Access

reference container::at (size_type idx)
const_reference container::at (size_type idx) const

Both return the element with the index idx (the first element has index 0).
Passing an invalid index (less than 0 or equal to size() or greater than size()) throws an out_of _range exception.
Note that the returned reference may get invalidated due to later modifications or reallocations.
If you are sure that the index is valid, you can use operator [ ], which is faster.
Provided by vectors, deques, and strings.

reference container::operator [ ] (size_type idx)
const_reference container::operator [ ] (size_type idx) const

Both return the element with the index idx (the first element has index 0).
Passing an invalid index (less than 0 or equal to size() or greater than size()) results in undefined behavior. Thus, the caller must ensure that the index is valid; otherwise, at() should be used.
The reference returned for the nonconstant string may get invalidated due to string modifications or reallocations (see page 487 for details).
Provided by vectors, deques, and strings.

T& map::operator [] (const key_type& key)

Operator [ ] for associative arrays.
Returns the corresponding value to key in a map.
Note: If no element with a key equal to key exists, this operation creates a new element automatically with a value that is initialized by the default constructor of the value type. Thus, you can't have an invalid index (only wrong behavior). For example:

map<int,string> coll; coll [77] = "hello"; // insert key 77 with value "hello" cout << coll [42]; // Oops, inserts key 42 with value "" and prints the value
T is the type of the element value.

It is equivalent to:

       
     (*((insert(make_pair(x,T()))).first)).second

Provided by maps.

reference container::front ()
const_reference container::front () const

Both return the first element (the element with index 0).
The caller must ensure that the container contains an element (size ()>0); otherwise, the behavior is undefined.
Provided by vectors, deques, and lists.

reference container::back ()
const_reference container::back () const

Both return the last element (the element with index size()-l).
The caller must ensure that the container contains an element (size()>0); otherwise, the behavior is undefined.
Provided by vectors, deques, and lists.

Operations to Generate Iterators

The following member functions return iterators to iterate over the elements of the containers. Table below lists the iterator category according to the different container types.

Table :- Iterator Categories According to Container Types
Container	Iterator Category
Vector	Random access
Deque	Random access
List	Bidirectional
Set	Bidirectional, element is constant
Multiset	Bidirectional, element is constant
Map	Bidirectional, key is constant
Multimap	Bidirectional, key is constant
String	Random access

iterator container::begin ()
const_iterator container:: begin () const

Both return an iterator for the beginning of the container (the position of the first element).
If the container is empty, the calls are equivalent to container::end().
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

iterator container::end ()
const_iterator container::end () const

Both return an iterator for the end of the container (the position after the last element).
If the container is empty, the calls are equivalent to container: : begin().
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

reverse_iterator container::rbegin ()
const_reverse_iterator container::rbegin () const

Both return a reverse iterator for the beginning of a reverse iteration over the elements of the container (the position of the last element).
If the container is empty, the calls are equivalent to container:: rend().
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

reverse_iterator container::rend ()
const_reverse_iterator container::rend () const

Both return a reverse iterator for the end of a reverse iteration over the elements of the container (the position before the first element).
If the container is empty, the calls are equivalent to container:: rbegin().
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Inserting and Removing Elements

iterator container::insert (const T& value)
pair<iterator,bool> container::insert (const T& value)

Both insert a copy of value into an associative container.
Containers that allow duplicates (multisets and multimaps) have the first signature. They return the position of the new element.
Containers that do not allow duplicates (sets and maps) have the second signature. If they can't insert the value because an element with an equal value or key exists, they return the position of the existing element and false. If they can insert the value, they return the position of the new element and true.
T is the type of the container elements. Thus, for maps and multimaps it is a key/value pair.
The functions either succeed or have no effect.
Provided by sets, multisets, maps, and multimaps.

iterator container::insert (iterator pos, const T& value)

Inserts a copy of value at the position of iterator pos.
Returns the position of the new element.
For associative containers (sets, multisets, maps, and multimaps), the position is only used as hint, pointing to where the insert should start to search. If value is inserted right behind pos the function has amortized constant complexity; otherwise, it has logarithmic complexity.
If the container is a set or a map that already contains an element equal to (the key of) value, then the call has no effect and the return value is the position of the existing element.
For vectors and deques, this operation might invalidate iterators and references to other elements.
T is the type of the container elements. Thus, for maps and multimaps it is a key/value pair.
For strings, value is not passed by reference.
For vectors and deques, if the copy operations (copy constructor and assignment operator) of the elements don't throw, the function either succeeds or has no effect. For all other standard containers, the function either succeeds or has no effect.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

void container::insert (iterator pos, size_type num, const T& value)

Inserts num copies of value at the position of iterator pos.
For vectors and deques, this operation might invalidate iterators and references to other elements.
T is the type of the container elements. Thus, for maps and multimaps it is a key/value pair.
For strings, value is not passed by reference.
For vectors and deques, if the copy operations (copy constructor and assignment operator) of the elements don't throw, the function either succeeds or has no effect. For lists, the function either succeeds or has no effect.
Provided by vectors, deques, lists, and strings.

void container::insert (InputIterator beg, InputIterator end)

Inserts copies of all elements of the range [beg,end) into the associative container.
This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
Provided by sets, multisets, maps, and multimaps.

void container::insert (iterator pos, InputIterator beg, InputIterator end)

Inserts copies of all elements of the range [beg,end) at the position of iterator pos.
This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
For vectors and deques, this operation might invalidate iterators and references to other elements.
For lists, the function either succeeds or has no effect.
Provided by vectors, deques, lists, and strings.

void container::push_front (const T& value)

Inserts a copy of value as the new first element.
T is the type of the container elements.
It is equivalent to insert(begin(), value).
For deques, this operation invalidates iterators to other elements. References to other elements stay valid.
This function either succeeds or has no effect.
Provided by deques and lists.

void container::push_back (const T& value)

Appends a copy of value as the new last element.
T is the type of the container elements.
It is equivalent to insert(end() ,value).
For vectors, this operation invalidates iterators and references to other elements when reallocation takes place.
For deques, this operation invalidates iterators to other elements. References to other elements stay valid.
This function either succeeds or has no effect.
Provided by vectors, deques, lists, and strings.

void list::remove (const T& value)
void list::remove_if (UnaryPredicate op)

remove() removes all elements with value value.
remove_if() removes all elements for which the unary predicate
```
       
   op(elem)
      
```
yields true.
Note that op should not change its state during a function call.
Both call the destructors of the removed elements.
The order of the remaining arguments remains stable.
This is the special version of the remove() algorithm.
T is the type of the container elements.
For further details and examples,
The functions may only throw if the comparison of the elements may throw.
Provided by lists.

size_type container::erase (const T& value)

Removes all elements equal to value from an associative container.
Returns the number of removed elements.
Calls the destructors of the removed elements.
T is the type of the sorted value:
- For sets and multisets, it is the type of the elements.
- For maps and multimaps, it is the type of the keys.
The function does not throw.
Provided by sets, multisets, maps, and multimaps.

void container::erase (iterator pos)
iterator container::erase (iterator pos)

Both remove the element at the position of iterator pos.
Sequence containers (vectors, deques, lists, and strings) have the second signature. They return the position of the following element (or end()).
Associative containers (sets, multisets, maps, and multimaps) have the first signature. They return nothing.
Both call the destructors of the removed elements.
Note that the caller must ensure that the iterator pos is valid. For example:

coll. erase (coll. end()); // ERROR ? undefined behavior
For vectors and deques, this operation might invalidate iterators and references to other elements.
For vectors and deques, the function may only throw if the copy constructor or assignment operator of the elements may throw. For all other containers, the function does not throw.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

void container::erase (iterator beg, iterator end)
iterator container::erase (iterator beg, iterator end)

Both remove the elements of the range [beg,end).
Sequence containers (vectors, deques, lists, and strings) have the second signature. They return the position of the element that was behind the last removed element on entry (or end()).
Associative containers (sets, multisets, maps, and multimaps) have the first signature. They return nothing.
As always for ranges, all elements including beg but excluding end are removed.
Both call the destructors of the removed elements.
Note that the caller must ensure that beg and end define a valid range that is part of the container.
For vectors and deques, this operation might invalidate iterators and references to other elements.
For vectors and deques, the function may only throw if the copy constructor or the assignment operator of the elements may throw. For all other containers, the function does not throw.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

void container::pop_front ()

Removes the first element of the container.
It is equivalent to container. erase (container.begin()).
Note: If the container is empty, the behavior is undefined. Thus, the caller must ensure that the container contains at least one element (size () >0).
The function does not throw.
Provided by deques and lists.

void container::pop_back ()

Removes the last element of the container.
It is equivalent to container.erase(--container.end()), provided this expression is valid, which might not be the case for vectors.
Note: If the container is empty, the behavior is undefined. Thus, the caller must ensure that the container contains at least one element (size()>0).
The function does not throw.
Provided by vectors, deques, and lists.

void container::resize (size_type num)
void container::resize (size_type num, T value)

Both change the number of elements to num.
If size() is num on entry, they have no effect.
If num is greater than size() on entry, additional elements are created and appended to the end of the container. The first form creates the new elements by calling their default constructor; the second form creates the new elements as copies of value.
If num is less than size() on entry, elements are removed at the end to get the new size. In this case, they call the destructor of the removed elements.
For vectors and deques, these functions might invalidate iterators and references to other elements.
For vectors and deques, these functions either succeed or have no effect, provided the copy constructor or the assignment operator of the elements don't throw. For lists, the functions either succeed or have no effect.
Provided by vectors, deques, lists, and strings.

void container::clear ()

Removes all elements (makes the container empty).
Calls the destructors of the removed elements.
Invalidates all iterators and references to the container.
For vectors and deques, the function may only throw if the copy constructor or the assignment operator of the elements may throw. For all other containers, the function does not throw.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Special Member Functions for Lists

void list:: unique ()
void list::unique (BinaryPredicate op)

Both remove subsequent duplicates of list elements so that each element contains a different value than the following element.
The first form removes all elements for which the previous values are equal.
The second form removes all elements that follow an element e and for which the binary predicate
```
       
   op(elem,e)
      
```
yields true. In other words, the predicate is not used to compare an element with its predecessor; the element is compared with the previous element that was not removed.

Note that op should not change its state during a function call.
Both call the destructors of the removed elements.
These are the special versions of the unique() algorithms.
The functions do not throw if the comparisons of the elements do not throw.

void list::splice (iterator pos, list& source)

Moves all elements of source into *this and inserts them at the position of iterator pos.
source is empty after the call.
If source and *this are identical, the behavior is undefined. Thus, the caller must ensure that source is a different list. To move elements inside the same list you must use the following form of splice().
The caller must ensure that pos is a valid position of *this; otherwise, the behavior is undefined.
This function does not throw.

void list::splice (iterator pos, list& source, iterator sourcePos)

Moves the element at the position sourcePos of the list source into *this and inserts it at the position of iterator pos.
source and *this may be identical. In this case, the element is moved inside the list.
If source is a different list, it contains one element less after the operation.
The caller must ensure that pos is a valid position of *this, sourcePos is a valid iterator of source, and sourcePos is not source. end(); otherwise, the behavior is undefined.
This function does not throw.

void list::splice (iterator pos, list& source, iterator sourceBeg, iterator sourceEnd)

Moves the elements of the range [sourceBeg,sourceEnd) of the list source to *this and inserts it at the position of iterator pos.
source and *this may be identical. In this case, pos must not be part of the moved range, and the elements are moved inside the list.
If source is a different list, it contains less elements after the operation.
The caller must ensure that pos is a valid position of *this, and that sourceBeg and sourceEnd define a valid range that is part of source; otherwise, the behavior is undefined.
This function does not throw.

void list::sort ()
void list::sort (CompFunc op)

Both sort the elements in the list.
The first form sorts all elements in the list with operator <.
The second form sorts all elements in the list by calling op to compare two elements:
```
op(elem1,elem2)

      
```
The order of elements that have an equal value remains stable (unless an exception is thrown).
These are the special versions of the sort() and stable_sort() algorithms,

void list::merge (list& source)
void list::merge (list& source, CompFunc op)

Both merge all elements of the list source into *this.
source is empty after the call.
If *this and source are sorted on entry according to the sorting criterion < or op, the resulting list is also sorted. Strictly speaking, the standard requires that both lists be sorted on entry. In practice, however, merging is also possible for unsorted lists. However, you should check this before you rely on it.
The first form uses operator < as the sorting criterion.
The second form uses op as the optional sorting criterion and is used to compare two elements^[36] :
```
       
op (elem, sourceElem)

      
```
This is the special version of the merge() algorithm.
If the comparisons of the elements do not throw, the functions either succeed or have no effect.

void list::reverse ()

Reverses the order of the elements in a list.
This is the special version of the reverse() algorithm.
This function does not throw.

Allocator Support

All STL containers can be used with a special memory model that is defined by an allocator object. This subsection describes the members for allocator support.

Standard containers require that all instances of an allocator type are interchangeable. Thus, storage allocated from one container can be deallocated via another that has the same type. Therefore, it is no problem when elements (and their storage) are moved between containers of the same type.

Fundamental Allocator Members

container::allocator_type

The type of the allocator.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

allocator_type container::get_allocator () const

Returns the memory model of the container.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

Constructors with Optional Allocator Parameters

explicit container container (const Allocator& alloc)

Creates a new empty container that uses the memory model alloc.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::container (const CompFunc& op, const Allocator& alloc)

Creates a new empty container with op used as the sorting criterion that uses the memory model alloc.
The sorting criterion must define a "strict weak ordering" (see page 176).
Provided by sets, multisets, maps, and multimaps.

container::container (size.type num, const T& value, const Allocator& alloc)

Creates a container with num elements that uses the memory model alloc.
The elements are created as copies of value.
T is the type of the container elements. Note that for strings, value is passed by value.
Provided by vectors, deques, lists, and strings.

container::container (InputIterator beg, InputIterator end, const Allocator& alloc)

Creates a container that is initialized by all elements of the range [beg,end) and uses the memory model alloc.
This function is a member template. Thus, the elements of the source range may have any type that is convertible to the element type of the container.
Provided by vectors, deques, lists, sets, multisets, maps, multimaps, and strings.

container::container (InputIterator beg, InputIterator end, const CompFunc& op, const Allocator& alloc)

Creates a container that has the sorting criterion op, is initialized by all elements of the range [beg,end), and uses the memory model alloc.
This function is a member template (see page 11). Thus, the elements of the source range may have any type that is convertible to the element type of the container.
The sorting criterion must define a "strict weak ordering".
Provided by sets, multisets, maps, and multimaps.

Overview of Exception Handling in STL Containers

As mentioned in earlier post containers provide different guarantees in the face of exceptions. In general, the C++ standard library will not leak resources or violate container invariants in the face of exceptions. However, some operations give stronger guarantees (provided the arguments meet some requirements): They may guarantee commit-or-rollback behavior, or they may even guarantee that they will never throw at all. Table below lists all operations that give these stronger guarantees.

For vectors, deques, and lists, you also have guarantees for resize(). It is defined as having the effect of either calling erase() or calling insert() or doing nothing:

Thus, its guarantees are a combination of the guarantees of erase() and insert().

Table . Container operations with Special Guarantees in Face of Exceptions
Operation		Guarantee
`vector::push_back()`		Either succeeds or has no effect
`vector::insert()`		Either succeeds or has no effect if copying/assigning elements doesn't throw
`vector::pop_back()`		Doesn't throw
`vector::erase()`		Doesn't throw if copying/assigning elements doesn't throw
`vector::clear()`		Doesn't throw if copying/assigning elements doesn't throw
`vector::swap()`		Doesn't throw
`deque::push_back()`		Either succeeds or has no effect
`deque::push_front()`		Either succeeds or has no effect
`deque::insert()`		Either succeeds or has no effect if copying/assigning elements doesn't throw
`deque::pop_back()`		Doesn't throw
`deque::pop_front()`		Doesn't throw
`deque::erase()`		Doesn't throw if copying/assigning elements doesn't throw
`deque::clear()`		Doesn't throw if copying/assigning elements doesn't throw
`deque::swap()`		Doesn't throw
`list::push_back()`		Either succeeds or has no effect
`list::push_front()`		Either succeeds or has no effect
`list::insert()`		Either succeeds or has no effect
`list::pop_back()`		Doesn't throw
`list::pop_front()`		Doesn't throw
`list::erase()`		Doesn't throw
`list:: clear()`		Doesn't throw
`list:: remove()`		Doesn't throw if comparing the elements doesn't throw
`list::remove_if()`		Doesn't throw if the predicate doesn't throw
`list::unique()`		Doesn't throw if comparing the elements doesn't throw
`list::splice()`		Doesn't throw
`list::merge()`		Either succeeds or has no effect if comparing the elements doesn't throw
`list::reverse()`		Doesn't throw
`list::swap()`		Doesn't throw
`[multi]set::insert()`		For single elements either succeeds or has no effect
`[multi]set::erase()`		Doesn't throw
`[multi]set::clear()`		Doesn't throw
`[multi]set::swap()`		Doesn't throw if copying/assigning the comparison criterion doesn't throw
`[multi]map::insert()`		For single elements either succeeds or has no effect
`[multi]map::erase()`		Doesn't throw
`[multi]map::clear()`		Doesn't throw
`[multi]map::swap()`		Doesn't throw if copying/assigning the comparison criterion doesn't throw

-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

-----------------------------------------------------------------

Wednesday, February 19, 2014

Auxiliary Iterator Functions

Stepping Iterators Using advance()

Processing Iterator Distance Using distance()

Swapping Iterator Values Using iter_swap()

Auxiliary Iterator Functions

Stepping Iterators Using advance()

Processing Iterator Distance Using distance()

Swapping Iterator Values Using iter_swap()

Figure:- Iterator Categories

Table:- Abilities of Iterator Categories

Input Iterators

Table:- Operations of Input Iterators

Output Iterators

Table:- Operations of Output Iterators

Forward Iterators

Table :- Operations of Forward Iterators

Bidirectional Iterators

Table :- Additional Operations of Bidirectional Iterators

Random Access Iterators

Table:- Additional Operations of Random Access Iterators

Figure :- Incrementing Iterators by More than One Element

The Increment and Decrement Problem of Vector Iterators

Saturday, February 15, 2014

Thursday, February 13, 2014

Header Files for Iterators

Wednesday, February 12, 2014

Container Types and Members in Detail

Type Definitions

Create, Copy, and Destroy Operations

Nonmodifying Operations

Size Operations

Special Nonmodifying Operations for Associative Containers

Assignments

Direct Element Access

Operations to Generate Iterators

Table :- Iterator Categories According to Container Types

Inserting and Removing Elements

Special Member Functions for Lists

Allocator Support

Fundamental Allocator Members

Constructors with Optional Allocator Parameters

Overview of Exception Handling in STL Containers

Table . Container operations with Special Guarantees in Face of Exceptions

Stepping Iterators Using `advance()`

Processing Iterator Distance Using `distance()`

Swapping Iterator Values Using `iter_swap()`

Stepping Iterators Using `advance()`

Processing Iterator Distance Using `distance()`

Swapping Iterator Values Using `iter_swap()`