Generic algorithms

Perform common classical algorithms such as sorting, searching. Generic in that they work independent of the elements of data.

Although they may depend on element-type operations, overloaded operator< for example.

Algorithms are applied to containers through the iterators that are available to traverse containers.

They operate through the iterators and indeed they are container independent.

Most of the algorithms take one of the following four forms:

alg(beg, end, other args);
alg(beg, end, dest, other args);

alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);

The arguments dest, beg2, and end2, are used to reference a destination, or a second input sequence.

Algorithms makes assumptions about the sizes of those.

Algorithms don’t add elements to a sequence, and generally we need to avoid using iterators in a setting where during the iteration a container is resized.

Here goes an example where we attempt resizing, taken from https://en.wikipedia.org/wiki/Criticism_of_C%2B%2B

This will likely result in a segmentation fault.

#include <iostream>
#include <string>

int main()
{
std::string text = "One\nTwo\nThree\nFour\n";
// Let's add an '!' where we find newlines
for (auto it = text.begin(); it != text.end(); ++it) {
if (*it == '\n') {
// it =
text.insert(it, '!') + 1;
// Without updating the iterator this program has
// undefined behavior and will likely crash
}
}
std::cout << text;
}

Generally the algorithms are generic, but the containers list and forward_list define some algorithms as members.

This is to get better performance for the algorithms that generically make use of random-access iterators:
Sort, merge, remove, reverse, and unique.

The generic algorithms aren’t typically used on associative containers.

It’s not possible to pass those containers to the algorithms that write to or reorder container elements, since the keys are const.
If the algorithm is for reading elements, typically some sort of searching, are likely less efficient than using the container specific functionality.

Algorithm categories

Check out: http://en.cppreference.com/w/cpp/algorithm

Non-modifying sequence operations:
- e.g. find.
Modifying sequence operations:
- E.g. copy.
Partitioning operations:
Sorting operations:
Binary search operations (on sorted ranges):
Set operations (on sorted ranges):
Heap operations:
Minimum/maximum operations:
Numeric operations:
Operations on uninitialized memory: (mostly C++17)
C library:

Complexity

The details on the algorithms at http://en.cppreference.com/w/cpp/algorithm indicate their complexity.

For example:
next_permutation

Complexity: At most N/2 swaps,
where N = std::distance(first, last).#include <algorithm>

#include <string>
#include <iostream>

int main()
{
std::string s = "abcd";
std::sort(s.begin(), s.end());
do {
std::cout << s << '\n';
} while(next_permutation(s.begin(), s.end()));

}

Page updated

Google Sites

Report abuse