map_and_set.md

Set and Map

Put object in to set/map

Need to define the < operator:

1. Define the '<' operator in the class:

struct Myobject {
	int val;
	int pos;
	// asending order
	bool operator < (const Myobject& obj) const {
		return val < obj.val;
	}
}

2. Define a functor as argument of the set

struct Comparator {
	bool operator() (const Myobject& obj1, const Myobject& obj2) const {
		return obj1.val < obj2.val;
	}
}

set<Myobject,Comparator> mySet;

---

Find element in BST

lower_bound(x): iterator to first element >= x upper_bound(x): iterator to first element > x if the element do not exist, return end()

Find first element >= x

auto it = map.lower_bound(x);
if(it==map.end()) cout<<"Not Exist";

Find first element > x

// assume x is the integer
auto it = map.upper_bound(x);
if(it==map.end()) cout<<"Not Exist";

Find last element <= x

auto it = map.upper_bound(x);
if(it==map.begin()) cout<<"Not Exist";
--it; 

Find last element < x

auto it = map.lower_bound(x);
if(it==map.begin()) cout<<"Not Exist";
--it;