• Choose a category
• All
• Classic-Fiction

By Root 1098 0

need. Thus, the best libraries are extensible: They allow clients to adapt and add to the basic capabilities to obtain exactly the functionality they require. The STL is inherently extensible because of its fundamental structure of separating data from the algorithms that operate on them. You can write your own container that can work with the STL algorithms by providing an iterator that conforms to the STL standard. Similarly, you can write a function that works with iterators from the standard containers. This section explains the rules for extending the STL and provides sample implementations of extensions.

Why Extend the STL?

If you sit down to write an algorithm or container in C++, you can either make it adhere to the STL conventions or not. For simple containers and algorithms, it might not be worth the extra effort to follow the STL guidelines. However, for substantial code that you plan to reuse, the effort pays off. First, the code will be easier for other C++ programmers to understand, because you follow well-established interface guidelines. Second, you will be able to use your container or algorithm on the other parts of the STL (algorithms or containers), without needing to provide special hacks or adapters. Finally, it will force you to employ the necessary rigor required to develop solid code.

Writing an STL Algorithm

Chapter 13 describes a useful set of algorithms which are part of the STL, but you will inevitably encounter situations in your programs for which you need new algorithms. When that happens, it is usually not difficult to write your own algorithm that works with STL iterators just like the standard algorithms.

find_all()

Suppose that you want to find all the elements matching a predicate in a given range. The find() and find_if() algorithms are the most likely candidate algorithms, but each returns an iterator referring to only one element. In fact, there is no standard algorithm to find all the elements matching a predicate, but you can write your own version of this functionality called find_all().

The first task is to define the function prototype. You can follow the model established by find_if(). It will be a templatized function on two type parameters: the iterator and the predicate. Its arguments will be start and end iterators and the predicate object. Only its return value differs from find_if(): Instead of returning a single iterator referring to the matching element, find_all() returns a vector of iterators referring to all the matching elements. Here is the prototype:

template

vector

find_all(InputIterator first, InputIterator last, Predicate pred);

Code snippet from WritingAlgorithms\FindAll.cpp

Another option would be to return an iterator that iterates over all the matching elements in the container, but that would require you to write your own iterator class.

The next task is to write the implementation. The find_all() algorithm can be layered on top of find_if() by calling find_if() repeatedly. The first call to find_if() uses the whole supplied range from first to last. The second call uses a smaller range, from the element found with the previous call to last. The loop continues until find_if() fails to find a match. Here is the implementation:

template

vector

find_all(InputIterator first, InputIterator last, Predicate pred)

{

vector res;

while (true) {

// Find the next match in the current range.

first = find_if(first, last, pred);

// check if find_if failed to find a match

if (first == last) {

break;

}

// Store this match.

res.push_back(first);

// Shorten the range to start at one past the current match

++first;

}

return res;

}

Code snippet from WritingAlgorithms\FindAll.cpp

This find_all() implementation creates a local vector to store the result. At the end of the function, this local vector is returned. In C++ prior to C++11 this would require the local vector to be copied. However, since the local