Accessing elements of a list of lists in C++

Question

I have a list of lists like this:

    std::list<std::list<double> > list;

I filled it with some lists with doubles in them (actually quite a lot, which is why I am not using a vector. All this copying takes up a lot of time.)

Say I want to access the element that could be accesed like list[3][3] if the list were not a list but a vector or two dimensional array. How would I do that?

I know that accessing elements in a list is accomplished by using an iterator. I couldn't figure out how to get out the double though.

Solution 1

double item = *std::next(std::begin(*std::next(std::begin(list), 3)), 3);

Using a vector would usually have much better performance, though; accessing element n of a list is O(n).

If you're concerned about performance of splicing the interior of the container, you could use deque, which has operator[], amortized constant insertion and deletion from either end, and linear time insertion and deletion from the interior.

For C++03 compilers, you can implement begin and next yourself:

template<typename Container>
typename Container::iterator begin(Container &container)
{
    return container.begin();
}
template<typename Container>
typename Container::const_iterator begin(const Container &container)
{
    return container.begin();
}
template<typename T, int n>
T *begin(T (&array)[n])
{
    return &array[0];
}

template<typename Iterator>
Iterator next(Iterator it, typename std::iterator_traits<Iterator>::difference_type n = 1)
{
    std::advance(it, n);
    return it;
}

Solution 2

To actually answer your question, you should probably look at std::advance.

Solution 3

To strictly answer your question, Joachim Pileborg's answer is the way to go:

std::list<std::list<double> >::iterator it = list.begin();
std::advance(it, 3);
std::list<double>::iterator it2 = (*it).begin();
std::advance(it2, 3);
double d = *it2;

Now, from your question and further comments it is not clear whether you always add elements to the end of the lists or they can be added anywhere. If you always add to the end, vector<double> will work better. A vector<T> does not need to be copied every time its size increases; only whenever its capacity increases, which is a very different thing.

In addition to this, using reserve(), as others said before, will help a lot with the reallocations. You don't need to reserve for the combined size of all vectors, but only for each individual vector. So:

std::vector<std::vector<double> > v;
v.reserve(512); // If you are inserting 400 vectors, with a little extra just in case

And you would also reserve for each vector<double> inside v. That's all.

Take into account that your list of lists will take much more space. For each double in the internal list, it will have to allocate at least two additional pointers, and also two additional pointers for each list inside the global least. This means that the total memory taken by your container will be roughly three times that of the vector. And all this allocation and management also takes extra runtime.