7

I am getting a

Error   C2678   binary '*': no operator found which takes a left-hand operand of type 'const _InIt' (or there is no acceptable conversion)

it is thrown by this code in MSVC (2022, V17.1) <algorithm> header.

template <class _FwdIt, class _Ty, class _Pr>
_NODISCARD _CONSTEXPR20 _FwdIt lower_bound(_FwdIt _First, const _FwdIt _Last, const _Ty& _Val, _Pr _Pred) {

...
        const auto _UMid                   = _STD next(_UFirst, _Count2);
        if (_Pred(*_UMid, _Val)) { // try top half

The second line throws the error because of the const on the line above.

The iterator I am passing in, is a custom LegacyRandomAccessIterator over a "flat-file" and its operator* looks like this:

  value_type operator*() { return current(); }

...

  ValueType current() {
    if (!cur_valid_) {
      cur_       = ffdb_->get_record(pos_);
      cur_valid_ = true;
    }
    return cur_;
  }

In other words, I can't just mark my operator* as const because it's not, and can't be really - It's doing loading of a buffered set of records from disk, and that's not a const operation in a the current design.

I implemented a "dummy" const version to prove that was the problem:

 value_type operator*() const { return value_type{}; }

Error is gone, but clearly this doesn't do anything.

libstdc++ doesn't have this expectation of a const operator*. (I haven't tested libc++)

Is this solvable, without some major redesign of my iterator?

Is it reasonable for MSVC's implementation to have this expectation?

Oliver Schönrock
  • 1,038
  • 6
  • 11
  • Not sure if that's a legal iterator. How about moving `get_record` logic to `++`? – HolyBlackCat Mar 18 '22 at 18:40
  • @HolyBlackCat It's a thought. and to the constructor then..? for the iterator returned by begin() of the parent class? – Oliver Schönrock Mar 18 '22 at 18:43
  • Yeah, probably. – HolyBlackCat Mar 18 '22 at 18:43
  • you could also make `cur_` & `cur_valid_` mutable, that way `current()` can be const. – Turtlefight Mar 18 '22 at 18:44
  • @Turtlefight also neat idea... I was just quite floored that there is the expectation to have a `const operator*`. Is that written somewhere that I have not seen? – Oliver Schönrock Mar 18 '22 at 18:46
  • Please note that the name of the template parameter is `_FwdIt`, so it requires a *forward iterator*, and for the forward iterator, the `operator*()` must be *equality-preserving*, that is, the values of the two calls before and after must be the same. – 康桓瑋 Mar 18 '22 at 18:48
  • 1
    @康桓瑋 Sure. OK. I think I comply with that. Do you mean: If you call operator* twice it must give you the same value. It does. Just some internal private state has potentially changed (ie the buffered records). – Oliver Schönrock Mar 18 '22 at 18:50
  • If it's equiality-preserving, then making the variables mutable should be ok. – HolyBlackCat Mar 18 '22 at 18:51
  • @HolyBlackCat Not 100% sure what equality preserving means exactly in this context... but yeah, I like the mutable idea. This seems to even suggest such usage: https://stackoverflow.com/a/105061/1087626 " Logical const is when an object doesn't change in a way that is visible through the public interface" – Oliver Schönrock Mar 18 '22 at 18:52
  • After reading [cppreference](https://en.cppreference.com/w/cpp/iterator/forward_iterator), I'm not even sure it's the right term. Basically, repeated dereferences should return the same thing, until it's incremented. – HolyBlackCat Mar 18 '22 at 18:54
  • @HolyBlackCat Agreed. That's my interpretation too. And that will be true even if I "sneak past the const" by making `cur_` and `cur_valid_` `mutable`. Seems like the answer? – Oliver Schönrock Mar 18 '22 at 18:57
  • @康桓瑋 yeah. Like I said. It super surprised me. I have not seen `const operator*` in the various suggested iterator implementations.... My standardese is nowhere near good enough to say whether MSVC is "wrong" though. – Oliver Schönrock Mar 18 '22 at 18:59
  • Also note that in the C++17 iterator system, the return type of `operator*()` of forward iterator must be a reference type, so your iterator still does not model the forward iterator. – 康桓瑋 Mar 18 '22 at 19:02
  • @康桓瑋 Yeah, that may be true. And it can easily be a `&` to the private internal `cur_`. – Oliver Schönrock Mar 18 '22 at 19:06
  • @康桓瑋 The irony is that my iterator is a `const_iterator` in the sense that you can't modify the values on disk via the reference you would get from `operator*`. But the iterator object itself is "not const" if that makes sense. – Oliver Schönrock Mar 18 '22 at 19:08
  • 3
    @OliverSchönrock *"Is [the expectation to have a `const operator*`] written somewhere that I have not seen?"* -- See [LegacyInputIterator](https://en.cppreference.com/w/cpp/named_req/InputIterator). Given `i`, a value of type `It` **or `const It`**, the expression `*i` must be valid. – JaMiT Mar 18 '22 at 19:09
  • just move `ffdb_->get_record(pos_)` et. al. into the increment operator and let `operator*` be truly const. – jwezorek Mar 18 '22 at 19:10
  • @JaMiT OK, that's good... For clarity.. this is actually a random access iterator... otherwise not much point calling std::lower_bound. ... binary search ... – Oliver Schönrock Mar 18 '22 at 19:12
  • @jwezorek That could also work. I just don't like the fact that it would then have to make `cur_` valid immediately upon construction, ie when you call `begin()` on the parent class. – Oliver Schönrock Mar 18 '22 at 19:13
  • 1
    @OliverSchönrock You asked about what `std::lower_bound` requires. It requires a _LegacyForwardIterator_, and a _LegacyForwardIterator_ must satisfy _LegacyInputIterator_. This requirement does not change based upon what you intend your iterator to be. (Still, if you intend your iterator to be a _LegacyRandomAccessIterator_, then it must also be a _LegacyBidirectionalIterator_, which in turn requires being a _LegacyForwardIterator_, and we're back to satisfying _LegacyInputIterator_.) – JaMiT Mar 18 '22 at 19:25
  • @JaMiT Yes I understand all that. Thank you. I thought it was worth mentioning that the requirements on the iterator are actually a significant SUPERSET LegacyForwardIterator. Beause of what it is doing in the application, not because of std::lower_bound. Although std::lower_bound is quite pointless if you feed it with a FWdIt. – Oliver Schönrock Mar 18 '22 at 19:26

1 Answers1

5

std::lower_bound takes a Cpp17ForwardIterator, which must also be a Cpp17InputIterator. The Cpp17InputIterator requirements include:

Expression Return type
*a reference, convertible to T

Here, a is a "value of type X or const X", so MSVC is justified in requiring a const-qualified unary indirection operator; the "or" means that the code using the iterator can use either, and the author of the iterator has to support both. (Note that Cpp17InputIterator differs from Cpp17OutputIterator, where the required operation is *r = o, with r a non-const reference, X&.)

So your operator* should have const qualification, and return a reference; specifically, a reference to T or const T (this is a Cpp17ForwardIterator requirement). You can satisfy this straightforwardly with using reference = const T& and by making cur_ and cur_valid_ mutable.

The use of mutable here is entirely legitimate; since operator*() const is idempotent, it is "logically const" and the modifications to the data members are non-observable.

ecatmur
  • 152,476
  • 27
  • 293
  • 366