STL algorithms and const_iterators

Question

Hello,

Today I wrote a small predicate to find matching symbols in a container.

But I'm faced to a problem: I want to use this predicate in a std::find_if call inside a const-method of a class, searching in a container that is a member of this class.

But I just noticed that neither std::find nor std::find_if are able to operate on const_iterators !

I checked on some C++ references and it seems there is no version of std::find or std::find_if that accept/return const_iterators. I just can't understand why, since from what I've seen, there is no way that these algorithms could modify the object referenced by the iterator.

Here is how is documented std::find in the SGI implementation:

Returns the first iterator i in the range [first, last) such that *i == value. Returns last if no such iterator exists.

Answer 1

std::find and std::find_if can definitely operate on *::const_iterator for a given container. Are you by chance looking at the signatures of those functions, and misunderstanding them?

template <class InputIterator, class Type>
InputIterator find(InputIterator first, InputIterator last, const Type& val);

Note that InputIterator here is just a name of a template type parameter, and any const_iterator will satisfy the requirements for it.

Or, perhaps, you're confusing const_iterator (i.e. an iterator referencing a const value) with a const iterator (i.e. an iterator which is itself const)?

Answer 2

std::find and std::find_if both take the iterator type as a template parameter, so they most certainly can operate on const_iterators. Just for a quick example:

#include <vector>
#include <algorithm>
#include <iostream>
int main() { 
    std::vector<int> x;

    std::fill_n(std::back_inserter(x), 20, 2);
    x.push_back(3);

    std::vector<int>::const_iterator b = x.begin();
    std::vector<int>::const_iterator e = x.end();

    std::vector<int>::const_iterator p = std::find(b, e, 3);

    std::cout << *p << " found at position: " << std::distance(b, p) << "\n";
    return 0;
}

This should be accepted by any properly functioning C++ compiler, and produce results like:

3 found at position: 20

Answer 3

I have just had the same problem. I had a member function that was calling find_if on a member vector, and the compiler gave me an error when I tried making the member function const. It turned out that this was because I was assigning the return value of find_if to an iterator instead of const_iterator. The caused the compiler to assume that the parameters of find_if must also be iterator instead of const_iterator, which it could not get from the const member vector.