LeetCode. Insert Delete GetRandom （巧用map与vector结合，实现O(1)复杂度）

unordered_map 底层数据结构是hash表，插入insert和删除delete都是 O(1) 时间复杂度
利用vector来实现 random() 方法，map的key保存元素值，value保存元素存在vector的数组下标
对于删除delete的数val，直接使用vector的末尾数字填充到被删除的数的位置，并且还需要修改map，将被删的数移除，并且将末尾数字在map中对应的value值修改为被填充的数组下标

#include <unordered_map>
#include <vector>
#include <time.h>
using namespace std;
class RandomizedSet {
private:
	//元素 + 数组下标
	unordered_map<int, int> map;
	vector<int> vec;
public:
	/** Initialize your data structure here. */
	RandomizedSet() {
		srand(time(0));
	}

	/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
	bool insert(int val) {
		if (map.find(val) != map.end()) {
			return false;
		}
		else {
			vec.push_back(val);
			map[val] = vec.size() - 1;
			return true;
		}
	}

	/** Removes a value from the set. Returns true if the set contained the specified element. */
	//
	// Replaces the last element with the deleted element
	bool remove(int val) {
		if (map.find(val) != map.end()) {
			int vecIndex = map[val];

			map[vec.back()] = vecIndex;
			vec[vecIndex] = vec.back();

			//save it for last before deleting it(val)
			//prevent error with only one element
			map.erase(val);
			vec.pop_back();
			return true;
		}
		else {
			return false;
		}
	}

	/** Get a random element from the set. */
	int getRandom() {
		if (vec.empty())return -1;
		return *(vec.begin() + (rand() % vec.size()));
	}
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * bool param_1 = obj.insert(val);
 * bool param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */