Red bez duplikata

Napisati generičku klasu red_bez_duplikata<T> koja implementira red elemenata tipa T. Red ne sme da sadrži duplikate, tj. svaki element može da se nalazi u redu najviše jednom. Klasa treba da podržava sledeće operacije:

void dodaj(const T& element) - dodaje element na kraj reda ako već nije prisutan.
void ukloni() - uklanja element sa početka reda.
const T& pogledaj() const - vraća referencu na element na početku reda bez uklanjanja.

Sve operacije treba da budu složenosti ne veće od $O(1)$.

Ulaz

Sa standardnog ulaza, sve do kraja ulaza, učitavaju se naredbe u formatu:

i x - dodaje element x na kraj reda
r - uklanja i ispisuje element sa početka reda

Izlaz

Na standardni izlaz ispisati rezultate izvršavanja naredbi r. Ako je red prazan, ispisati poruku izuzetka na standardni izlaz za greške.

Primer

`stdin`

i 1
i 2
i 1
i 3
r
i 4
r
r
r
r

`stdout`

`stderr`

Red je prazan

Rešenje

`main.cpp`

#include <iostream>
#include <queue>
#include <unordered_set>

namespace matf
{
	/* Klasa za red bez duplikata */
	template <typename T>
	class red_bez_duplikata
	{
		public:
			/* Dodaje element u red ako nije vec prisutan */
			void dodaj(T x)
			{
				if (skup.find(x) == skup.end()) {
					red.push(x);
					skup.insert(x);
				}
			}

			/* Uklanja element sa pocetka reda */
			void ukloni()
			{
				if (red.empty()) {
					throw std::out_of_range("Red je prazan");
				}

				T x = red.front();
				red.pop();
				skup.erase(x);
			}

			/* Pogledaj element na pocetku reda */
			const T& pogledaj() const
			{
				if (red.empty()) {
					throw std::out_of_range("Red je prazan");
				}

				return red.front();
			}

		private:
			std::queue<T> red;
			std::unordered_set<T> skup;
	};
};

int main(void)
{
	matf::red_bez_duplikata<int> red;

	char op;

	while (std::cin >> op) {
		if (op == 'i') {
			int x; std::cin >> x;
			red.dodaj(x);
		} else if (op == 'r') {
			try {
				std::cout << red.pogledaj() << std::endl;
				red.ukloni();
			} catch (const std::out_of_range& e) {
				std::cerr << e.what() << std::endl;
			}
		}
	}

	return 0;
}