user1095108 / xl

c++ xor linked list implementation

xl

This is a c++ implementation of an XOR linked list, a doubly linked list with reduced storage requirements, and a model of a (container, iterator) pair implementation.

STL containers are often slowed by various safety checks, exception safety and legacy code. A general rule of thumb seems to be, that pretty much anything we implement ourselves will outperform an STL implementation in some way; we have more flexibility than STL programmers and can adapt/optimize our implementations to our particular needs.

As usual with XOR containers, when you erase an iterator, the succeeding iterator is also invalidated. However, invalidated iterators can still be dereferenced. You should not use invalidated iterators for any operations, other than dereferencing. The same applies to insertion.

build instructions

g++ -std=c++20 -Ofast list.cpp -o l

resources

• Open Data Structures