# 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);
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;
}
};