2

There are times when I'll want to use the iterator returned by a function from the algorithm library. The problem I'm facing occurs when I go between a modifying function and a non-modifying function. Cause in the non-modifying function I want to use a const_iterator. As a toy example:

vector<int> v = { 1, 8, 7, 4, 3, 6, 2, 5 };
auto it = partition(begin(v), end(v), bind(greater<int>(), placeholders::_1, 3));

cout << (find(cbegin(v), it, 13) != cend(v)) << endl;

When I try to compile this code I get the error:

no matching function for call to find(std::vector<int>::const_iterator, __gnu_cxx::__normal_iterator<int*, std::vector<int> >&, int)

The problem I'm running into is the only conversion process I can find is potentially expensive: auto cit = next(cbegin(v), distance(begin(v), it))

Is there a way I can make this work? Or am I stuck converting or just using non-const_iterators?

Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288
  • Just a preemptive comment, I know that I could just use `find` directly on `v`. I'm not looking for a better way to write my toy example; I'm looking for a solution to the problem it illustrates. – Jonathan Mee Feb 16 '17 at 20:11
  • Have you tried just constructing a const_iterator from the normal one? – rubenvb Feb 16 '17 at 20:13
  • Are we to assume that the type of the original container is unknown? If not, `decltype(v)::const_iterator(it)` does the trick. Using `cvegin(v)` in your proposed solution seems to imply you have access to `v`, and not only the iterator. – François Andrieux Feb 16 '17 at 20:13
  • 1
    All STL container `iterator` are convertible to its `const_iterator`. See [this](http://stackoverflow.com/questions/7759246/c-iterator-to-const-iterator) – WhiZTiM Feb 16 '17 at 20:14
  • 2
    Maybe using `std::list` would be better for the toy example, otherwise assertions such as `distance` being expensive don't hold. – nwp Feb 16 '17 at 20:16
  • the other way around (const_iterator to iterator) would be problematic... – mike Feb 16 '17 at 20:41
  • @mike Yeah, when I realized you could cast that was my next question. I'll ask tomorrow or you can now, but if you do please link so i can find it. – Jonathan Mee Feb 16 '17 at 20:45
  • 1
    @JonathanMee something like this? http://stackoverflow.com/questions/765148/how-to-remove-constness-of-const-iterator – clcto Feb 16 '17 at 20:49
  • @clcto Great link! Thanks for protecting me from duping. [James McNellis's solution](http://stackoverflow.com/a/10669041/2642059) is particularly headsploding. It doesn't makes sense that it hasn't been accepted since `const_iterator`s are only available for containers (and arrays for which pointer arithmetic is inexpensive.) – Jonathan Mee Feb 16 '17 at 20:55
  • 1
    nice link - Scott Meyers have not included it in item 13 of his Effective Modern C++. He states that in c++11 conversion of const_iterator to iterator is UB. But he mentions that there are ways to accomplish that but they are not worth including in the book. – mike Feb 16 '17 at 21:00

3 Answers3

4

You can specify the template argument:

find<decltype(cbegin(v))>(cbegin(v), it, 13) != cend(v)

Demo

clcto
  • 9,530
  • 20
  • 42
  • 2
    I see the error is actually because I'm cause ambiguity in the template deduction of `find`. So this is the same as the other examples, forcing a cast. Is there a statement anywhere that such a cast is legal, and not just implementation defined? – Jonathan Mee Feb 16 '17 at 20:28
3

It's much less expensive to simply cast the mutable iterator to a constant iterator:

cout << (find(cbegin(v), vector<int>::const_iterator{it}, 13)
      != cend(v)) << endl;

A mutable iterator should always be castable into a constant iterator.

EDIT: I found the part of the standard that guarantees that an iterator is convertible to a constant iterator.

Table 96 in section 23.2 "Container requirements" specifies that the expression X::iterator results in:

any iterator category that meets the forward iterator requirements. convertible to X::const_iterator.

Sam Varshavchik
  • 114,536
  • 5
  • 94
  • 148
  • 1
    Is there a guaranteed such conversion? – Cheers and hth. - Alf Feb 16 '17 at 20:16
  • 1
    @Cheersandhth.-Alf See here: http://stackoverflow.com/a/7759474/1294207 – Fantastic Mr Fox Feb 16 '17 at 20:17
  • 1
    @FantasticMrFox: That's fantastic, thanks. I sort of trust the Good Robot. But a standard ref. would have clinched the matter. – Cheers and hth. - Alf Feb 16 '17 at 20:19
  • 2
    "Note: iterator and const_-iterator have identical semantics in this case, and iterator is convertible to const_iterator." - I found this wording explicitly copy-pasted between 23.2.4, associative containers, and 23.2.5 unordered associative containers. Curiously it is missing from 23.3, sequence containers, which seems to be an oversight, unless it is worded slightly differently. – Sam Varshavchik Feb 16 '17 at 20:25
  • @SamVarshavchik interesting. Since all these answers point out that this is a legal cast (which I didn't know) I'd really like if one of the answers could differentiate by demonstrating this is defined per the standard. – Jonathan Mee Feb 16 '17 at 20:28
  • 2
    @JonathanMee -- found the cite from the standard, that seems to apply to all iterator types. – Sam Varshavchik Feb 16 '17 at 20:39
1

There are three approaches.

The first one is to write

cout << (find( begin(v), it, 13) != cend(v)) << endl;
               ^^^^^

The second one is to write

cout << (find(cbegin(v), static_cast<std::vector<int>::const_iterator>( it )
, 13) != cend(v)) << endl;

Or shorter

cout << (find(cbegin(v), static_cast<decltype( v.cbegin())>( it )
, 13) != cend(v)) << endl;

And the third one is to write

cout << (find<std::vector<int>>::const_iterator>( cbegin(v), it, 13) != cend(v)) << endl;

or shorter

cout << (find<decltype( v.cbegin())>( cbegin(v), it, 13) != cend(v)) << endl;
Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
  • Yeah i mention in the question that **1** is undesirable. The other 2 options are both effectively casting to a `const_iterator` (which I didn't know you could do.) Is there anything in the standard that explicitly allows this? – Jonathan Mee Feb 16 '17 at 20:30
  • 1
    @JonathanMee See in the Table 96 — Container requirements the row about iterators. – Vlad from Moscow Feb 16 '17 at 20:35