Geek asks and answers

C ++: replacing container for vector / deque for huge sizes

therefore my applications have containers with 100 million or more elements.

I am in search of a container that behaves in time - better than std :: deque (not to mention std :: vector) regarding frequent inserts and deletes throughout the container ... including near the middle, Access time to n -th element does not have to be as fast as the vector, but it should be better than a full crawl, as in std :: list (which in any case has huge memory overhead for each element).

Elements must be processed by index (e.g. vector, deque, list), so std :: set or std :: unordered_set also doesn't work well.

Before you sit down and encode such a container: has anyone seen such a beast already? I'm pretty sure STL has nothing of the kind when looking at BOOST. I did not find something that I could use, but I could be wrong.

Any clues?

+5
source share
4 answers

I think you can get the performance characteristics you want using the skip list:

https://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist

This, of course, is the "indexed" part that you are interested in - you really do not want the elements to be sorted. Therefore, some modification is required, which I leave as an exercise.

, 100 32- , , , 64 .

+1

STL , :

edit: . 100 . , , 96MiB. , STXXL , .

+3

1) , .. , , :

2) Hash O (1) , sparsehash, , ; sparsetable, .

3) (, , , ), swap , , resize O (1). push_back.

0

Try a hash map. The STL has several, all with an unordered naming prefix, such as unorderd_map, etc. It has a constant time insertion and search considering a good hashing algorithm. Given your “huge” data, the hash map is likely to cover your needs. A small change in the application to cover interface differences is trivial.

0
source

More articles:


All Articles