Разница между std:: list <std:: pair> и std:: map в С++ stl

Ответ 1

std::map<X, Y>:

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

Ответ 5

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;
}

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

Ответ 6

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

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

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

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

Ответ 7

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