All geek questions in one place

What's better, an STL list or an STL map for 20 entries, given the insertion order, is just as important as search speed

I have the following scenario. Implementation is required for a real-time application.

1) I need to store a maximum of 20 entries in a container (STL Map, STL List, etc.). 2) If there is a new record, and already 20 records, I have to overwrite the old record with a new record.

Given point 2, I feel that the container is full (maximum 20 entries) "list" is the best bet since I can always delete the first entry in the list and add a new one finally (push_back). However, the search will not be so effective.

For only 20 entries, is this really significant in terms of search efficiency if I use a list instead of a map?

Also, given the cost of inserting on the map, do I feel I have to go after the list?

Could you tell me which is better for me?

+3
source share
8 answers

Only 20 elements, I would not worry about which container you use. If you determine that the selected container is actually detrimental to the performance of your application, it should be relatively easy to change the selected container and replace it later with a more efficient container.

, std:: deque, , , . std::vector, std:: deque , . std:: list, std:: deque .

+2
1) 20 (STL Map, STL List ..). 2) 20 , .

, boost:: circle_buffer.

, . , .

_ , STL. , std:: list std:: deque. , std-. round_buffer . , ( , ), .

round_buffer , , , . , circle_buffer_space_optimized. round_buffer, , .

, 20 ( ), "" , , , , STL.

+8

: .

std::map , . , . list, a deque a vector. , list, ( ) - .

map, , : O (log n). 20 . a std::set.

+3

. STL .

+1

.

, , , , , .

O() , , C O (N + C) + C .

, (, ) , .

+1

, . . Binary Heap .

0

, ?

, , , , , .

0

Source: https://habr.com/ru/post/1740737/

More articles:


All Articles