How is a rangeiterator implemented in Python?

Question

>>> reversed(xrange(100))
<rangeiterator object at 0xb72aab78>
>>> it = reversed(xrange(100)).__iter__()
>>> it
<rangeiterator object at 0xb72aa4d0>
>>> next(it)
99

How can I implement something like this in Python? To be more spesific, how can I make an iterator, that could be reversed without it being made a list in the memory before it could get reversed?

You ask how to create an iterator which is reversible using reversed() without becoming too expensive, did I get you right? — Alfe, Mar 22 '12 at 10:04

score 3 · Answer 1 · answered Mar 22 '12 at 10:09

Basically, you implement the __reversed__ magic method on the collection.

The logic for xrange is something like:

def __reversed__(self):
    return iter(xrange(stop - 1, start - 1, step * -1))

There is no trick -- you need to know how to produce a reverse iterator. Python doesn't do it for you.

score 1 · Answer 2 · answered Mar 22 '12 at 10:09

1

If your iterator implements the method __reversed__(), this will be used by the builtin reversed(). xrange() returns iterators which do that.

answered Mar 22 '12 at 10:09

Alfe

56,346
20
107
159

score 0 · Answer 3 · edited May 23 '17 at 12:23

reversed will work with two types of object:

a sequence (such as a list)
an iterator with the __reversed__ magic method

If you have a custom sequence, and you can take the len() of that sequence, you are good to go -- otherwise, you need to add the __len__ magic method; if you cannot (e.g. because the length is not known), then you cannot reverse it lazily.

If you have a custom iterator, then make sure it has the __reversed__ magic method: __reversed__ must return a new iterator that goes backwards; again, if you cannot provide one (e.g. because the length is not known), then you cannot lazily reverse it.

Note: for more info about creating custom iterables see this answer.

How is a rangeiterator implemented in Python?

3 Answers3