Impact of removing a list item on reversed() in python

Question

As far as I know, reversed() function gives an iterator and works just like iter() but will give the items in reverse order. However I faced a strange behavior from the object that gets back from reversed() function.

By looking at:

lst = ['a', 'b', 'c', 'd']
iter_lst = iter(lst)
lst.remove('c')
print(list(iter_lst))

output : ['a', 'b', 'd']

It's just as expected. but:

lst = ['a', 'b', 'c', 'd']
rev_iter_lst = reversed(lst)
lst.remove('c')
print(list(rev_iter_lst))

output : []

Shouldn't it be : ['d', 'b', 'a'] ?

Is it something in implementation of __reversed__() method in list object or __next__() method in the iterator object that prevents this ? I mean if something changes in original list it won't produce reverse sequence maybe...

Update: I've posted an answer which is a possible fix to it here, I've tested that but I'm unaware if there is a situation that this implementation would give unexcepted result.

Answer 1

according to list.__reversed__ source code, the iterator remembers the last index address and returns the iterator which remembers the last index address. now when you remove an item it will shift all the indexes and makes the last address point to nowhere and it will return an empty list because there is nothing to iterate over. let me describe more: consider following list: lst = ['a','b','c'] also let's assume lst[0] is at the 100 and each character is one byte so, the character 'c' is in the 102. when you create a revered iterator it will remember 102 as the start point. in the next step, we omit 'b' now the character 'c' is in address 101. and when you ask the iterator to iterate, it will start to look at position 102. what it will found there? literally nothing and obviously it will return an empty list.

I hope this can be helpful :)

EDIT: the word address is not correct. I must use index instead...

Answer 2

So after the discussion with @kkasra12 I ended up implementing Python's pseudo-list object (without doing all the necessary checkings) to mimic it's behavior and I just focused on reverse() operation. Here is my class:

class MyList:
    def __init__(self, n):
        self.length = n
        self._seq = list(range(n))

    @property
    def seq(self):
        return self._seq

    def __len__(self):
        return self.length

    def __getitem__(self, item):
        return self._seq[item]

    def __setitem__(self, idx, value):
        self._seq[idx] = value

    def __reversed__(self):
        return ReverseIterator(self)

    def __str__(self):
        return str(self._seq)

    def append(self, v):
        self._seq.append(v)
        self.length += 1

    def remove(self, v):
        self._seq.remove(v)
        self.length -= 1

And my ReverseIterator:

class ReverseIterator:
    def __init__(self, org):
        self.org = org
        self._index = org.length

    def __iter__(self):
        return self

    def __next__(self):
        if 0 < self._index:
            try:
                item = self.org.seq[self._index - 1]
                self._index -= 1
                return item
            except IndexError:
                raise StopIteration()
        else:
            raise StopIteration()

The result:

obj = MyList(6)
iter_obj = iter(obj)
obj.remove(2)
print(list(iter_obj))

print('-----------------------')

obj = MyList(6)
rev_iter_obj = reversed(obj)
obj.remove(2)
print(list(rev_iter_obj))

output :

[0, 1, 3, 4, 5]
-----------------------
[]

By commenting those remove statements above, we can see that it works like original list object.

Then I created new SmartReverseIterator iterator which can handle if an item is removed from the original object and can generate the values on the fly just like how iter() wokred on the list in OP.

The only thing should be considered is if an item is removed(self._index would be smaller than original object's length), the self._index should be reset.

class SmartReverseIterator:
    def __init__(self, org):
        self.org = org
        self._index = org.length

    def __iter__(self):
        return self

    def __next__(self):
        if 0 < self._index:
            try:
                item = self.org.seq[self._index - 1]
                return item

            except IndexError:
                self._index = self.org.length
                item = self.org.seq[self._index - 1]
                return item

            finally:
                self._index -= 1
        else:
            raise StopIteration()

By changing the __reversed__ method on MyList to return this new iterator, the result is going to be:

obj = MyList(6)
iter_obj = iter(obj)
obj.remove(2)
print(list(iter_obj))

print('-----------------------')

obj = MyList(6)
rev_iter_obj = reversed(obj)
obj.remove(2)
print(list(rev_iter_obj))

Output:

[0, 1, 3, 4, 5]
-----------------------
[5, 4, 3, 1, 0]

I wanted to know if there is any downside to this, or in other words why python decided not to implement __reversed__ method on list objects like this to result exactly how iter() can generate values if an item is removed.

In which situation we would see issues ?

Answer 3

The list call will iterate the reverse iterator, whose index < PyList_GET_SIZE(seq) check here will fail because you shrunk seq in the meantime, and thus won't yield a value but stop:

listreviter_next(listreviterobject *it)
{
    (some checks)
    index = it->it_index;
    if (index>=0 && index < PyList_GET_SIZE(seq)) {
        (decrease the index and return the element)
    }
    (stop the iteration)
}