Nasumični skup

Napisati generičku klasu nasumicni_skup<T> koja implementira strukturu podataka koja podržava sledeće operacije:

void dodaj(const T& vrednost) - dodaje vrednost u skup. Ukoliko vrednost već postoji u skupu, ništa se ne dešava.
void ukloni(const T& vrednost) - uklanja vrednost iz skupa. Ukoliko vrednost ne postoji u skupu, ništa se ne dešava.
T nasumicni_element() const - vraća nasumično izabran element iz skupa. Svi elementi u skupu treba da imaju jednaku verovatnonoću da budu izabrani. Ukoliko je skup prazan, treba baciti izuzetak std::out_of_range sa odgovarajućom porukom.

Sve operacije traba da budu implementirane tako da rade u očekivanoj vremenskoj složenosti $O(1)$.

Ulaz

Sa standardnog ulaza se učitavaju naredbe u formatu:

a x - dodaje vrednost x (celo broj) u skup.
r x - uklanja vrednost x iz skupa.
n - ispisuje nasumično izabrani element iz skupa.

Za generisanje nasumičnih brojeva koristiti std::rand() iz <cstdlib>, sa početnim semenom std::srand(42).

Izlaz

Na standardni izlaz ispisati rezultate izvršavanja naredbi n. Ukoliko je skup prazan, treba baciti izuzetak std::out_of_range sa odgovarajućom porukom.

Primer

`stdin`

a 1
a 2
a 3
a 4
a 5
n
n
r 3
r 4
r 2
n
n
n

`stdout`

Rešenje

`main.cpp`

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdlib>
#include <stdexcept>

namespace matf
{
	/* Klasa za nasumicni skup */
	template <typename T>
	class nasumicni_skup
	{
		public:
			/* Dodaje element u skup */
			void dodaj(const T& vrednost)
			{
				if (indeks.find(vrednost) != indeks.end()) {
					return; // Vrednost vec postoji
				}

				elementi.push_back(vrednost);
				indeks[vrednost] = elementi.size() - 1;
			}

			/* Uklanja element iz skupa */
			void ukloni(const T& vrednost)
			{
				auto it = indeks.find(vrednost);
				if (it == indeks.end()) {
					return; // Vrednost ne postoji
				}

				size_t pozicija = it->second;
				T poslednji_element = elementi.back();

				elementi[pozicija] = poslednji_element;
				indeks[poslednji_element] = pozicija;

				elementi.pop_back();
				indeks.erase(it);
			}

			/* Vraca nasumicni element iz skupa */
			T nasumicni_element() const
			{
				if (elementi.empty()) {
					throw std::out_of_range("Skup je prazan");
				}

				size_t nasumicni_indeks = std::rand() % elementi.size();
				return elementi[nasumicni_indeks];
			}

		private:
			std::vector<T> elementi;
			std::unordered_map<T, size_t> indeks;
	};
};

int main(void)
{
	std::srand(42); // Postavljanje semena za nasumicne brojeve

	matf::nasumicni_skup<int> ns;

	char op;

	while (std::cin >> op) {
		if (op == 'a') {
			int x; std::cin >> x;
			ns.dodaj(x);
		} else if (op == 'r') {
			int x; std::cin >> x;
			ns.ukloni(x);
		} else if (op == 'n') {
			try {
				std::cout << ns.nasumicni_element() << std::endl;
			} catch (const std::out_of_range& e) {
				std::cout << e.what() << std::endl;
			}
		}
	}
	

	return 0;
}