manipulating algorithms stl c++

Manipulating Algorithms

Several algorithms modify destination ranges. In particular, they may remove elements. If this happens, special aspects apply. These aspects are explained in this section. They are surprising and show the price of the STL concept that separates containers and algorithms with great flexibility.

"Removing" Elements

The remove() algorithm removes elements from a range. However, if you use it for all elements of a container it operates in a surprising way. Consider the following example:

#include <iostream> #include <list> #include <algorithm> using namespace std; int main() { list<int> coll; //insert elements from 6 to 1 and 1 to 6 for (int i=1; i<=6; ++i) { coll.push_front(i); coll.push_back(i); } //print all elements of the collection cout << "pre: "; copy (coll.begin(), coll.end(), //source ostream_iterator<int> (cout," ")); //destination cout << endl; //remove all elements with value 3 remove (coll.begin() , coll.end(), //range 3); //value //print all elements of the collection cout << "post: "; copy (coll.begin(), coll.end(), //source ostream_iterator<int> (cout," ")); //destination cout << endl; }

Someone reading this program without deeper knowledge would expect that all elements with value 3 are removed from the collection. However, the output of the program is as follows:

pre: 6 5 4 3 2 1 1 2 3 4 5 6 post: 6 5 4 2 1 1 2 4 5 6 5 6

Thus, remove() did not change the number of elements in the collection for which it was called.

The end() member function returns the old end, whereas size() returns the old number of elements. However, something has changed: The elements changed their order as if the elements were removed. Each element with value 3 was overwritten by the following elements (figure below). At the end of the collection, the old elements that were not overwritten by the algorithm remain unchanged. Logically, these elements no longer belong to the collection.

Figure : How remove () works

However, the algorithm does return the new end. By using it, you can access the resulting range, reduce the size of the collection, or process the number of removed elements. Consider the following modified version of the example:

#include <iostream> #include <list> #include <algorithm> using namespace std; int main() { list<int> coll; //insert elements from 6 to 1 and 1 to 6 for (int i=1; i<=6; ++i) { coll.push_front(i); coll.push_back(i); } //print all elements of the collection copy (coll.begin(), coll.end(), ostream_iterator<int>(cout," ")); cout << endl; //remove all elements with value 3 // - retain new end list<int>::iterator end = remove (coll.begin(), coll.end(), 3); //print resulting elements of the collection copy (coll.begin(), end, ostream_iterator<int>(cout," ")); cout << endl; //print number of resulting elements cout << "number of removed elements: " << distance(end,coll.end()) << endl; //remove "removed'' elements coll.erase (end, coll.end()); //print all elements of the modified collection copy (coll.begin(), coll.end(), ostream_iterator<int>(cout," ")); cout << endl; }

In this version, the return value of remove() is assigned to the iterator end:

list<int>::iterator end = remove (coll.begin(), coll.end(), 3);

This is the new logical end of the modified collection after the elements are "removed." You can use this return value as the new end for further operations:

copy (coll.begin(), end, ostream_iterator<int>(cout," "));

Another possibility is to process the number of "removed" elements by processing the distance between the "logical" and the real ends of the collection:

cout << "number of removed elements: " << distance(end,coll.end()) << endl;

Here, a special auxiliary function for iterators, distance(), is used. It returns the distance between two iterators. If the iterators were random access iterators you could process the difference directly with operator -. However, the container is a list, so it provides only bidirectional iterators. 

If you really want to remove the "removed" elements, you must call an appropriate member function of the container. To do this, containers provide the erase() member function, erase() removes all elements of the range that is specified by its arguments:

coll.erase (end, coll.end());
Here is the output of the whole program:

6 5 4 3 2 1 1 2 3 4 5 6 6 5 4 2 1 1 2 4 5 6 number of removed elements: 2 6 5 4 2 1 1 2 4 5 6

If you really want to remove elements in one statement, you can call the following statement:

coll.erase (remove(coll.begin(),coll.end(), 3), coll.end());

