[iterator] Idea for "range_from_ref_iterator"
Hi to all, Trying to simplify containers' code in Boost.Interprocess, I've seen that an iterator that simulates a range of values from a single value is useful to implement functions taking a value and a count in containers: template<class T, class A> class vector { //... void insert (iterator position, size_type n, const T& x); void assign (size_type n, const T& x); }; My intention was to reuse the code for "insert" and "assign" taking iterators to avoid nearly duplicating the code (which is quite complex in vector, deque and basic_string). This way, I've created an iterator called "range_from_ref_iterator" that can be used to implement the "insert" function taking a value and a count like this: void insert (iterator position, size_type n, const T& x) { this->insert(position ,range_from_ref_iterator<const T>(x, n) ,range_from_ref_iterator<const T>()); } This iterator is a random access traversal iterator, that I only would use as read iterator but I'm not sure if it would fill write iterator requirements. The code to implement the iterator: template <class T, class Difference = std::ptrdiff_t> class range_from_ref_iterator : public boost::iterator_facade < range_from_ref_iterator<T> , T , boost::random_access_traversal_tag , T & , Difference> { typedef boost::iterator_facade < range_from_ref_iterator<T> , T , boost::random_access_traversal_tag> super_t; typedef range_from_ref_iterator<T> this_type; //Give access to private core functions friend class boost::iterator_core_access; public: explicit range_from_ref_iterator(T &ref, Difference range_size) : m_ptr(&ref), m_num(range_size){} //This constructor creates a "end" iterator range_from_ref_iterator() : m_ptr(0), m_num(0){} private: T * m_ptr; Difference m_num; void increment() { --m_num; } void decrement() { ++m_num; } bool equal(const this_type &other) const { return m_num == other.m_num; } T & dereference() const { return *m_ptr; } void advance(Difference n) { m_num -= n; } Difference distance_to(const this_type &other)const { return m_num - other.m_num; } }; Do you think this iterator is a good addition to boost iterator library? Obviously it can be more refined. It could take the external value by reference or store a copy depending on the type. But I think it can be useful. I'm open to write the documentation following Boost.Iterator style if this iterator is considered useful (I'm open also to let others do the hard work, of course). Comments? Regards, Ion
Ion Gaztañaga <igaztanaga@gmail.com> writes:
Hi to all,
Trying to simplify containers' code in Boost.Interprocess, I've seen that an iterator that simulates a range of values from a single value is useful to implement functions taking a value and a count in containers:
template<class T, class A> class vector { //... void insert (iterator position, size_type n, const T& x); void assign (size_type n, const T& x); };
My intention was to reuse the code for "insert" and "assign" taking iterators to avoid nearly duplicating the code (which is quite complex in vector, deque and basic_string). This way, I've created an iterator called "range_from_ref_iterator" that can be used to implement the "insert" function taking a value and a count like this:
You haven't really explained what this thing is supposed to be doing. As far as I can tell from the code, it dereferences to the same location at each position. If that's really what you intend, you ought to do something to ensure that its iterator category doesn't indicate it satisfies forward iterator requirements.
Do you think this iterator is a good addition to boost iterator library? Obviously it can be more refined. It could take the external value by reference or store a copy depending on the type. But I think it can be useful. I'm open to write the documentation following Boost.Iterator style if this iterator is considered useful (I'm open also to let others do the hard work, of course). Comments?
Seems like a reasonable idea, but I'm not sure whether it's useful enough to be included. I'd definitely call it something other than range_from_ref_iterator, though. constant_iterator or something like that seems appropriate. -- Dave Abrahams Boost Consulting www.boost-consulting.com
You haven't really explained what this thing is supposed to be doing. As far as I can tell from the code, it dereferences to the same location at each position. If that's really what you intend, you ought to do something to ensure that its iterator category doesn't indicate it satisfies forward iterator requirements.
A pair of "range_from_ref_iterator" simulates a pair of random access iterators that point to an array of N identical values. Suppose: range_from_ref_iterator<T>(val, N); is a iterator to the beginning of a simulated array of N equal elements with "val" value. range_from_ref_iterator<T>(); is a "end" iterator to the end of the array. If you have a function taking a pair of iterators: template <class InpIt> void do_something(InpIt beg, InpIt end); And you want to simulate it with a range of N equal input values, you can write: std::vector<T> values(N, val); std::vector<T>::const_iterator beg = values.begin(), end = values.end() do_something(beg, end); but it's more efficient to write: T val; do_something(range_from_ref_iterator<const T>(val, N), range_from_ref_iterator<const T>()); range_from_ref_iterator basically stores a pointer to the value and an internal count. The end iterator has a 0 count. The internal count is decremented when incrementing the iterator and operator*() always returns a reference to "val". Since range_from_ref_iterator is a random traversal iterator the function taking iteratorscan optimize the code as if it was an array (for example in vectors when reallocating internal storage). Obviously, maybe is only useful with const values because inside an iteration the source can be modified and in the rest of the iterations the value would be different from original value, and external "val" value would be also modified. Maybe even this modification could be useful, who knows, as an accumulation effect. But I wanted it to simulate a constant N element array of identical values.
Seems like a reasonable idea, but I'm not sure whether it's useful enough to be included. I'd definitely call it something other than range_from_ref_iterator, though. constant_iterator or something like that seems appropriate.
constant_iterator seems good, because I'm thinking that maybe it has sense only to store a constant reference that can't be modified, so constant_iterator<T>(val, T); would return a const reference to val every iteration instead of a non-const reference. Ion
Ion Gaztañaga <igaztanaga@gmail.com> writes:
You haven't really explained what this thing is supposed to be doing. As far as I can tell from the code, it dereferences to the same location at each position. If that's really what you intend, you ought to do something to ensure that its iterator category doesn't indicate it satisfies forward iterator requirements.
A pair of "range_from_ref_iterator" simulates a pair of random access iterators that point to an array of N identical values.
It's not a legal random access (or even forward) iterator if it visits the same *element* more than once in a traversal. That's why I said the above about the iterator category.
Seems like a reasonable idea, but I'm not sure whether it's useful enough to be included. I'd definitely call it something other than range_from_ref_iterator, though. constant_iterator or something like that seems appropriate.
constant_iterator seems good,
Whoops, "constant iterator" is already overloaded with a different meaning. Something else, maybe... "repeat iterator?" -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Ion Gaztañaga <igaztanaga@gmail.com> writes:
You haven't really explained what this thing is supposed to be doing. As far as I can tell from the code, it dereferences to the same location at each position. If that's really what you intend, you ought to do something to ensure that its iterator category doesn't indicate it satisfies forward iterator requirements.
A pair of "range_from_ref_iterator" simulates a pair of random access iterators that point to an array of N identical values.
It's not a legal random access (or even forward) iterator if it visits the same *element* more than once in a traversal. That's why I said the above about the iterator category.
Seems like a reasonable idea, but I'm not sure whether it's useful enough to be included. I'd definitely call it something other than range_from_ref_iterator, though. constant_iterator or something like that seems appropriate.
constant_iterator seems good,
Whoops, "constant iterator" is already overloaded with a different meaning. Something else, maybe... "repeat iterator?"
I agree it is nice to have "verb" for 'range adaptors'. copy(x|repeated(10)|transformed..., outIter); repeat_range(repeat_iterator pair) seems to make an object be a range: copy(x|repeated(1), outIter); So generalized! But as Mr.Abrahams pointed, it is pity repeat_iterator for now is illegal. (I remember I wrote the same code as Mr.Gaztanaga's!) Is it possible it can have a legal implementation? I don't know for sure... -- Shunsuke Sogame
It's not a legal random access (or even forward) iterator if it visits the same *element* more than once in a traversal. That's why I said the above about the iterator category.
Ooops! I would agree that for non-const values it wouldn't be a random-access but as an read iterator with const values you can't notice it's returning the same value unless you unconst it. The random access tag is in my opinion a strongest point of the iterator, you can get a performance boost in many applications (specially when implementing containers). I'm out of ideas about how to solve this. Can't we live breaking the law? Should we create new categories? Just let it as a "poor" input iterator?
Whoops, "constant iterator" is already overloaded with a different meaning. Something else, maybe... "repeat iterator?"
constant_iterator is also very similar to const_iterator. Regards, Ion
Ion Gaztañaga <igaztanaga@gmail.com> writes:
It's not a legal random access (or even forward) iterator if it visits the same *element* more than once in a traversal. That's why I said the above about the iterator category.
Ooops! I would agree that for non-const values it wouldn't be a random-access but as an read iterator with const values you can't notice it's returning the same value unless you unconst it.
You can check the address. Is that an issue? I'm not sure. It's the old "equivalence" problem again.
The random access tag is in my opinion a strongest point of the iterator, you can get a performance boost in many applications (specially when implementing containers). I'm out of ideas about how to solve this. Can't we live breaking the law? Should we create new categories? Just let it as a "poor" input iterator?
We already have new categories. It can report that it has random access traversal. It's just not allowed to have random_access_iterator_tag. See the "new iterator categories" document.
Whoops, "constant iterator" is already overloaded with a different meaning. Something else, maybe... "repeat iterator?"
constant_iterator is also very similar to const_iterator.
That's a "pre-existing condition." -- Dave Abrahams Boost Consulting www.boost-consulting.com
The random access tag is in my opinion a strongest point of the iterator, you can get a performance boost in many applications (specially when implementing containers). I'm out of ideas about how to solve this. Can't we live breaking the law? Should we create new categories? Just let it as a "poor" input iterator?
We already have new categories. It can report that it has random access traversal. It's just not allowed to have random_access_iterator_tag. See the "new iterator categories" document.
Sorry, I really wanted to say "random access traversal" instead of random access iterator. Taking a snippet of the proposed implementation: template <class T, class Difference = std::ptrdiff_t> class range_from_ref_iterator : public boost::iterator_facade < range_from_ref_iterator<T, Difference> , T , boost::random_access_traversal_tag , T & , Difference> Correct me if I'm wrong but what I want is to simulate a source of N identical objects without modifying them, so I think this is a Readable Iterator and a Random Access Traversal Iterator. I would now propose something like: template <class T, class Difference = std::ptrdiff_t> class repeat_read_iterator : public boost::iterator_facade < repeat_read_iterator<T, Difference> , const T , boost::random_access_traversal_tag , const T & , Difference> so dereferencing "repeat_read_iterator<T>" would return const T & with random_access_traversal capability to be able move fast inside that "virtual read-only array". Am I missing something? Do you see this read only repeated sequence simulation useful to include it the iterator library? Regards, Ion
Ion Gaztañaga <igaztanaga@gmail.com> writes:
Sorry, I really wanted to say "random access traversal" instead of random access iterator. Taking a snippet of the proposed implementation:
template <class T, class Difference = std::ptrdiff_t> class range_from_ref_iterator : public boost::iterator_facade < range_from_ref_iterator<T, Difference> , T , boost::random_access_traversal_tag , T & , Difference>
Correct me if I'm wrong but what I want is to simulate a source of N identical objects without modifying them, so I think this is a Readable Iterator and a Random Access Traversal Iterator.
Yes, but unless you take special measures, the iterator library will notice that you're using random access traversal and your reference type is a real reference, and it will make iterator_traits<range_from_ref_iterator<...> >::iterator_category be random_access_iterator_tag. IIUC, that would be a nonconforming iterator. 24.1.3 says: If a and b are both dereferenceable, then a == b if and only if *a and *b are the same object. I don't think your iterators meet taht criterion.
I would now propose something like:
template <class T, class Difference = std::ptrdiff_t> class repeat_read_iterator : public boost::iterator_facade < repeat_read_iterator<T, Difference> , const T , boost::random_access_traversal_tag , const T & , Difference>
so dereferencing "repeat_read_iterator<T>" would return const T & with random_access_traversal capability to be able move fast inside that "virtual read-only array". Am I missing something?
Only that the library will assign the wrong category unless you do something to prevent it.
Do you see this read only repeated sequence simulation useful to include it the iterator library?
Sure. But useful enough? That I do not know. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Ion Gaztañaga <igaztanaga@gmail.com> writes:
I would now propose something like:
template <class T, class Difference = std::ptrdiff_t> class repeat_read_iterator : public boost::iterator_facade < repeat_read_iterator<T, Difference> , const T , boost::random_access_traversal_tag , const T & , Difference>
so dereferencing "repeat_read_iterator<T>" would return const T & with random_access_traversal capability to be able move fast inside that "virtual read-only array". Am I missing something?
Only that the library will assign the wrong category unless you do something to prevent it.
Do you see this read only repeated sequence simulation useful to include it the iterator library?
Sure. But useful enough? That I do not know.
I think the iterator is related to Boost.MPL's 'single_view'. In the context of iterators, it is maybe 'single_range', which is the iterator pair of (&x, &x + 1). I said the iterator could be more generalized by changing the parameter to a range: if (equals(make_repeat_range(make_single_range('x'), 6), std::string("xxxxxx"))) {... if (equals(make_repeat_range(std::string("xxx"), 2), std::string("xxxxxx"))) {... Using nicer syntax: if (equals( std::string("xxx")|repeated(2)|jointed(std::string("yy")), std::string("xxxxxxyy") ) {... That iterator seems to raise yet another regex/xpressive? :-) (though I'm not sure it is legal.) -- Shunsuke Sogame
Ion Gaztañaga wrote:
You haven't really explained what this thing is supposed to be doing. As far as I can tell from the code, it dereferences to the same location at each position. If that's really what you intend, you ought to do something to ensure that its iterator category doesn't indicate it satisfies forward iterator requirements.
A pair of "range_from_ref_iterator" simulates a pair of random access iterators that point to an array of N identical values.
Let me note that, that iterator, illegal or not, can be more generalized. copy(rng|repeated(12), outIter); I mean your iterator should take not a value but a range(iterator pair) as the argument of the constructor. Thus, copy(make_identity_range(x)|repeated(12), outIter); -- Shunsuke Sogame
participants (3)
-
David Abrahams -
Ion Gaztañaga -
Shunsuke Sogame