0

I have any container that does not provide random access iterators and the goal is to create an adapter that takes input such iterators and provide random access iterator interface to the container.

I am not sure how to use boost::iterator_facade as it is a bit confusing :-/ there are some examples on stack overflow but I am not sure how to use them ( here )

Any link/example could be helpful. (i read the examples in the boost they are a bit hard to digest considering my experience in boost

Community
  • 1
  • 1
KawKaw
  • 1
  • 2
    The standard requires that all operations on an iterator take amortized constant time. You can't take an iterator that takes `O(N)` time to increment by `N`, and magically turn it into an iterator that takes `O(1)` time to do the same. The result won't satisfy the complexity requirements of a random access iterator. – Igor Tandetnik Dec 19 '14 at 05:34
  • is it something that using `std::advance` will solve for you? – Anycorn Dec 19 '14 at 05:41
  • agreed, i do understand the design and concepts of iterators and containers... but is it possible to implement even with worst performance. if so, i would just want to implement it myself but i just need any idea/start for this. thanks! – KawKaw Dec 19 '14 at 05:42
  • just need range of iterators (begin_it, end_it) that are random access. underlying implementation can be anything even with poor performance. I am not modifying containers, just need a random access wrapper. – KawKaw Dec 19 '14 at 05:44

1 Answers1

1

You don't want to do this.

Either

  • Use a generalized range library with facilities to do "on the fly" caching, like Eric Niebler's Container Ranges concept from his Ranges proposal
  • explicitly code the intent, e.g. by creating a tag dispatched overload for your function that "reifies" an input range into a temporary container for random-access algorithms

If you really insist, yes you can probably implement your idea, but I don't see what it gains except hiding the runtime/storage cost. Especially, it won't be trivial with the need to keep lifetime around.¹

Slightly related: Boost Spirit has a boost::spirit::multi_pass adapter but that only upgrades from InputIterator to ForwardIterator (to allow backtracking).

¹ (What do you do when you have a temporary that's already a random access range? You cannot keep a reference to it, but you should also not unnecessarily copy it.)

sehe
  • 374,641
  • 47
  • 450
  • 633
  • This is true in the STL sense, but there is use for such a scheme: particularly `boost` [RandomAccessTraversalIterators](https://www.boost.org/doc/libs/1_63_0/libs/iterator/doc/new-iter-concepts.html#random-access-traversal-iterators-lib-random-access-traversal-iterators), where the iterator is expected to provide e.g. `operator+=` even when it is expected to occur in linear time. I am unsure if there is a magic adapter for such a case but one could probably write an adapter which uses `std::advance` for such operators easily enough. – fritzelr Oct 28 '18 at 17:10