В чем разница между std::list‹std::pair› и std::map в C++ STL?

std::map<X, Y>:

• является упорядоченной структурой по отношению к ключам (то есть, когда вы перебираете ее, ключи всегда будут увеличиваться).
• поддерживает только уникальные ключи (Xs)
• предлагает быстрый метод find() (O(log n)), который находит пару ключ-значение по ключу
• предлагает оператор индексации map[key], который также быстро

std::list<std::pair<X, Y> >:

• представляет собой простую последовательность парных Xs и Ys. Они остаются в том порядке, в котором вы их положили.
• может содержать любое количество дубликатов
• поиск определенного ключа в list равен O(N) (без специального метода)
• предлагает метод splice.

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). И если список упорядочен, и вы хотите использовать дихотомию, вы не получите ожидаемого прироста производительности, так как обход элементов в любом случае выполняется поэлементно.

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

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

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

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

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

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

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

Карты 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;
}

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

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

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

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

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

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