52

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

0

7 Answers 7

129

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.
3
  • 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.
    – alicederyn
    Aug 5, 2010 at 8:20
  • 1
    @chrispy: std::vector<std::pair<X, Y> > offers O(log n) lookup ONLY when it is sorted
    – jpalecek
    Aug 5, 2010 at 9:07
  • yes indeed, hence it's O(n) to insert once sorted and thus best for static data
    – alicederyn
    Aug 7, 2010 at 20:37
27

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)

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

3

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

1

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.

2
  • 3
    STL maps are not implemented by hashmaps, but red-black (or the like) trees.
    – jpalecek
    Aug 2, 2010 at 16:40
  • 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. Aug 2, 2010 at 18:26
1

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

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.