Segmentation fault in reverse iterator

[tfpf]

Found a bug while working on #215.

I know, very funny! (Not.)

from pysorteddict import *
d = SortedDict()
d["foo"] = ()
d["bar"] = [100]
d["baz"] = 3.14
for key in reversed(d.keys()):
    d[key] = "spam"
    d["z_" + key] = "eggs"
    if "foo" in d:
        del d["foo"]
print(d)

[tfpf]

Root Cause Analysis

A reverse iterator tracks (and therefore prevents the deletion of) a key it will yield next. Thus, it allows the deletion of the key it yielded last. When said key is deleted, the underlying forward iterator (which previously pointed to it) is invalidated, and the reverse iterator is also invalidated. Calling next on it crashes the program.

#include <map>
#include <iostream>

int main(void)
{
    std::map<int, int> m;
    m[1] = 1;
    m[2] = 2;
    m[3] = 3;
    auto it = m.rbegin();
    std::cout << it->first << '\n';
    // ++it;
    std::cout << it->first << '\n';
    m.erase(3);
    std::cout << it->first << '\n';
}

Uncommenting the commented line makes this program invoke undefined behaviour, and therefore crash.