# Introduction of Container Map in C++ Standard Template Library (STL) - Updated 2022/01/23

## Brief

Maps are associative containters that store elements formed by a combination of a key value and a mapped value, following a specific order.

In a map, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key, and typically implemented as binary search trees.

The type of key and mapped value map may differ, and are grouped together in member type value_type, which is a pair type combining both:

typedef pair< const Key, T > value_type;

## Exercise 1: (Leetcode) 1128. Number of Equivalent dominoes Pairs

Description: Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either (a==c and b==d), or (a==b and b==c) - that is, one domino can be rotated to be equal to another domino.

Return the number of pair (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

Solution:

typedef pair< int, int > two_int;
int Dynamic_Array_Exercise::numEquivDominoPairs_opt(vector< vector< int > >& dominoes) {
int result = 0;
map< pair< int, int >, int > dict;

for(int i=0; i<dominoes.size(); i++){
int a = dominoes[i][0], b = dominoes[i][1];
// Sorting
two_int key = {min(a, b), max(a, b)};
// Count the same pair
dict[key] += 1;
}

for(auto it = dict.begin(); it != dict.end(); it++){
int value = it->second;
result += value * (value-1) / 2;
}
return result;
}

The basic functions for caculating the number of equivalent dominoes pairs are as follows:

• Sorting the dominoes and count the number of equivalent dominoes pair
• Calculate the arithmetic series and summarize

## Exercise 2: Number of Fractions that Sum to 1

Description: Given a list of lists fractions where each list contains [numerator, denominator] which represents the number numerator/denominator.

Return the number of pairs of fractions there are sums to 1.

Solution:

int Solutions::sumFraction( std::vector < std::vector <int > > & fracrion)
{
std::map < std::pair < int, int >, int > dict;
int ans = 0;

for (auto& elem : fracrion) {
int g = gcd(elem[0], elem[1]);
dict[{elem[0]/g, elem[1]/g}]++;
}

for (auto it = dict.begin(); it != dict.end() ; it++) {
std::pair <int, int > key = it->first;
int count = it->second;

if (key.first * 2 > key.second) continue;
if (key.first * 2 == key.second) {
ans += count * (count - 1) /2;
} else {
auto it_match = dict.find({key.second - key.first, key.second});
if ( it_match!= dict.end()) ans += count * it_match->second;
}
}
return ans;
}

The solution was initially extracted from binary search: fractions and then reworked. The basic functions for caculating the number of pairs of fractions there are sums to 1 are as follows:

• Accumulate the pair of 1/2
• Accumulate the rest of pair of the fractions there are sums to 1

=========== To be continued…. ==========

## Reference

[3] Binarysearch

If you have any constructive criticism or advises, leave the comments below or feel free to email me @qazqazqaz850@gmail.com. Hope this post will help! :)