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.

Slotter

You should use vector. Use list only when you need to splice. – Evalynevan

@Evalynevan if you don't need random-access and you need remove elements from begin/middle of container - using vector is very bad idea. – Dissentious

use vector::reserve to reserve the memory and avoid extra copies if that is your concern. Also, even though you can get operator[] for what you want, it will be really inefficient. – Organization

std::vector is usually pretty smart when it needs to reallocate, so the bigger it gets the less it has to reallocate and copy. std::list is only faster if you are creating the container many many times during the lifetime of the program. – Rooted

@ForEveR, you're right, if you need to insert/remove from begin/middle, you shouldn't use vector either. Just because you don't need random access doesn't mean that you shouldn't use vector though. – Evalynevan

there's a list data structure in boost that offers both the capabilities of std::vector and list\ – Heterodox

Answer 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;
}

Woodsman

On accessing it does, but not on inserting. The vector has to be copied to a new memory location each time it's size is expanded. Since the list will later on (not for testing purposes) be accessed in a linear way, taking a look at each element, I think it does not matter that it is a list and has linear lookup time for one element – Slotter

@oaktree: Besides that you can reserve() to alleviate this, it allocates always so much extra space that it does not have to reallocate on every resize. – Prudy

@Prudy I could reserve the memory if I knew exactly how many elements need to be added. I am adding about 512 elements per list and have about 400 lists. I know that is not yet a huge amount, but quite a bit... – Slotter

@Woodsman My stl does not seem to have std::next() or including iterator is simply not enough. It also seems to lack std::begin() – Slotter

@Slotter std::next and std::begin were added in C++11. – Woodsman

@Woodsman I guess it will take some time until the cl compiler will support that^^ – Slotter

@Slotter Assuming you're referring to Visual Studio, Microsoft have been adding C++11 features since VC10, and VC12 is reputedly pretty good. It's easy to write a compatibility replacement for std::next; I'll show it above. – Woodsman

Answer 2

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

Rooted

Answer 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.

Knorring

advance won't work on a temporary such as returned by begin. You need to use next. – Woodsman

I forgot to add something. If you don't really know the final size of the container and are concerned about allocating too much space or too little, consider using deque<>. It is generally a bit slower than vector<>, but grows much better, since it does not need to copy itself. For this reason, deque<> has no method reserve(). – Knorring

@ecatmur: In fact, advance() does not work the way I wrote. I am editing the code. – Knorring