Pointer to std::list object

[fhg38]

In a class, I have a static std::list of all the instances of that class. I want to be able to efficiently remove objects from the std::list in various circumstances. Obviously std::list has built in methods for this but they involve (behind the scenes) iterating through the entire list and are therefore inefficient. In principle, I don't see why I couldn't store a pointer to an objects std::list entry as member data, which I could then use to randomly access the linked list. But I'm not sure how to implement this, do I need to store a pointer to the iterator? (I tried this but it doesn't seem to work properly)

[Bazzy]

You can store the iterator itself.
But if you want random-access, why are you using lists? They are meant for sequential access

[PanGalactic]

Ignoring the design issues for just a moment, just store the iterator that element:

list.push_front(this);
this->element = list.begin();

// and then in the destructor
list.erase(this->element);

However, having a class know about all of its instances violates the single responsibility principle. Better to create a factory to track instances of a particular class and require the use of the factory to create new objects.

[m4ster r0shi]

I stumbled upon this the other day:

http://freesoftwarehacker.blogspot.com/2010/06/yo-dawgi-heard-youre-concerned-with.html

It inspired me to write something similar. I initially used a map to store every tenth iterator of my list to speed up access: If I wanted to go to element 127, I would jump to element 120 in O(log(n/10)) time (map lookup) and then walk to 127 in O(1) time (at most 10 steps). Then, I realized I could use a vector instead of a map and thus achieve overall O(1) access time for my list!...

The real drawback is not the memory consumption (it's only 10% more iterators - note, iterators, not list elements) but the fact that inserting/erasing an element in/from the middle of the list now becomes a O(n/10) operation, as you have to update the iterator container every time you insert/erase an element. Nonetheless, I think it's a good tradeoff, and if you add the fact that iterators stay valid as you operate on your list, it really becomes something very tempting to at least play around with for a while.

I compiled the following with -O3 and FastList finished in less than 1 ms, while std::list needed almost 1 s. Try to change '2500's to '5000's and see what happens...

#include <iostream>
#include <list>
#include <vector>
#include <ctime>
using namespace std;

const unsigned ITER_DIFF=10;

template <class T>
struct FastList
{
    typedef typename list<T>::iterator ListIter;

    list<T> data;
    vector<ListIter> iters;

    unsigned size;

    FastList():size(0) {}

    void PushBack(const T & val)
    {
        ListIter it=data.insert(data.end(),val);
        if (size%ITER_DIFF==0) iters.push_back(it);
        size++;
    }

    T & operator[](unsigned pos)
    {
        unsigned search_pos=pos-pos%ITER_DIFF;
        ListIter it=iters[search_pos/ITER_DIFF];
        while (search_pos<pos) {it++; search_pos++;}
        return *it;
    }
};

void AddData(list<int> & l) { for (int i=0; i<10; i++) l.push_back(i); }
void AddData(FastList<int> & fl) { for (int i=0; i<10; i++) fl.PushBack(i); }

int main()
{
    list<int> my_list;
    FastList<int> my_fast_list;

    for (int i=0; i<2500; i++) AddData(my_fast_list);
    for (int i=0; i<2500; i++) AddData(my_list);

    int fsize=my_fast_list.size;
    int size=my_list.size();

    int start, stop;

    start=clock();
    for (int i=0; i<fsize; i++) my_fast_list[i]=0;
    stop=clock();

    cout << "FastList access time: ";
    cout << (stop-start)*1000./CLOCKS_PER_SEC << endl;

    list<int>::iterator it;
    start=clock();
    for (int i=0; i<size; i++)
    {
        it=my_list.begin();
        for (int j=0; j<i; j++) it++;
        *it=0;
    }
    stop=clock();

    cout << "std::list access time: ";
    cout << (stop-start)*1000./CLOCKS_PER_SEC << endl;

    cout << "\nhit enter to quit...";
    cin.get();
    return 0;
}

[simeonz]

I haven't used them, but I think you need http://www.boost.org/doc/libs/1_45_0/doc/html/intrusive.html

These are the boost intrusive containers. They allow you to deal with the nodes inside the container directly. The nodes themselves are user classes that are derived from a base class that only stores the links to other nodes. The "auto-unlink" variant offers the possibility to destroy and unlink a node without referring to the container at all.

As I said, I haven't used them much. I think you can make even more independent node manipulation on your own, with insertion, modification, etc. After all, most containers have recursive structure and the node is actually a smaller container itself. But it will not be trivial.

Regards