Это одинаково быстро?(Карта и Список)

Question

Какой из них быстрее?Фрагмент А или Фрагмент Б?Или они будут более или менее одинаковыми?

Я знаю, что это непрактичные программы;это только для целей обучения.

list<string> A(1000);
//assign random string values to each entry in A (code not shown). 
//At least one of the strings is "test"
list<string>::iterator it;

//BEGINNING OF FRAGMENT A:
for(it=A.begin(); it!=A.end(); it++){
    if((*it)=="test"){
        cout << "found";
        break;
    }
}
//END OF FRAGMENT A

.

map<string,bool> B(1000);
//assign random string values to each entry in B (code not shown). 
//At least one of the strings is "test".
//B[any string]=1 (code not shown)
//
//BEGINNING OF FRAGMENT B:
if(B["test"]) cout << "found";
////END OF FRAGMENT B

Answer 1

Первый всего, что вы должны профилировать.

Второй; они не равны, поскольку B["test"] вставит элемент, если его нет в контейнере.if(B.count("test") != 0) - правильный способ сделать это.

В-третьих; B быстрее и получит больше, чем контейнер, поскольку он выполнит двоичный поиск в отсортированном контейнере; O (log (N)) вместо O (N) .

Forth; std :: hash_set или hash_map, вероятно, то, что выищем как еще быстрее чем std :: map

Answer 2

Поиск по списку имеет наихудший вариант сложности O (n), где, как если бы map делал это в O (log n) так что карта быстрее, когда дело доходит до поиска.

Answer 3

карту быстрее найти по ключевой информации.

Answer 4

Поиск по связанному list имеет линейную сложность, O (n), тогда как поиск по map будет иметь логарифмическую сложность, O (log n).

В качестве альтернативы, вы можете использовать set тип.

Answer 5

B намного быстрее.В A вы должны пройти весь список, который является операцией O(n).

Карты обычно реализуются в виде деревьев, что дает O(log(n)) время.