stl auxiliary function

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:

#include <iterator> void advance (InputIterator& pos, Dist n)

• 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():

#include <iostream> #include <list> #include <algorithm> using namespace std; int main() { list<int> coll; //insert elements from 1 to 9 for (int i=1; i<=9; ++i) { coll.push_back(i); } list<int>::iterator pos = coll.begin(); //print actual element cout << *pos << endl; //step three elements forward advance (pos, 3); //print actual element cout << *pos << endl; //step three elements backward advance (pos, -1); //print actual element cout << *pos << endl; }

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

1 4 3

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:

#include <iterator> Dist distance (InputIterator pos1, InputIterator pos2)

• 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:

#include <iostream> #include <list> #include <algorithm> using namespace std; int main() { list<int> coll; //insert elements from -3 to 9 for (int i=-3; i<=9; ++i) { coll.push_back(i); } //search element with value 5 list<int>::iterator pos; pos = find (coll.begin(), coll.end(), //range 5); //value if (pos != coll.end()) { //process and print difference from the beginning cout << "difference between beginning and 5: " << distance(coll.begin(),pos) << endl; } else { cout << "5 not found" << endl; } }
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:

difference between beginning and 5: 8

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:

template <class Iterator> inline long distance (Iterator pos1, Iterator pos2) { long d = 0; distance (pos1, pos2, d); return d; }
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:

#include <algorithm> void iter_swap (ForwardIterator1 pos1, ForwardIterator2 pos2)

• 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 

#include <iostream> #include <list> #include <algorithm> #include "print.hpp" using namespace std; int main() { list<int> coll; //insert elements from 1 to 9 for (int i=1; i<=9; ++i) { coll.push_back(i); } PRINT_ELEMENTS(coll); //swap first and second value iter_swap (coll.begin(), ++coll.begin()); PRINT_ELEMENTS(coll); //swap first and last value iter_swap (coll.begin(), --coll.end()); PRINT_ELEMENTS(coll); }

The output of the program is as follows:

1 2 3 4 5 6 7 8 9 2 1 3 4 5 6 7 8 9 9 1 3 4 5 6 7 8 2

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:
-----------------------------------------------------------------

• Complete Tutorial of C++ Template's
• Standard Template Library Tutorial
• Inter Process Communication Tutorial
• Advance Programming in C & C++

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

The Art of Learning with Innovation,
eLearning Courses for C and C++ Programming Language - The Most appreciated course !!!

Copyright © ccplusplus.com