5

I need an iterator for my custom random access collection class. I want to use the iterator with std::sort. As I'm a C++ newbee with a limited time budget, I'd like to avoid writing the whole thing myself.

My iterator is basically just a simple size_t. Therefore, I thought boost::counting_iterator could be a good match. Once I had completed the Incrementable I had to realize that counting_iterator defines its reference type as const Incrementable&.

Although I'm still confused by a lot of C++, I believe this will prevent me from using the iterator with std::sort because const iterators can not be used to swap collection elements.

Here is the question: why does boost::counting_iterator define its reference type as const and, probably more important, what should I use instead?

Johannes Luong
  • 574
  • 5
  • 19
  • 1
    `boost::counting_iterator` is not usable for accessing containers. It is created for "accessing" a sequence of natural numbers `0, 1, 2, ...`. That's why its reference type is a `const`: you cannot hack `2` to become `3`. – n. m. could be an AI Aug 09 '16 at 12:18
  • "I need an iterator for my custom random access collection class." is probably not compatible with "I'm a newbie". May I ask why you need a custom collection class? – Richard Hodges Aug 09 '16 at 12:28
  • "My iterator is basically just a simple `size_t`" I don't understand. `size_t` does not meet the requirements of the iterator concept – KABoissonneault Aug 09 '16 at 12:59
  • @KABoissonneault what I meant by that statement is that my iterator can be represented internally by a simple size_t which denotes the index of an element in the collection. – Johannes Luong Aug 09 '16 at 13:29
  • @RichardHodges I want a relation (SQL) like collection whose implementation I understand and control. Currently I use a simple column oriented format i.e. a `std::tuple` of `std::vector`s. The iterator has to work row oriented instead of column oriented though. – Johannes Luong Aug 09 '16 at 13:34
  • I've seen an example of this in the DTL - http://dtemplatelib.sourceforge.net/ – Richard Hodges Aug 09 '16 at 15:02

1 Answers1

1

Why does boost::counting_iterator define its reference type as const?

Its purpose, as described here, is to fill arrays with an object that is itself incremented when the iterator is incremented. Having had a brief look through its docs (I'm no Boost expert btw) it seems to hold a copy of the Incrementable object you hand it. It then returns const references to its internal copy, to stop someone modifying its internal copy.

Once I had completed the Incrementable I had to realize that counting_iterator defines its reference type as const Incrementable&.

Yes, when dereferenced it will return a constant reference to the Incrementable object that it holds, which is itself non-constant (hence it can be incremented and decremented).

I believe this will prevent me from using the iterator with std::sort because const iterators can not be used to swap collection elements.

Correct :) Under-the-hood a swap looks like

using T = size_t;
T tmp = a;
a = b;    // requires a to be non-constant
b = tmp;  // requires b to be non-constant

What should I use instead?

Depends on your container. An iterator to a container should contain a pointer to an element in the container. You can probably just re purpose a standard iterator.

Judge
  • 372
  • 2
  • 8
  • You are right, `counting_iterator` clearly has a different purpose. Unfortunately, my collection does not allow a simple pointer to a collection element. My collection resembles a SQL relation and it stores its elements by column. The iterator on the other hand, models access by row so reading from and writing to the iterator has to go through some kind of translation process. Simple pointers are therefore not an option. – Johannes Luong Aug 09 '16 at 13:49
  • what standard iterators are you thinking of? I can only find iterators that are bound to specific collection types. – Johannes Luong Aug 09 '16 at 13:59
  • I'm not an SQL expert, but if you're using a `std::tuple` of `std::vector`s then I don't think it's possible to iterate across the tuple with an iterator ([see here for how you might do it recursively](http://stackoverflow.com/a/6894436/6367128)). Do all the vectors contain the same underlying type? If so, then you can avoid the tuple and use a vector of vectors. – Judge Aug 09 '16 at 14:46
  • Given what you're trying to do, I don't think a standard iterator will work anymore. If you can guarantee that the values are contiguous in memory, then you might be able to use some sort of [strided iterator](http://www.boost.org/doc/libs/1_47_0/boost/range/adaptor/strided.hpp), where to get to the next element in the row, you add the length of the column. If you can't, then you might have to define your own iterator that has knowledge of your containers internal structure and does the "translation" process you're after. – Judge Aug 09 '16 at 14:52
  • I will probably give `boost::iterator_facade` a try and report my findings here. Thanks for your patience. – Johannes Luong Aug 09 '16 at 14:58