2.6.2. Map and Set

In C++ STL, map and set, including multimap and multiset, are basically binary search trees. The time complexities of search, insert and delete are O(LogN). The difference is set is used to store only keys while map is used to store key value pairs.

To use any object as a key in map/set, we have to tell the map/set how to compare the two objects using a comparison function in the third parameter of the template. We can:

1. Define less-than operator< inside the object class

2. Use a comparison object

3. Specialize std::less function

One example is:

template<typename T1, typename T2>
struct Node
{
    T1 x;
    T2 y;
    // constructor
    Node(T1 x, T2 y): x(x), y(y) {}
    // overload `<` operator to use a `Node` object as a key in a `std::map`
    // It returns true if the current object appears before the specified object
    bool operator<(const Node &ob) const {
        return x < ob.x || (x == ob.x && y < ob.y);
    }
};

Or we can use the built-in transparent functor greater<>:

set<int, greater<>> s = {1, 2, 3, 4};
for (int i: s) cout << i; // output: 4321
map<int, char, greater<>> m = {{1, 'a'},
                               {2, 'b'}};
for (auto &[x, y]: m) cout << x; // output: 21

Functions to know: erase, count, find, equal_range, lower_bound, upper_bound, insert/emplace.

• 🐾 How to delete one item from multimap?

Erasing by value may cause unexpected result because multimap could have duplicate values. The correct way is to erase by iterator.

nx = a_map.erase(a_map.find(x))

If you want to delete the first item in case there are duplicate values, you can use:

nx = a_map.erase(a_map.lower_bound(x))

The same applied to multiset. Also note the erase method returns the next iterator of the deleted iterator.

2.6.2.1. Entity Spotter

input: string -> "Apple Park is the corporate headquarters of Apple Inc"
        idx   ->  0     1    2  3   4         5            6  7     8
        dict: {"Apple", "Apple Park", "corporate"}
output: {"Apple":{0,1},{7,8}, "Apple Park":{0,2}, "corporate":{4,5}}

Code Block 2.6.8 Entity Spotter

map<string, vector<pair<int, int>>> get_range(string s, const unordered_set<string>& dict){
  map<string, vector<pair<int, int>>> res;
  auto vi = split(s);
  for (int i = 0; i < vi.size(); i++) {
    string n = vi[i];
    if (dict.count(n)) res[n].emplace_back(i, i + 1);
    for (int j = i + 1; j < vi.size(); j++) {
      n += " " + vi[j];
      if (dict.find(n) != dict.end())
        res[n].emplace_back(i, j + 1);
    }
  }
  return res;
}

2.6.2.2. Dynamic Bounding Box

Implement a class, on the x-y plane, there are no points at the beginning, constantly add and remove points, the points are represented by coordinates (x, y), each step returns a minimum box to frame all the points, the box is parallel to x and y axis.

^                                 ^                                 ^
|                                 |       +z(3,5)                   |       +z(3,5)
|                                 |                                 |
|           +y(4,2)        -->    |           +y(4,2)        -->    |
|                                 |                                 |
|     +x(2,1)                     |     +x(2,1)                     |     +x(2,1)
|---------------------->          |---------------------->          |---------------------->
Bounding Box: {{2,1},{4,2}}        {{2,1},{4,5}}                     {{2,1},{3,5}}

Code Block 2.6.9 Dynamic Bounding Box

using PII = pair<int, int>;

struct comp_x{
  bool operator()(const PII& a, const PII &b) const {
    return a.first < b.first;
  }
};

struct comp_y{
  bool operator()(const PII& a, const PII &b) const {
    return a.second < b.second;
  }
};

class dynamic_bbox {
  multiset<PII, comp_x> points_by_x;
  multiset<PII, comp_y> points_by_y;
public:
  void add_point(int x, int y) {
    points_by_x.emplace(x, y);
    points_by_y.emplace(x, y);
  }
  void remove_point(int x, int y){
    if(points_by_x.count({x,y})){
      points_by_x.erase(points_by_x.find({x,y}));
      points_by_y.erase(points_by_y.find({x,y}));
    }
  }
  pair<PII, PII> get_bbox() {
    int min_x = points_by_x.begin()->first;
    int max_x = points_by_x.rbegin()->first;
    int min_y = points_by_y.begin()->second;
    int max_y = points_by_y.rbegin()->second;
    return {{min_x, min_y},{max_x, max_y}};
  }
};