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::pair<A,B> > и std::map<A,B>
Примечание: отредактировано после издания вопроса.
Таким образом, на первый взгляд карта пар и список пар могут показаться одинаковыми. Но это не тот случай:
Карта изначально упорядочена предоставленным функтором, в то время как список будет хранить пары [A, B] там, где вы их положили. Это делает вставку O (log n) для карты, тогда как необработанная вставка внутри списка представляет собой постоянную сложность (поиск, куда ее вставить, является другой проблемой).
Вы можете имитировать поведение карты, используя список пар, но учтите, что карта обычно реализована в виде дерева элементов, тогда как список представляет собой цепочку списков элементов. Таким образом, такой алгоритм, как дихотомия, будет работать намного быстрее на карте, чем в списке.
Таким образом, поиск элемента на карте - это O (log n), тогда как в неупорядоченном списке это O (n). И если список упорядочен, и вы хотите использовать дихотомию, вы не получите ожидаемого прироста производительности, поскольку обход списка элементов в любом случае выполняется поэлементно.
( В проекте, над которым я работал год назад, мы заменили список упорядоченных элементов набором одинаковых упорядоченных элементов, что повысило производительность. Набор, имеющий ту же внутреннюю древовидную структуру, что и карта Я думаю, что то же самое усиление применимо и здесь )