Kontener set<T>

Odpowiedz Nowy wątek
2012-12-31 14:15

Rejestracja: 7 lat temu

Ostatnio: 4 lata temu

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"?

edytowany 1x, ostatnio: darkfucker, 2012-12-31 14:16

Pozostało 580 znaków

2012-12-31 14:30
Moderator

Rejestracja: 16 lat temu

Ostatnio: 7 minut temu

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).


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
Dzięki za odp. - darkfucker 2012-12-31 14:41

Pozostało 580 znaków

2012-12-31 16:01

Rejestracja: 7 lat temu

Ostatnio: 5 lat temu

Lokalizacja: Opole

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.


Nie odpowiadam na PW z prośbą o pomoc programistyczną.

Pozostało 580 znaków

2012-12-31 16:38

Rejestracja: 8 lat temu

Ostatnio: 3 lata temu

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.

edytowany 1x, ostatnio: 0x200x20, 2012-12-31 16:51
Uprzedziłeś mnie. ;) - Oak 2012-12-31 16:41

Pozostało 580 znaków

Oak
2012-12-31 16:41
Oak

Rejestracja: 8 lat temu

Ostatnio: 4 lata temu

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)

Pozostało 580 znaków

2012-12-31 17:01

Rejestracja: 16 lat temu

Ostatnio: 1 rok temu

Lokalizacja: Katowice

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


"(...) otherwise, the behavior is undefined".
edytowany 1x, ostatnio: Endrju, 2012-12-31 17:46

Pozostało 580 znaków

2012-12-31 17:33

Rejestracja: 7 lat temu

Ostatnio: 4 lata temu

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ę...

Pozostało 580 znaków

2012-12-31 17:43

Rejestracja: 16 lat temu

Ostatnio: 1 rok temu

Lokalizacja: Katowice

2

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


"(...) otherwise, the behavior is undefined".

Pozostało 580 znaków

Odpowiedz

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