Lower bound and upper bound of set/map

Posted by chunyang on March 8, 2020
TAGS: #cpp

STL’s map/set/multimap/multiset is an ordered container which compares to unordered_map and unordered_set. So there are special methods which implemented due to the order. multiset and multimap allow repeated elements. Its erase method is a little different.

Introduction

set and map are implemented using Red-Black Tree. They are sorted containers. If we traverse it from begin to end, we will get a sorted collections according the key type.

So if we want to maintain a sorted range, we can use them. But if we want a faster insert and access of the data, the unordered versions(unordered_set and unordered_map) are suggested.

Search and find

  • lower_bound: Find the first number which is >= target
  • upper_bound: Find the first number which is > target
  • equal_range: Range between(lower_bound, upper_bound)
  • find: Find the specific target, (C++ 20 intoduces contains)

Delete elements

We can delete an element using erase. But when it comes to multiset or multimap, it is a little different.

  • erase(iterator pos)
  • erase(iterator start, iterator end)
  • erase(key_type key)

When we only specify the key, it will delete all the keys instead of deleting only one element.

In 220. Contains Duplicate III, we need to maintain a range which is sorted. When the size of the set is larger than required, we need to delete the head element.

// 220. Contains Duplicate III
// https://leetcode.com/problems/contains-duplicate-iii/
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int size = nums.size();
        if (k == 0 || size < 2) return false;
        multiset<int> s;
        s.insert(nums[0]);
        for (int i = 1; i < size; ++i) {
            auto l = s.lower_bound(nums[i]);
            auto r = prev(l);


            if (l != s.end() && (abs(*l - (long long)nums[i])) <= t) return true;
            if (r != s.end() && (abs(*prev(l) - (long long)nums[i])) <= t) return true;

            if (s.size() == k) {
                // We cannot directly delete: s.erase(nums[i-k]);
                auto ite = s.find(nums[i-k]);
                s.erase(ite);
            }

            s.insert(nums[i]);
        }
        return false;
    }
};

Related