What is the difference between std::list<std::pair> and std::map in C++ STL?

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.

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)

(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.