Kontener set<T>

0

Postanowiłem zgłębić tajniki kontenera set, w związku z czym wyprodukowałem taki fragment kodu:

#include <iostream>
#include <set>

class liczba
{
	private:
		unsigned long long int x;
	public:
		liczba() : x(0) {}
		liczba(unsigned long long int y) : x(y) {}
		unsigned long long int get() const {return(x);}
		bool operator<(liczba const & o) const {return(x < o.get());}
		//bool operator<=(liczba const & o) const {return(x <= o.get());}
		//bool operator>(liczba const & o) const {return(x > o.get());}
		//bool operator>=(liczba const & o) const {return(x >= o.get());}
		//bool operator==(liczba const & o) const {return(x == o.get());}
		friend std::istream& operator>> (std::istream &inp, liczba & r)         
			{inp >> r.x; return inp;}
		friend std::ostream & operator<< (std::ostream &out, const liczba &s) 
			{return out << s.get();}
};

template <typename T>
void add(std::set<T> & tmp, unsigned long long int ile)
{
	T m;
	while(ile--)
	{
		std::cin>>m;
		tmp.insert(m);
	}
	std::cout<<"\n";
}

template <typename T>
void write(const std::set<T> tmp)
{
	typename std::set<T>::iterator it;
	for(it=tmp.begin();it!=tmp.end(); it++) 
		std::cout<<*it<<"\n";
}

int main()
{
	const unsigned long long int c = 3; //elementy do dodania
	std::set<liczba> tab;
  		
  	add(tab, c);
  	write(tab);
 	
	return(0);
}

Zdziwiło mnie to, że do jego działania wystarczy jeden operator: "<". Jego działanie rozumiem w ten sposób, że dodaje on obiekty, które są automatycznie sortowane z pominięciem duplikatów. O ile jakieś tam sortowanie to da się przeprowadzić za pomocą tego jednego operatora, to zapobieżenie przed dodaniem duplikatu bez jakiegokolwiek porównania już chyba nie bardzo. Albo ja nie do końca rozumiem jego ideę. Wie ktoś jak to działa, ale tak "od środka"?

0

set<T> działa w oparciu o drzewa binarne (zwykle czerwono-czarne, tak samo jak map<T>). Więc tu się nic nie sortuje, tylko następuje dodawanie do drzewa. Jak przeczytasz na jakiej zasadzie działa takie dodawanie to zauważysz ze spokojnie wykryjesz duplikat klucza na podstawie jednego tylko operatora porównania (bo jak coś nie jest ani mniejsze ani większe, to jest równe).

0

Co do tego jak zbiór wydobywa elementy. Odbywa się to logarytmicznie. Innymi słowy. Jak mamy zbiór 10,20,30,40,50,60,70,80,90. To wydobycie np "30" odbywa się tak:
Znajdowana jest tak jakby środkowa wartość tego zbioru. W tym przypadku będzie to 50 i jest ona porównywana ze szukaną wartością. 30 jest mniejsze od 50. Więc dzielimy zbiór na połówke i szukamy zadanego elementu w tej gdzie się znajdują mniejsze wartości(ta po lewej). Z tej mniejszej połówki znowu wyodrębniamy środkową wartość i porównujemy ze szukaną wartością aby wyodrębnić kolejne dwie połówki itd aż znajdziemy dany element.

1

Kazde porownanie da sie przeprowadzic uzywajac tylko operatora <:
a == b jest rownowazne !(a < b) && !(b < a)
a != b jest rownowazne (a < b) || (b < a)
a <= b jest rownowazne !(b < a)
a >= b jest rownowazne !(a < b)
a > b jest rownowazne b < a

To wszystko jest oczywiscie przy zalozeniu, ze na elementach a i b operator < definiuje porzadek liniowy.

0

Jako ciekawostka, możliwym sposobem definicji innych operatorów logicznych mając dostęp tylko do

a < b

jest np.

a >= b  =  not (a < b)
a == b  =  (a >= b) && (b >= a)
a /= b  =  not (a == b)
a <= b  =  (a < b) || (a == b)
a  > b  =  (a >= b) && (a /= b)
0

Przy okazji: To o czym piszecie wyżej jest częściowo dostępne w bibliotece standardowej w std::rel_ops. Z tym, że wymagany jest operator < oraz ==.

http://en.cppreference.com/w/cpp/utility/rel_ops/operator_cmp

0

No ja się tam nie do końca szczęśliwie wyraziłem...
Wiadomo, że można przeprowadzić każde porównanie za pomocą "<".
Ale czy autorzy biblioteki stosowaliby takie cuda wianki, zamiast sobie poprzeciążać inne operatory?
Wątpię...

2

Tego wymaga standard C++. 23.2.4 punkty 2 oraz 3.

1 użytkowników online, w tym zalogowanych: 0, gości: 1