[Discretize Relabeling] 離散化器

離散化是演算法競賽常用的操作，在各種實際問題上也能看到其應用。最基本的情況，是對於n個可排序的元素，製造一個map使得它們可以和自己的名次一一對應，但通常的應用中這n個元素確定之後就不太會有增減的動作，因此可以存到vector中排序去除重複的部分，搜索的部分就用二分搜尋來取代。

	#include <algorithm>
	#include <stdexcept>
	#include <vector>
	template <typename T, typename Alloc = std::allocator<T>>
	class Discretizer : private std::vector<T, Alloc> {
	void build() {
	std::sort(std::vector<T, Alloc>::begin(), std::vector<T, Alloc>::end());
	std::vector<T, Alloc>::erase(std::unique(std::vector<T, Alloc>::begin(),
	std::vector<T, Alloc>::end()),
	std::vector<T, Alloc>::end());
	}
	public:
	using const_iterator = typename std::vector<T, Alloc>::const_iterator;
	using const_reverse_iterator =
	typename std::vector<T, Alloc>::const_reverse_iterator;
	using const_reference = typename std::vector<T, Alloc>::const_reference;
	using size_type = typename std::vector<T, Alloc>::size_type;
	Discretizer() = default;
	template <class InputIterator>
	Discretizer(InputIterator first, InputIterator last,
	const Alloc &alloc = Alloc())
	: std::vector<T, Alloc>(first, last, alloc) {
	build();
	}
	Discretizer(const typename std::vector<T, Alloc> &x)
	: std::vector<T, Alloc>(x) {
	build();
	}
	Discretizer(const typename std::vector<T, Alloc> &x, const Alloc &alloc)
	: std::vector<T, Alloc>(x, alloc) {
	build();
	}
	Discretizer(typename std::vector<T, Alloc> &&x)
	: std::vector<T, Alloc>(std::move(x)) {
	build();
	}
	Discretizer(typename std::vector<T, Alloc> &&x, const Alloc &alloc)
	: std::vector<T, Alloc>(std::move(x), alloc) {
	build();
	}
	Discretizer(std::initializer_list<T> il, const Alloc &alloc = Alloc())
	: std::vector<T, Alloc>(il, alloc) {
	build();
	}
	Discretizer(const Discretizer &x) : std::vector<T, Alloc>(x) {}
	Discretizer(Discretizer &&x) : std::vector<T, Alloc>(std::move(x)) {}
	Discretizer(Discretizer &&x, const Alloc &alloc)
	: std::vector<T, Alloc>(std::move(x), alloc) {}
	Discretizer &operator=(const Discretizer &x) {
	std::vector<T, Alloc>::operator=(x);
	return *this;
	}
	Discretizer &operator=(Discretizer &&x) {
	std::vector<T, Alloc>::operator=(std::move(x));
	return *this;
	}
	const_iterator begin() const noexcept {
	return std::vector<T, Alloc>::begin();
	}
	const_iterator end() const noexcept { return std::vector<T, Alloc>::end(); }
	const_reverse_iterator rbegin() const noexcept {
	return std::vector<T, Alloc>::rbegin();
	}
	const_reverse_iterator rend() const noexcept {
	return std::vector<T, Alloc>::rend();
	}
	size_type size() const noexcept { return std::vector<T, Alloc>::size(); }
	size_type capacity() const noexcept {
	return std::vector<T, Alloc>::capacity();
	}
	bool empty() const noexcept { return std::vector<T, Alloc>::empty(); }
	void shrink_to_fit() { std::vector<T, Alloc>::shrink_to_fit(); }
	const_reference operator[](size_type n) const {
	return std::vector<T, Alloc>::operator[](n);
	}
	const_reference at(size_type n) const { return std::vector<T, Alloc>::at(n); }
	const_reference front() const { return std::vector<T, Alloc>::front(); }
	const_reference back() const { return std::vector<T, Alloc>::back(); }
	void pop_back() { std::vector<T, Alloc>::pop_back(); }
	void clear() noexcept { std::vector<T, Alloc>::clear(); }
	void swap(Discretizer<T, Alloc> &x) { std::vector<T, Alloc>::swap(x); }
	const_iterator lower_bound(const_reference x) const {
	return std::lower_bound(begin(), end(), x);
	}
	const_iterator upper_bound(const_reference x) const {
	return std::upper_bound(begin(), end(), x);
	}
	size_type getIndex(const_reference x) const {
	auto Iter = lower_bound(x);
	if (Iter == end() || *Iter != x)
	throw std::out_of_range("value not exist.");
	return Iter - begin();
	}
	};

view raw Discretizer.h hosted with ❤ by GitHub

	#include <iostream>
	#include "Discretizer.h"
	int main() {
	std::vector<int> V{3, 1, 9, 2, 2, 7, 3, 100};
	Discretizer<int> D(std::move(V));
	for (auto e : D)
	std::cout << e << ' ';
	std::cout << '\n';
	std::cout << D.getIndex(7) << '\n';
	std::cout << D.getIndex(100) << '\n';
	std::cout << D.upper_bound(9) - D.lower_bound(2) << '\n';
	return 0;
	}

view raw main.cpp hosted with ❤ by GitHub