What is the difference between std list std pair and std map in C STL

Question

What distinguishes std::list<std::pair> from std::map?

Does the list also include a search method?

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