Difference between std::list<std::pair> and std::map in C++ stl

Question

Hi,

Can you please tell me the difference between std::list<std::pair> and std::map. Can I used find method on list too?

Thank you.

-- Clarification

Question edited to be more clear.

Answer 1

(Edited after clarification)

std::map is optimized for fast searching. It has its own find method that uses its internal structure to provide good performance. In general, it will only inspect log(N) keys, where N is the number of items in the map.

std::list<std::pair> is a simple linked list, and so only supports element-by-element traversal. You could use the separate std::find algorithm, or std::find_if with a custom predicate that only examines the first member to better match the semantics of std::map::find, but that would be very slow. In fact, it will have to look at every pair in the list for any failed search, and will look at half on average for any successful one.

Answer 2

std:pair holds exactly two objects. std:map hold a collection of paired objects.

You cannot use find() on pair, because there is nothing to find. The object you want is either pair.First or pair.Second

UPDATE: Assuming you meant the difference between map<> and list<pair<> >: Map should be implemented for fast lookup on the key member. list has just a simple linear list. Looking up an item in a list requires running through the whole list. However, std::find() will work on both.

Answer 3

std::pair is just for grouping together exactly 2 objects (say, "coordinates on a page" is comprized of X and Y).

std::map is a mapping from one set of objects to another.

There's no point of trying to use a find method on a pair, as what's the point of finding something in a list of two things of which you know the order to, even if that find method existed in a pair class which it does not.

However, you CAN use std::pair as a map value if that's what you want.

Answer 4

std::pair

std::pair is a templated tuple-structure limited to 2 items, called first and second:

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

std::pair is used as a "generic container" by the STL (and other code) to aggregate two values at the same time without having to redefine yet another struct.

std::map

std::map is an templated associative container, associating keys and values together. The easiest (but not more efficient) example is :

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 and std::map

Note: This was the answer to the original, unedited question.

The std::map functions needs to return iterators to the keys and values at the same time to remain efficient... So the obvious solution is to return iterators to pairs:

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> > and std::map<A,B>

Note: Edited after edition of the question.

Thus, at first glance, a map of pairs and a list of pairs would seem the same. But this is not the case:

The map is inherently ordered by the functor provided, whereas the list will keep the pairs of [A,B] right where you put them. This makes insertion O(log n) for the map, whereas raw insertion inside a list is a constant complexity (searching where to insert it is another problem).

You can simulate somewhat the behavior of a map using a list of pairs, but note that the map is usually implemented as a tree of items, whereas the list is a chained list of items. Thus, algorithm like dichotomy will work a lot faster in a map than in a list.

Thus, finding an item in a map is O(log n), whereas in an unordered list, it is O(n). And if the list is ordered, and you want to use dichotomy, you won't get the expected performance boost, as the traversal the list of items is done item by item anyway.

(In a project I worked on one year ago, we replaced a list of ordered items by a set of the same ordered items, and it boosted the performance. The set having the same internal tree structure as the map, I guess the same boost would apply here)

Answer 5

STL maps are associative arrays, usually implemented as hashmaps inside. If you want to get iterate over an STL map it'll return an STL pair.

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

I'd suggest googling and reading the complete STL API reference since STL (with the exception of storing booleans in vectors and other oddities like that) implements a lot of data structure functionality you'd want to use in any program without reinventing the wheel.

Answer 6

std::map<X, Y>:

• is an ordered structure with respect to keys (that is, when you iterate over it, keys will be always increasing).
• supports unique keys (Xs) only
• offers fast find() method (O(log n)) which finds the Key-Value pair by Key
• offers an indexing operator map[key], which is also fast

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

• is a simple sequence of paired Xs and Ys. They remain in the order you put it in.
• can hold any number of duplicates
• finding a particular key in a list is O(N) (no special method)
• offers the splice method.