Why don't algorithms call erase() by themselves? Well, this question highlights the price of the flexibility of the STL. The STL separates data structures and algorithms by using iterators as the interface. However, iterators are an abstraction to represent a position in a container. In general, iterators do not know their containers. Thus, the algorithms, which use the iterators to access the elements of the container, can't call any member function for it.

This design has important consequences because it allows algorithms to operate on ranges that are different from "all elements of a container." For example, the range might be a subset of all elements of a collection. And, it might even be a container that provides no erase() member function (ordinary arrays are an example of such a container). So, to make algorithms as flexible as possible, there are good reasons not to require that iterators know their container.

Note that it is often not necessary to remove the "removed" elements. Often, it is no problem to use the returned new logical end instead of the real end of the container. In particular, you can call all algorithms with the new logical end.

Manipulating Algorithms and Associative Containers

Manipulation algorithms (those that remove elements as well as those that reorder or modify elements) have another problem when you try to use them with associative containers: Associative containers can't be used as a destination. The reason for this is simple: If modifying algorithms would work for associative containers, they could change the value or position of elements so that they are not sorted anymore. This would break the general rule that elements in associative containers are always sorted automatically according to their sorting criterion. So, not to compromise the sorting, every iterator for an associative container is declared as an iterator for a constant value (or key). Thus, manipulating elements of or in associative containers results in a failure at compile time. 

Note that this problem prevents you from calling removing algorithms for associative containers because these algorithms manipulate elements implicitly. The values of "removed" elements are overwritten by the following elements that are not removed.

Now the question arises, How does one remove elements in associative containers? Well, the answer is simple: Call their member functions! Every associative container provides member functions to remove elements. For example, you can call the member function erase() to remove elements:

#include <iostream> #include <set> #include <algorithm> using namespace std; int main() { set<int> coll; //insert elements from 1 to 9 for (int i=1; i<=9; ++i) { coll.insert(i); } //print all elements of the collection copy (coll.begin(), coll.end(), ostream_iterator<int>(cout," ")); cout << endl; /*Remove all elements with value 3 * - algorithm remove() does not work * - instead member function erase() works */ int num = coll.erase(3); //print number of removed elements cout << "number of removed elements: " << num << endl; //print all elements of the modified collection copy (coll.begin(), coll.end(), ostream_iterator<int>(cout," ")); cout << endl; }

Note that containers provide different erase() member functions. Only the form that gets the value of the element(s) to remove as a single argument returns the number of removed elements. Of course, when duplicates are not allowed, the return value can only be 0 or 1 (as is the case for sets and maps).

The output of the program is as follows:

1 2 3 4 5 6 7 8 9 number of removed elements: 1 1 2 4 5 6 7 8 9

Algorithms versus Member Functions

Even if you are able to use an algorithm, it might be a bad idea to do so. A container might have member functions that provide much better performance.

Calling remove() for elements of a list is a good example of this. If you call remove() for elements of a list, the algorithm doesn't know that it is operating on a list. Thus, it does what it does for any container: It reorders the elements by changing their values. If, for example, it removes the first element, all the following elements are assigned to their previous elements. This behavior contradicts the main advantage of lists — the ability to insert, move, and remove elements by modifying the links instead of the values.

To avoid bad performance, lists provide special member functions for all manipulating algorithms. You should always use them. Furthermore, these member functions really remove "removed" elements, as this example shows:

#include <iostream> #include <list> #include <algorithm> using namespace std; int main() { list<int> coll; //insert elements from 6 to 1 and 1 to 6 for (int i=1; i<=6; ++i) { coll.push_front(i); coll.push_back(i); } //remove all elements with value 3 //- poor performance coll.erase (remove(coll.begin(),coll.end(), 3), coll.end()); //remove all elements with value 4 //- good performance coll.remove (4); }

You should always prefer a member function over an algorithm if good performance is the goal. The problem is, you have to know that a member function exists that has significantly better performance for a certain container. No warning or error message appears if you use the remove() algorithm for a list. However, if you prefer a member function in these cases you have to change the code when you switch to another container type. In the reference sections of algorithms.

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