An array of pairs instead of an STL map - possible? What are the pros and cons? [duplicate]

Question

Why are c++ standard maps very famous for, whereas an array of pairs is also similar those?

When would it be better to use c++ standard maps, and when to use an array of pairs? Or are the applications similar for both?

Answer 1

Why are c++ standard maps very famous for, whereas an array of pairs is also similar to those?

The following table should give you a small idea, where to use c++ standard maps (only choose some) rather an array of pairs.

---

When would it be better to use c++ standard maps, and when to use an array of pairs?

You can always benchmark the efficiency of your data-structure, to see which one is apt for which situations.

Let's look into an example.

For instance, the followings are the bench-mark done in https://quick-bench.com/, for the insertion of 10000 elements in the beginning of each

1. array of pairs (i.e. std::vector<std::pair<int, std::string>>) vs
2. standard map (i.e. std::map<int, std::string>) vs
3. standard hash-map (i.e. std::unordered_map<int, std::string>).

It turned out that using the C++ standard maps is faster/efficient than array of pairs for this kind of operations.

(See online bench-mark)

However, for the case of fewer entries (let's consider 10 elements), the same test shows that the usage of array of pairs (i.e. std::vector<std::pair<int, std::string>>) would be faster/efficient than standard hash-map (i.e. std::unordered_map<int, std::string>), and alomost equalent to standard map (i.e. std::map<int, std::string>).

(See online bench-mark)

---

In short, the thumb rule is, always bench-mark and test for the operations what you will be having, before choosing the right data structure for best results. For further references have a look std::vector, std::map, std::unordered_map, etc and their individual operations.

Answer 2

You use a Map when you are trying to do just that, map one item to another. An array of pairs is just storing a bunch of pairs and it provides no map functionality since you are still constrained by the index of the array.

A map is also handy for counting frequencies. Since a map (the standard map at least, there are variations of maps that allow duplicates) will not duplicate key values. You can use that to find the frequency of an element etc.

The main reason to use a map is when you want to find a value based on a key that you get to define. Its not so much about just storing items together as in a pair.