Различие между станд.:: список <станд.:: пара> и станд.:: карта в C++ stl

(Отредактировано после уточнения)

std :: map оптимизирован для быстрого поиска. У него есть собственный метод find , который использует его внутреннюю структуру для обеспечения хорошей производительности. Как правило, он будет проверять только ключи log (N) , где N - количество элементов на карте.

std :: list - это простой связанный список, поэтому он поддерживает только поэлементный обход. Вы могли использовать отдельный алгоритм std :: find или std :: find_if с настраиваемым предикатом, который проверяет только первый член чтобы лучше соответствовать семантике std :: map :: find , но это будет очень медленно. Фактически, ему придется проверять каждую пару в списке для любого неудачного поиска и в среднем искать половину для любого успешного.

std::pair

std:: pair - это шаблонизированная кортеж-структура, ограниченная двумя элементами, называемыми первым и вторым:

std::pair<int, std::string> myPair ;
myPair.first = 42 ;
myPair.second = "Hello World" ;

std::pair используется как "общий контейнер" в STL (и другом коде) для объединения двух значений одновременно без необходимости переопределения еще одной struct.

std::map

std::map - это шаблонный ассоциативный контейнер, связывающий вместе ключи и значения. Самый простой (но не более эффективный) пример :

std::map<int, std::string> myMap ;
myMap[42] = "Fourty Two" ;
myMap[111] = "Hello World" ;
// ...
std::string strText ;  // strText is ""
strText = myMap[111] ; // strText is now "Hello World"
strText = myMap[42] ;  // strText is now "Fourty Two"
strText = myMap[23] ;  // strText is now "" (and myMap has
                       // a new value "" for key 23)

std::pair и std::map

Примечание: Это был ответ на первоначальный, неотредактированный вопрос.

Функции std::map должны возвращать итераторы ключей и значений одновременно, чтобы оставаться эффективными... Поэтому очевидным решением является возврат итераторов к парам:

std::map<int, std::string> myMap ;
myMap[42] = "Fourty Two" ;
myMap[111] = "Hello World" ;

myMap.insert(std::make_pair(23, "Bye")) ;

std::map<int, std::string>::iterator it = myMap.find(42) ;
std::pair<int, std::string> keyvalue = *it ;    // We assume 42 does
                                                // exist in the map
int key = keyvalue.first ;
int value = keyvalue.second ;

std::list > и std::map

Примечание: отредактировано после редакции вопроса.

Таким образом, на первый взгляд, карта пар и список пар - одно и то же. Но это не так:

Карта изначально упорядочена предоставленным функтором, тогда как список будет хранить пары [A,B] там, куда вы их положили. Это делает вставку O(log n) для карты, в то время как необработанная вставка внутри списка является постоянной сложностью (поиск места вставки - это другая проблема).

Вы можете в некоторой степени имитировать поведение карты, используя список пар, но обратите внимание, что карта обычно реализуется как дерево элементов, в то время как список - это цепочечный список элементов. Таким образом, алгоритм типа дихотомии будет работать намного быстрее в карте, чем в списке.

Таким образом, найти элемент в карте можно за O(log n), тогда как в неупорядоченном списке - за O(n). И если список упорядочен, и вы хотите использовать дихотомию, вы не получите ожидаемого прироста производительности, так как обход списка элементов в любом случае выполняется элемент за элементом.

(В проекте, над которым я работал год назад, мы заменили список упорядоченных элементов на набор таких же упорядоченных элементов, и это увеличило производительность. Набор имеет ту же внутреннюю древовидную структуру, что и карта, и я полагаю, что здесь применим тот же эффект)

STL карты - это ассоциативные массивы, обычно реализуемые как хэшмапы внутри. Если вы хотите получить итерацию по карте STL, она вернет пару STL.

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
        map<string, int> myMap;
        myMap["myKey"] = 1337;

        map<string, int>::iterator myIterator = myMap.begin();

        pair<string, int> myPair = *myIterator;

        cout<<"the key \""<<myPair.first<<"\" maps to the value of "<<myPair.second<<endl;
        cout<<"the key \"myKey"\" maps to the value of "<<myMap["myKey"]<<endl;
        return 0;
}

Я бы посоветовал погуглить и прочитать полный справочник по STL API, поскольку STL (за исключением хранения булевых чисел в векторах и других подобных странностей) реализует множество функций структур данных, которые вы захотите использовать в любой программе, не изобретая колесо.

std: pair содержит ровно два объекта. std: map содержит коллекцию парных объектов.

Вы не можете использовать find () для пары, потому что там нечего искать. Вам нужен объект пара. Первая или пара. Второе

ОБНОВЛЕНИЕ: Предполагая, что вы имели в виду разницу между map <> и list > : Map должна быть реализована для быстрого поиска по ключевому элементу . list имеет простой линейный список. Для поиска элемента в списке необходимо просмотреть весь список. Однако std :: find () будет работать с обоими.

std :: pair предназначена только для группировки ровно 2 объектов (скажем, «координаты на странице» состоят из X и Y).

std :: map - это отображение одного набора объектов в другой.

Нет смысла пытаться использовать метод поиска для пары, так как какой смысл находить что-то в списке из двух вещей, порядок которых вам известен, даже если этот метод поиска существовал в классе пары, который он не.

Однако вы МОЖЕТЕ использовать std :: pair в качестве значения карты, если хотите.