set

Ordered set that implemented by a “Self balancing BST” like Red-Black Tree.

Extra find operations

  • equal_range returns range of elements matching a specific key
  • lower_bound returns an iterator to the first element not less than the given key
  • upper_bound returns an iterator to the first element greater than the given key
#include <iostream>
#include <set>
#include <assert.h>

using namespace std;

int main(void) {
		set<int> hset;

		hset.insert(5);
		hset.insert(8);
		hset.insert(13);

		{
				// Lower bound equal or greater than
				auto iter = hset.lower_bound(5);
				assert(*iter == 5); // 5's lower bound is 5 itself in the set
		}
		{
				// Upper bound greater than 5
				auto iter = hset.upper_bound(5);
				assert(*iter == 8); // 5's upper bound is the first value greater than itself
		}
}

unordered_set

Set that implemented by Hash Table.