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

c++ stl stdmap std-pair stdlist
Boolean picture Boolean · Aug 2, 2010 · Viewed 62.8k times · Source

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

Answer

jpalecek picture jpalecek · Aug 2, 2010

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.

Related questions

Use of for_each on map elements

I have a map where I'd like to perform a call on every data type object member function. I yet know how to do this on any sequence but, is it possible to do it on an associative container? The …

Read More
What is the preferred/idiomatic way to insert into a map?

I have identified four different ways of inserting elements into a std::map: std::map<int, int> function; function[0] = 42; function.insert(std::map<int, int>::value_type(0, 42)); function.insert(std::pair<int, int>(0, 42)); function.…

Read More
Initializing a static std::map<int, int> in C++

What is the right way of initializing a static map? Do we need a static function that will initialize it?

Read More