STL container for a list with random access?

0
votes

Is there an STL container similar to a list in that elements of lists are not stored contiguously? The size of this container can be up to 1000x1000 elements with each element being a vector containing 36 doubles. This would be a large chunk to store together (like ~200 megabytes). Is there a variant that instead stores pointers to its contents as a separate vector so it would allow for random access. Is there an STL container class for this that already exists or should I just store the pointers manually?

The container I need is actually a constant size so I think implementing it myself wouldnt be too difficult, but I was wondering if an STL container already exists for this. I'd like to avoid a vector because the list is large and the contents will be of medium size. If the vectors in the container don't need to reside next to each other then wouldn't it be better to separate them in a list to prevent running out of memory from fragmentation?

3
c++stl
so... what you want is std::array<std::unique_ptr<T>, length>? - Mooing Duck
What aspect of the performance of std::vector<T> or std::array<T, n> are you concerned about? - ecatmur
OK, you don't need the container to be contiguous. That isn't a reason to avoid vector or array! - ecatmur
Similar to a list in what respect? Fast insertion/deletion at an iterator? Elements never relocate? If all you need is a sequence, then the standard sequences (aside from array) are vector, deque and list. As far as contiguity is concerned, vector is contiguous, deque need not be contiguous but it has random access and for ops like insert/remove in the middle it need not be any faster than if it was, list is non-contiguous and guarantees the benefits (and drawbacks) of non-contiguity. - Steve Jessop
@MooingDuck: it's not clear to me that the outer container must hold a vector: for all that the questioner says it will, people are valiantly arguing in favour of array for the fixed-size rows, so I wanted to cover that case. But if it does hold a vector then agreed. It won't get really big until you're starting to run out of total memory anyway, so it's not going to make a difference of more than (say) a factor of 2-ish in max size that works. - Steve Jessop

3 Answers

1
votes

Both deque<array<double, 36>> and vector<vector<double>> would avoid the need for any really huge contiguous allocations.

The vector<vector<double>> is worse in those terms. For the numbers you specify it needs a contiguous allocation of 1000*1000*sizeof(vector<double>), which is low 10s of MB (most likely a vector is the size of 3 pointers). That's rarely a problem on a "proper computer" (desktop or server). The places where it would be a concern for fragmentation reasons (small virtual address space or no virtual addressing at all), you might also have a more fundamental problem that you don't have 300MB-ish of RAM anyway. But you could play extra-safe by avoiding it, since clearly there can exist environments where you could allocate 300MB total but not 12MB contiguously.

There is no std::array in C++03, but there's boost::array or you could easily write a class to represent 36 doubles.

vector<array<double, 36>> suffers worst from fragmentation, it requires a contiguous 250-MB allocation. Personally I don't find it easy to simulate in testing "the worst possible memory fragmentation we will ever face", but I'm not the best tester. That size of block is about where I start feeling a bit uneasy in a 32 bit process, but it will work fine in good conditions.

0
votes

I highly recommend you to use the std::array class. It is constant sized, it supports random access to all elements, and has implementations of iterator, const_iterator, reverse_iterator, const_reverse_iterator. More about it: http://www.cplusplus.com/reference/stl/array/

0
votes

It isn't clear what characteristic of std::list<T> you are after exactly. If you want a container whose elements stay put when adding or removing elements, you might want to have a look at std::deque<T>: when adding/removing elements at the front or the back all other element stay at the same location. That is, pointers and references to elements stay valid, unless elements are add or removed in the middle. Iterators get invalid on any insertion or removal. std::deque<T> provides random access.

There is no container directly given random access and support addition/removal at any poistion with the elements staying put. However, as others have pointed out, using a container of pointers provides such an interface. It may be necessary to wrap it to hide the use of pointers.