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

Question

What is the difference between std::list<std::pair> and std::map? Is there a find method for the list, too?

Solution 1

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.

Solution 2

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)

Solution 3

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.

Solution 4

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

Solution 5

Map can provide the better searching time in the range of O(log n), whilw list can have the searching time of O(n).

View more solutions

Comments

[BetweenTwoTests]

STL maps are not implemented by hashmaps, but red-black (or the like) trees.

[Dennis Zickefoose]

There are a few places where the STL documentation does not match the requirements set by the C++ standard, so reading the STL API can get you aren't actualy using it.

[Alice Purcell]

For completeness: std::vector<std::pair<X, Y> > offers O(log n) lookup, and is smaller (and should be faster) than a map for immutable data. Useful for e.g. a static, frequently-used lookup. But use a map until you show the optimization will provide real benefits.

[BetweenTwoTests]

@chrispy: std::vector<std::pair<X, Y> > offers O(log n) lookup ONLY when it is sorted

[Alice Purcell]

yes indeed, hence it's O(n) to insert once sorted and thus best for static data