Components

Iterator Algorithms

Free Trial

The Iterator Algorithms component contains parallel versions of many common algorithms that operate on ranges of iterators. It contains the same methods as the Array Algorithms component, but the methods operate on iterators.

Iterators are the most important innovation in generic libraries because they decouple algorithms from the data structures. These concepts make it possible to reuse existing algorithms with new data structures and existing data structures with new algorithms. Iterators, along with function objects, allow even a simple algorithm to be reused in very diverse contexts.

You can use PTL iterator algorithms with PTL Containers and Persistent Containers components. You can also design your own containers that work with PTL iterator algorithms by implementing the Iterator interfaces from the Progeneric.PTL.Interfaces component. The Interfaces component is bundled with the Iterator Algorithms component, and you can view its online documentation for more information.

Algorithms are grouped into the following static classes based on their actions on data structures. Therefore, it is easy to use and memorize them.

Class Algorithms Example Methods
Algobase Basic algorithms that operate on ranges of iterators. Compare, Copy, Count, Equal, ForEach, LexicographicalCompare, Max, Min, Mismatch, Swap, Transform
AlterOper Algorithms that modify some of the elements that iterators point to. Fill, Remove, Replace
HeapOper Basic operations of a heap data structure. IsHeap, MakeHeap, PopHeap, PushHeap, SortHeap
NumericOper Algorithms that are generalizations of basic numeric operations. Accumulate, AdjacentDifference, InnerProduct, PartialSum
ReorderOper Algorithms that put the elements of the input range into a different order without changing, eliminating or introducing elements. Arrangements, Combinations, Factorial, NextPermutation, Partition, PrevPermutation, RandomSample, RandomShuffle, Reverse, Rotate, StablePartition
SearchOper Algorithms that return information about the elements in the range without changing the elements. AdjacentFind, BinarySearch, EqualRange, Find, LowerBound, Search, UpperBound
SetOper Basic operations of set theory. Except, Includes, Intersect, SymmetricExcept, Union
SortOper Algorithms that sort ranges or operate on sorted ranges of iterators. InplaceMerge, IsSorted, Merge, PartialSort, Sort, StableSort
TestOper Algorithms that test ranges of iterators. Any, Equal, None

Algorithms operate on a linear range of elements [first, last). This notation comes from mathematics. It is written in this asymmetric form to emphasize that [first, last) is a half-open interval that includes first but not last. A range [first, last) is valid if all the iterators in [first, last) are dereferenceable (have an associated value) and if last is reachable from first.

Better by Design:

  • Algorithms are designed by assuming as little as possible, without loss of efficiency. This means that algorithms work with as many different kinds of iterators as possible.
  • All algorithms are very efficient and can compete with the performance of their non-generic counterparts. We do not abstract an algorithm in such a way that it becomes inefficient when you instantiate it back.
  • The majority of algorithms have a parallel version that scales linearly with the number of cores, particularly for ranges with a large number of elements. The only difference between the sequential and parallel version is in the name; the parallel version is prefixed with "P" (e.g. Sort vs. PSort, Copy vs. PCopy).
  • The user is completely isolated from parallel programming pitfalls: threads, locks, race conditions, cache coherency, etc.