Memory efficient version of std :: map

Question

I use std::mapabout 20 million records to store. If they were saved without any container overhead, it would take approximately 650 MB of memory. However, since they are stored using std::map, it uses about 15 GB of memory (i.e. Too much).

The reason I use std::mapis because I need to find keys that are equal / greater / less than x. That's why something like sparsehashthis won't work (because, using this, I can't find the keys by comparison).

Is there an alternative to using std::map(or ordered cards in general), which will lead to less memory usage?

EDIT: Write performance is much more important than read performance. He will probably only read ~ 10 records, but I don’t know which records he will read.

Answer 1

It turns out there was no problem std::map.

I realized that I used 3 separate cards to represent different parts of the same data, and after losing weight to 1, the difference in memory was completely insignificant.

Looking at the code a bit more, I realized that the code that I wrote to free up a really expensive structure (on a map element) didn't actually work.

Fixing this part, it now uses <1 GB of memory, as it should be! :)

---

TL; DR: std::map . .

Answer 2

" " , ? , , std::vector .

, , (O (N * log N), std::map, ), ( O (logN) std::map).

, , . , , " " , , , , .

Answer 3

- flat_map Boost.Containers: , std::map, ( std::vector) . , .

, , , - back-end. , .

Answer 4

:

• Insert must be quick
• There are many items to read.
• Rollback may be slow
• You only read data once.

I would review typedef std::pair<uint64, thirty_six_byte_struct> element;and fill out std::list<element>. It will be hard to beat in terms of performance.

For reading, I will just go through the linked list, checking each point if you need one of these elements. This is an O (N) workaround, but as you say, you only do it once.