List of arrays vs list

Question

A list uses a lot of memory since it adds a pointer to each node, and it is not contiguous, the memory is there fragmented ... A List of arrays in my opinion is a lot better. For example if I am managing 100 object, A list of 5 arrays of 20 is a lot better than a List of 100, only 5 Pointers added vs 100 pointers, we win locality, when using the same array, and we have less fragmentation. I did some research about this, but I can't find any interesting article about this, so I thought I am missing something.

What can be the benefit of using a List over a List of arrays ?

EDIT : This is definetely not Array vs List ... It is more like why putting only one element per list Node if it's possible to put more

Why bothering with `std::list` inefficiencies, if you can simply use `std::vector`? — πάντα ῥεῖ, May 22 '15 at 09:20
possible duplicate of [Array versus linked-list](http://stackoverflow.com/questions/166884/array-versus-linked-list) — BlackDwarf, May 22 '15 at 09:22
I can't use `std::vector` since I am managing a very large number of large objects — Othman Benchekroun, May 22 '15 at 09:22
@OthmanBenchekroun _"I can't use `std::vector` since I am managing a very large number of large objects"_ What qualifies `std::list` to be better then? — πάντα ῥεῖ, May 22 '15 at 09:27
If you are talking about Vectors of objects, then this is not even possible since the vector needs to be contiguous, and it is difficult to find such a large free block, a vector of pointers can be compared to list, but then again the list is better since I don't have to reserve memory, and if I don't do that with vector, the vector will be doing some useless copies everytime it needs more memory — Othman Benchekroun, May 22 '15 at 09:30
You might want to consider using a [std::deque](http://en.cppreference.com/w/cpp/container/deque), it does what you are describing under the hood but presents an `API` like a `std::vector` or an `array`. **quote:** "typical implementations use a sequence of individually allocated fixed-size arrays" — Galik, May 22 '15 at 09:30
@Galik I don't really understand your quote, however deque seems like what I am describing, but I still didn't get an answer to my question, that is the advantage of list over deque now — Othman Benchekroun, May 22 '15 at 09:36
I didn't have an answer but what strikes me is you have more control with the list of arrays but less convenience and more room for adding bugs. I would generally stick with standard containers unless they prove inadequate. The chances are a standard container will be implemented better and more efficiently that you could come up with yourself - being that they are refined over time and tested by a massive user-base. At least *that* is the theory ;o) — Galik, May 22 '15 at 09:43
I am sure that's implementation dependant. But I would imagine it would use less because (like your scheme) it uses a list of contiguous blocks. So each node accounts for many elements whereas a list has a node for each element. — Galik, May 22 '15 at 09:53

score 2 · Accepted Answer · answered May 22 '15 at 09:56

I think this is a valid question as memory location might affect the performance of your program. You can try std::deque as some suggested. However, the statement that a typical implementation uses chunks of memory is a general statement about implementation, not standard. It is therefor not guaranteed to be so.

In C++, you can improve the locality of your data through custom allocators and memory pools. Every STL container takes as a parameter allocator. The default allocator is probably a simple wrapper around new and delete but you can supply your own allocator that uses a memory pool. You can find more about allocators here and here is a link to the C++ default allocator. Here is a dr.dobbs article about this topic. A quote from the article:

If you're using node-based containers (such as maps, sets, or lists), allocators optimized for smaller objects are probably a better way to go.

Only profiling will tell you what works best for your case. Maybe the combination of std::deque and a custom allocator will be the best option.

score 1 · Answer 2 · edited May 23 '17 at 12:05

Some operations have guaranteed constant-time complexity with std::list and not with std::vector or std::deque. For example, with std::list you can move a subsequence ("splice") of 5000 consecutive elements from the middle of a list with a million items to the beginning (of the same list only!) in constant time. No way to do that with either std::vector or std::deque, and even for your list-of-arrays, it will be a fair bit more complicated.

This is a good read: Complexity of std::list::splice and other list containers

List of arrays vs list

2 Answers2