Ще видя ли увеличение на производителността, използвайки std::map вместо vector‹pair‹string, string› ›?

Не. Ако (както казвате) просто итерирате колекцията, ще видите малко (вероятно неизмеримо) намаляване на производителността чрез използване на std::map.

Картите са за достъп до стойност чрез нейния ключ. Ако никога не правите това, map е лош избор за контейнер.

Ако не модифицирате своя vector<pair<string,string> > - просто го итерирате отново и отново - ще получите влошаване на производителността, като използвате map. Това е така, защото типичният map е организиран с двоично дърво от обекти, всеки от които може да бъде разпределен в различни блокове памет (освен ако не напишете собствен разпределител). Плюс това, всеки възел на map управлява указатели към съседни обекти, така че това също е време и памет. Но търсенето по ключ е O(log) операция. От друга страна, vector съхранява данни в един блок, така че кешът на процесора обикновено се чувства по-добре с него. Търсенето във вектор всъщност е O(N) операция, която не е толкова добра, но приемлива. Търсенето в сортирания вектор може да бъде надстроено до O(log) с помощта на функции на lower_bound и т.н.

Зависи от операциите, които извършвате с тези данни. Ако правите много търсения - вероятно е по-добре да използвате хеширащ контейнер като unordered_map, тъй като търсенето по ключ в тези контейнери е O(1) операция. За итерация, както споменахме, vector е по-бързо.

Вероятно си струва да замените string във вашия pair, но това много зависи от това какво държите там и как имате достъп до контейнера.

Отговорът зависи от това какво правите с тези структури от данни и какъв е размерът им. Ако имате хиляди елементи във вашия std::vector<std::pair<std::stringm std::string> > и продължавате да търсите елемента first отново и отново, използването на std::map<std::string, std::string> може да подобри производителността (може да обмислите използването на std::unordered_map<std::string, std::string> за този случай на употреба вместо това). Ако вашите вектори са относително малки и не се опитвате да вмъквате елементи в средата твърде често, използването на вектори може да бъде много по-бързо. Ако просто итерирате върху елементите, векторите са много по-бързи от картите: итерациите всъщност не са една от силните им страни. Картите са добри в разглеждането на нещата, ако приемем, че броят на елементите не е наистина малък, защото в противен случай линейното търсене върху вектор е все още по-бързо.

Най-добрият начин да определите къде е изразходвано времето е да профилирате кода: често не е напълно ясно отпред къде е изразходвано времето. Често предполагаемите горещи точки всъщност не са проблемни, а други области показват неочаквани проблеми с производителността. Например, може да предавате на своите обекти моята стойност, а не чрез препратка на някое неясно място.

Ако вашият модел на използване е такъв, че извършвате много вмъквания, преди да извършите каквото и да е търсене, тогава може да се възползвате от прилагането на „мързелива“ карта, където елементите се сортират при поискване (т.е. когато придобиете итератор, извършите търсене и т.н.).

Както C++ казва std::vector сортира елементи в линейна памет, така че първо разпределя блок памет с първоначален капацитет и след това, когато искате да вмъкнете нов елемент във вектор, той ще провери дали има повече място или не и ако не, ще разпредели нов буфер с повече място, копирайте конструирайте всички елементи в нов буфер и след това изтрийте изходния буфер и го настройте на нов.

Когато току-що започнете да вмъквате елементи в vector и имате много елементи, страдате от твърде много преразпределения, копиране на конструкции и извикване на деструктор.

За да разрешите този проблем, ако сега преброите входните елементи (не точно, но обичайната му дължина), можете да reserve малко памет за вектора и да избегнете преразпределението и всичко друго. ако нямате представа за размера, можете да използвате колекция като std::list, която никога не преразпределя своите вътрешни елементи.