Standard Template Library Programmer's Guide

Find_end is misnamed: it is much more similar to search than to find , and a more accurate name would have been search_end .

Like search , find_end attempts to find a subsequence within the range [first1, last1) that is identical to [first2, last2) . The difference is that while search finds the first such subsequence, find_end finds the last such subsequence. Find_end returns an iterator pointing to the beginning of that subsequence; if no such subsequence exists, it returns last1 .

The two versions of find_end differ in how they determine whether two elements are the same: the first uses operator== , and the second uses the user-supplied function object comp .

The first version of find_end returns the last iterator i in the range [first1, last1 – (last2 – first2)) such that, for every iterator j in the range [first2, last2) , *(i + (j – first2)) == *j . The second version of find_end returns the last iterator i in [first1, last1 – (last2 – first2)) such that, for every iterator j in [first2, last2) , binary_pred(*(i + (j – first2)), *j) is true . These conditions simply mean that every element in the subrange beginning with i must be the same as the corresponding element in [first2, last2) .

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

For the first version:

• ForwardIterator1 is a model of Forward Iterator.

• ForwardIterator2 is a model of Forward Iterator.

• ForwardIterator1 's value type is a model of EqualityComparable.

• ForwardIterator2 's value type is a model of EqualityComparable.

• Objects of ForwardIterator1 's value type can be compared for equality with Objects of ForwardIterator2 's value type.

For the second version:

• ForwardIterator1 is a model of Forward Iterator.

• ForwardIterator2 is a model of Forward Iterator.

• BinaryPredicate is a model of Binary Predicate.

• ForwardIterator1 's value type is convertible to BinaryPredicate 's first argument type.

• ForwardIterator2 's value type is convertible to BinaryPredicate 's second argument type.

• [first1, last1) is a valid range.

• [first2, last2) is a valid range.

The number of comparisons is proportional to (last1 – first1) * (last2 – first2) . If both ForwardIterator1 and ForwardIterator2 are models of Bidirectional Iterator, then the average complexity is linear and the worst case is at most (last1 – first1) * (last2 – first2) comparisons.

int main() {

char* s = "executable.exe";

char* suffix = "exe";

const int N = strlen(s);

const int N_suf = strlen(suffix);

char* location = find_end(s, s + N, suffix, suffix + N_suf);

if (location != s + N) {

cout << "Found a match for " << suffix << " within " << s << endl;

cout << s << endl;

int i;

for (i = 0; i < (location – s); ++i) cout << ' ';

for (i = 0; i < N_suf; ++i) cout << '^';

cout << endl;

} else cout << "No match for " << suffix << " within " << s << endl;

}

[1] The reason that this range is [first1, last1 – (last2 – first2)) , instead of simply [first1, last1) , is that we are looking for a subsequence that is equal to the complete sequence [first2, last2) . An iterator i can't be the beginning of such a subsequence unless last1 – i is greater than or equal to last2 – first2 . Note the implication of this: you may call find_end with arguments such that last1 – first1 is less than last2 – first2 , but such a search will always fail.

search

Category: algorithms

Component type: function

template

OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);

Copy copies elements from the range [first, last) to the range [result, result + (last – first)) . That is, it performs the assignments *result = *first , *(result + 1) = *(first + 1) , and so on. [1] Generally, for every integer n from 0 to last – first , copy performs the assignment *(result + n) = *(first + n) . Assignments are performed in forward order, i.e. in order of increasing n . [2]

The return value is result + (last – first)

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

• InputIterator is a model of Input Iterator.

• OutputIterator is a model of Output Iterator.

• InputIterator's value type is convertible to a type in OutputIterator's set of value types.

• [first, last) is a valid range.

• result is not an iterator within the range [first, last) .

• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + (last – first)) is a valid range. [1]

Linear. Exactly last – first assignments are performed.

vector V(5);

iota(V.begin(), V.end(), 1);

list L(V.size());

copy(V.begin(), V.end(), L.begin());

assert(equal(V.begin(), V.end(), L.begin()));

[1] Note the implications of this. Copy cannot be used to insert elements into an empty Container: it overwrites elements, rather than inserting elements. If you want to insert elements into a Sequence, you can either use its insert member function explicitly, or else you can use copy along with an insert_iterator adaptor.

[2] The order of assignments matters in the case where the input and output ranges overlap: copy may not be used if result is in the range [first, last) . That is, it may not be used if the beginning of the output range overlaps with the input range, but it may be used if the end of the output range overlaps with the input range; copy_backward has opposite restrictions. If the two ranges are completely nonoverlapping, of course, then either algorithm may be used. The order of assignments also matters if result is an ostream_iterator , or some other iterator whose semantics depends on the order or assignments.