🚀 go-pugleaf

Dnia Mon, 24 Dec 2007 14:38:28 +0100, Sebastian Kaliszewski skrobie:
> >>>>>Ha ha ha. Wielka mi różnica, że tupli nie mogę modyfikować! I to w języku, w
> >>>>>którym i tak nawet głupiego consta nie da się zrobić.
> >>>
> >>>>consta który nie oznacza niezmienności obiektu? ROTFL!
> >>>
> >>>Niezmienności KTÓREGO obiektu?
> > 
> >>referowanego.
> > 
> > 
> > No dobrze, więc dlaczego ten const nie oznacza niezmienności referowanego
> > obiektu?

> Bo nie dotyczy obiektu tylko jednego do niego dojścia. Tuple są immutable, a 
> w C++ const z immutable nie ma nic wspólnego. Stąd twoje porównanie jest od 
> czapy.

No dobrze, i co z tego?

Jest to tylko przypadłość języka, nic więcej.

Co można uznać twoim zdaniem za zaletę faktu, że tupli nie można modyfikować?
Poza, powiedzmy, tą niby "lepszą wydajnością" (co przy ograniczonym
zastosowaniu z uwagi na niemodyfikowalność i tak niewiele znaczy)?

> >>>>>>>Tego typu podejście jest pożądane tylko w
> >>>>>>>językach, które mają większe rygory bezpieczeństwa, ale one sprawdzają to i
> >>>>>>>tak w czasie kompilacji (bo sprawdzanie tego w czasie wykonywania to pic na
> >>>>>>>wodę).
> >>>>>
> >>>>>>Bzdura.
> >>>>>
> >>>>>Bo nie masz nic więcej do powiedzenia?
> >>>
> >>>>Bo piszesz tak oczywiste bzdury, że szkoda na to czasu.
> >>>
> >>>To napisanie słowa "bzdura" jest tym bardziej marnowaniem czasu.
> > 
> >>Istnienie
> > 
> > Mów dalej.

> Patrz wyżej.

W które miejsce?

Dla porządku przytoczę wszystkie twoje wypowiedzi z "wyżej", a ty wybierz
sobie, która ci bardziej pasuje:

1.
> >>>>consta który nie oznacza niezmienności obiektu? ROTFL!

2.
> >>referowanego.

3.
> >>>>>>Bzdura.

4.
> >>>>Bo piszesz tak oczywiste bzdury, że szkoda na to czasu.

5.
> >>Istnienie

Wskaż teraz proszę tę merytoryczną wypowiedź, do której się odwołujesz, lub
podaj cytat, który być może przeoczyłem.

> >>>>>>>>>>Tylko czemu interfejs jest tak parszywie niejednolity? begin/end to trochę mało.
> >>>>>>>>>
> >>>>>>>>>Jak to niejednolity! Jest cholernie jednolity.
> >>>>>>>
> >>>>>>>>Ależ skąd. Jednolite w miarę są pary vector i deque, map i multimap oraz set 
> >>>>>>>>i multiset.
> >>>>>>>
> >>>>>>>A co jest niejednolitego w vector i list?
> >>>>>
> >>>>>>Wszystko.
> >>>>>
> >>>>>"Wszystko" to znaczy "nic" albo "nie wiem".
> >>>
> >>>>Napisane było poniżej.
> >>>
> >>>
> >>>Napisałeś "wszystko". Jeśli vector i list mają wspólne begin(), end(), size(),
> > 
> >>O tym napisałem. I na tym się ich "jednolistość" kończy.
> > 
> > Nie. Napisałeś, że "niejednolite" ma "wszystko". Patrz wyżej.

> Sam patrz wyżej. Pisałem wyraźnie o begin/end.

No dobrze. Nie kłóćmy się o to co kto kiedy powiedział.

Napisałeś "begin/end to trochę mało".

Otóż te zbiorniki posiadają wspólne również size(), empty(), clear(),
insert() i erase(). Te dwie ostatnie co prawda nie mają wspólnych założeń
pomiędzy vector i map (bo w vector pochodzą z koncepcji Sequence, a w map z
Unique Sorted Associative Container), ale mają ten sam interfejs i dają w
ogólności ten sam efekt końcowy.

Ale rozgadałem się. Rozprawmy się z trochę mniejszym twoim "niedomówieniem",
mianowicie że (zacytuję, żeby nie było znów problemu typu "patrz wyżej", który
mógłbym chyba na tym etapie ochrzcić "wykrętem Kaliszewskiego"):

> >>>>>>>A co jest niejednolitego w vector i list?
> >>>>>
> >>>>>>Wszystko.

Załóżmy nawet na upartego, że miałeś na myśli "wszystko poza begin i end",
choć wbrew temu, co twierdzisz, wcale tego nie napisałeś wprost.

Zgodnie z tym, co pisze dobrze znana dokumentacja, vector jest to:

 Model of
 Random Access Container, Back Insertion Sequence.

A list jest to:

 Model of
 Reversible Container, Front Insertion Sequence, Back Insertion Sequence.

Oczywiście, jakbyś nie wiedział, to gwoli ścisłości:

 A Random Access Container is a Reversible Container whose iterator type is a
 Random Access Iterator.

Co oznacza, że jeśli procedura używa zbiornika spodziewając się po nim, że
jest niczym więcej, niż Reversible Container i Back Insertion Sequence, to
może pracować równie dobrze na vector i list.

Zapytam więc wprost: co to znaczy, że "interfejs jest parszywie niejednolity"
i dlaczego to źle? I jak mogłoby być lepiej?

> >>>Powiedz mi najpierw może, dlaczego poniższy program się nie kompiluje:
> >>
> >>[błedny programik ciach]
> > 
> > 
> >>Bo sort wymaga iteratora o dostępie swobodnym.
> > 
> > No właśnie. Więc?

> Więc taka jest jego specyfikacja w standardzie. Która to specyfikacja jest 
> taka sobie.

A dlaczego jest taka i dlaczego twoim zdaniem mogłaby być inna i dlaczego
wtedy byłaby lepsza?

Sebek, wybacz że stawiam takie idiotyczne pytania, ale wydaje mi się, że
kompetentny człowiek dyskutując o określonych sprawach powinien o takich
rzeczach pisać przede wszystkim i to bez dodatkowego ponaglania.

> >>>>A stable sort moża i czasem trzeba użyć i na wektorze.
> >>>
> >>>Ale co to ma do rzeczy - tłumaczę ci, jak chłop krowie na miedzy: algorytmu
> >>>introsort
> > 
> >>Jakiego q.wa algorytmu introsort? Nie ma w C++ algorytmu intorosort. Jest 
> >>sorotowanie w czasie rzędu n*log2(n) na iteratorach o dostępie swobodnym. 
> > 
> > Zgadza się. A czy lista jest zbiornikiem swobodnego dostępu?

> Ale jest drugie sortowanie, które działa na iteratorach sekwencyjnych. To 
> jest pomieszanie dwu różnych rzeczy w jednym miejscu. Klasyczny błąd 
> projektowy -- "nonseparate concerns".

Przepraszam - które sortowanie twoim zdaniem działa na iteratorach
sekwencyjnych? Podaj mi tutaj, czym mam wypełnić poniższą funkcję:

template <class Container>
void bidirectional_applicable_sort( typename Container::iterator from,
                  typename Container::iterator to )
{
	// co tutaj?
}

> >>>NIE MOŻNA stosować na zbiorniku, który nie jest zbiornikiem
> >>>swobodnego dostępu, bo traci to sens - algorytm ten będzie w tym przypadku
> >>>działał wolniej, niż mergesort.
> > 
> >>>>>a list::sort jest to to samo co
> >>>>>std::stable_sort, tylko zaimplementowany w sposób bardziej specjalizowany
> >>>>>(stable_sort, tak jak sort, wykonywałby kopie wartości, a list::sort po prostu
> >>>>>przestawia węzły na żywca)?
> >>>
> >>>>Poza tym że wyszedłeś z całkowicie błednych założeń to co z tego?
> >>>
> >>>A co z tego niby ma być?
> > 
> >>No właśnie nic.
> > 
> > Chciałbym, żebyś uzasadnił po prostu, dlaczego uważasz, że std::sort powinien
> > mieć wersję pracującą na zbiornikach jednokierunkowych i jak wyobrażasz sobie
> > implementację takiego algorytmu.

> Nie ma zbiorników jednokierunkowych w C++.

Niech nawet będzie dwukierunkowych. Czepiasz się słówek.

> Implementację wyobrażam sobie 
> przes specjalizację za pomocą traitsów dla iteratorów (tak to powinno być 
> zrobione).

Nadal pytam: jak? Jest w stdc++ udostępnione sortowanie dla listy, już tak w
ramach drobnej podpowiedzi. Jak sobie wyobrażasz dorobienie do tego interfejsu
zgodnego z bieżącym interfejsem sort()?

> >>>>>Lista ma zaimplementowane wewnętrznie te rzeczy, które się tak zaimplementować
> >>>>>opłacało ze względu na jej szczególności i specjalizację.
> >>>
> >>>>To było wyspecjalizowac szablon std::sort dla listy a nie robić niejednolity 
> >>>>interfejs.
> >>>
> >>>Sebek, przestań...
> > 
> >>Nie zamierzam. Design listy w STL jest cienki.
> > 
> > Jak twoim zdaniem powinien on wyglądać lepiej?

> Wpychanie ni z tego ni zowego sort i splice do listy jest do kitu. Powinna 
> być udostępiona metoda iteratora swap -- powodująca zamianę wskazywanych 
> elementów. I std::stort czy std::stable_sort ma być specjalizowane iteroatorem.

Pomijając już, że pomyliłeś splice() z merge() - co taki swap() miałby zrobić?
I czy to wystarczy do zaimplementowania tego algorytmu równie efektywnie?

> >>>Obiecaj mi, że następnym razem pomyślisz 7 razy zanim palniesz, ok?
> >>>
> >>>Co miałby przepraszam robić std::sort dla listy, skoro istnieje jawnie
> >>>postawione wymaganie, że std::sort może pracować tylko na zbiorniku swobodnego
> >>>dostępu, a std::list takowym nie jest?
> > 
> >>To niech takiego wymagania nie będzie. Ono jest błędem projektowym. Bo można 
> >>mieć łatwo stabilne sortowanie bez mergowania, które jest od merge sorta 
> >>wydajniejsze.
> > 
> > To wciąż można zrobić, jaki problem?

> Mixed concrens.
> Że standardowy sort nie działa bez randdom access a stable_sort ni z tego ni 
> z owego działa.

Też nie działa (ja tak kiedyś myślałem, że działa, ale sprawdziłem dokładnie i
jednak byłem w błędzie). Nie działa z przyczyn zasadniczych: zewnętrzna
funkcja jest w stanie tylko nadpisywać elementy - nie jest w stanie
przestawiać węzłów, bo w tym celu potrzebne jest dobranie się do samego
zbiornika.

> >>I można mieć sortowanie bez obowiązku zachowania stabilności 
> >>dla iteratorów sekwencyjnych. Łączenie dwu ortogonalnych cech jest błedem 
> >>projektowym.
> > 
> > To wszystko również można zrobić!
> > 
> > Nie ma nigdzie żadnego takiego wymagania, że zbiornik dwukierunkowy musi mieć
> > sortowanie stabilne, nie wiem, skąd sobie takie dyrdymały wymyśliłeś.

> Nic nie rozumiesz. Po pierwsze nie zbiornik. Wpychanie sortowania do 
> zbiornika to jest interface bloat przy równoczesnym sortowaniu po 
> interatorach.

Nie, dlaczego - to jest po prostu inny interfejs.

> Sortuje się sekwencje wyznaczane przez iteratory -- i niech 
> się tego C++ już trzyma.

No to się trzyma.

Znalazłem takie wytłuymaczenie tego faktu na stronie SGI:

The sort algorithm works only for random access iterators. In principle,
however, it would be possible to write a sort algorithm that also accepted
bidirectional iterators. Even if there were such a version of sort, it would
still be useful for list to have a sort member function. That is, sort is
provided as a member function not only for the sake of efficiency, but also
because of the property that it preserves the values that list iterators point
to.

> Po drugie jedyne dostępne sortowanie dla iteratorów nie-swobodnych to 
> sortowanie stabilne.

To nic nie znaczy.

Chodzi nam cały czas o jedną rzecz: jak zaimplementować taką specjalizację
std::sort, żeby działała dla dowolnego zbiornika dwukierunkowego (pomińmy już
techniczne sprawy związane z szablonami, wykpiwając się koncepcjami):

template <BidirectionalContainer C>
void sort( typename C::iterator from, typename C::iterator to )
{
	// co tutaj?
}

Załóżmy nawet, że do iteratorów dodamy dowolne metody, jakie będą nam do
wykonania tej operacji potrzebne. Jak to zrobić?

> > Algorytm
> > sortowanie szybkiego i niestabilnego można by z powodzeniem dodać do listy.

> Nie do żadnej listy. Zlisty w ogóle należy wywalic sortowanie.

Zgadza się - sortowanie należy wyspecjalizować dla BidirectionalContainer.

> > Pytanie tylko: jak to zrobić, zakładając że masz do dyspozycji ciąg elementów,
> > po których możesz poruszać się jedynie dwukierunkowo. Słucham.

> Po pierwsze to możesz sobie np. zebrać do kupy cały ciąg np 30 iteratorów i 
> sortować na tym zebranym fragmencie być może zyskując na wydajności.

> Często przyzwoicie zrobione wydajne sortowanie używa wymyślnych metod tylko 
> do poziomu fragmentów długosci kilkudziesięciu elementów. Poniżej tego 
> opłaca się użyć prymitywnego algorytmu typu insertion-sort.

Sebek - wiem o tym, bo właśnie przejrzałem sobie implementację SGI do
list::sort.

Problem jest tylko w jednym: jak przestawiać iteratory w zbiorniku, nie mając
dostępu do samego zbiornika? Jak utrzymać w tym sensowną enkapsulację, bo nie
zapominaj, że iteratory z założenia mają tylko dawać wgląd do zbiornika, a nie
służyć do modyfikowania zbiornika.

> >>>Rozumiem, gdybyś zaproponował takie rozwiązanie, że istnieje std::stable_sort,
> >>>std::quick_sort oraz std::sort, który wybierze, powiedzmy, std::quick_sort dla
> >>>zbiornika swobodnego dostępu, a na liście zrobi sort() (i tak się tego nie da
> >>>zrobić w obecnych warunkach, ale to jest jeszcze do przedyskutowania).
> > 
> >>Bez sensu. Zdejmij klapki z krzyżykami z oczu. Ten design jest po prostu 
> >>zły. Pomieszano rzeczy ortogonalne takie jak stabilność sortowania i 
> >>wymaganie swobodnego dostępu ukrywając wszystko pod nazwą stabilności 
> >>sortowania. To jest do dupy.
> > 
> > Nieprawda. Jeżeli już cokolwiek pomieszano, to pomieszano wymaganie swobodnego
> > dostępu z możliwością pracy na części zbiornika.

> To jedno drumiemu nie przeszkadza.

> > Co masz do zaproponowania przy tak postawionym problemie?

> Sensownie zaprojektowany iterator (z metodą swap) problem rozwiązuje.

Pokazać. Nie ten iterator oczywiście, tylko jak zaimplementujesz samą funkcję
sort() przy założeniu, że coś takiego masz.

Kwestię tego, czy nie naruszy to innych założeń (np. do czego może służyć
iterator) odłóżmy na bok na razie.

> >>>>>To nie jest kwestia spójności zbiorników.
> >>>
> >>>>Jest.
> >>>
> >>>Ale ty wolisz argumenty typu "wszystko chuj".
> > 
> >>Jak coś jest "chuj" to należy to nazwać po imieni i się nie chrzanić.
> > 
> > Oraz uzasadnić. Na to czekam już od dłuższego czasu.

> Zostało to uzasadnione. Brak separacji problemów, nieortogonalne interfejsy, 
> brak użycia możliwości języka przez bibliotekę (która w innych miejsach 
> dokładnie tych samych możliwości używa)

Trudnosłowie.

> >>>>>Czy to jest takie trudne do zrozumienia?
> >>>
> >>>>Widzę, że dla Ciebie tak. Po tych bzdurach co tu powypisywałeś. Pomyli
> >>>
> >>>Może zacznij pisać w końcu coś do tematu.
> > 
> >>Ja piszę. Ty błądzisz po jakiś nieistotnych zakamarkach.
> > 
> > Jedyne co piszesz, to że design STL jest do dupy i że można to lepiej
> > wymyślić. Wybacz, na razie nie przekonałeś mnie jeszcze o tym.

> Patrz wyżej.

Nadal nie przekonałeś mnie o tym - proszę o pokazanie implementacji std::sort
używającej iteratora ze swap().

> >>>>>O tym, czy taki podział na koncepcje jest słuszny, możemy dopiero porozmawiać,
> >>>>>jak będziesz wiedział, jak należy postawić problem.
> >>>
> >>>>Ja wiem. Ty, jak widzę, wogóle go zgubiłeś.
> >>>
> >>>Nie widzę, żebyś wiedział - nie napisałeś jeszcze nic poza "bzdura, bzdura,
> >>>bzdura".
> > 
> >>Napisałem jak to powienno być zrobione.
> > 
> > Napisałeś, że powinno być zrobione - na "jak" na razie czekam.

> Patrz wyżej

No, napisałeś na razie co by ci się przydało do napisania - na "jak" nadal
czekam.

> >>>>>>lista z C++ jest wyjątkowo do dupy. Ponawtykali jakiś rzeczy których nie 
> >>>>>>powinno być (sort, merge, itp...)
> >>>>>
> >>>>>I bardzo słusznie zrobili - na tej samej zasadzie, na jakiej vector posiada
> >>>>>metodę reserve(), a list nie.
> >>>
> >>>>Zrobili do *dupy*. Od tego są specjalzacje szblonów a nie rozpieprzanie 
> >>>>interfejsu.
> >>>
> >>>Specjalizacje szablonów można zastosować pod warunkiem, że jesteś w stanie
> >>>ustalić wspólny interfejs, realizowalny dla różnych zbiorników.
> > 
> >>Wszędzie się daje, tylko w C++ nie...
> > 
> > W którym przepraszam języku masz możliwość sortowania fragmentu zbiornika o
> > dostępie tylko dwukierunkowym?

> Nie ma żadnej fundamentalnej różnicy między zbiornikiem a jego fragmentem.

Tylko pod warunkiem, że wszystkie iteratory masz tak zaimplementowane, żeby
miały dostęp do zbiornika, z której zostały pobrane. Na razie wszystkie znane
mi biblioteki zbiorników tak nie mają.

> > Z ciekawości, zajrzałem co ma Java. Java posiada algorytm
> > java.util.Collections.sort() (w dwóch wersjach, jedna z komparatorem).
> > Pierwszym argumentem jest LISTA (nie zakres elementów). W żadnej klasie
> > dziedziczącej po *.Collections nie jest ona przesłonięta.
> > 
> > Co więcej, *.Collections.sort() ma gwarancję, że jest stabilny. Ciekawe,
> > dlaczego?

> Bo nie dawali wersji niestabilnej?

Zgadza się. A dlaczego nie dali wersji niestabilnej?

> >>Można też zostawić interfejs taki jaki jest. I dostosować bebechy. To że 
> >>sort dla listy będzie tak naprawdę przepinał węzły a nie kopiował elementy 
> >>to jest wewnętrzny szczegół implementacji sort wyspecjalizowanego dla listy.
> > 
> > To w tym celu iterator musiałby mieć referencję do zbiornika.

> Nie musiał. swap() dla iteratora wystarczy.

I tu jest jeden drobny problem.

Otóż, żeby zrobić taką metodę swap(), o jakiej tutaj mówisz, musiałaby się ona
stać wymaganiem dla BidirectionalIterator, co oznacza, że stałaby się również
wymaganiem dla RandomAccessIterator. Przestawianie węzłów przez kluczową dla
sortowania listy metodę list::merge polega na tym, że element w zależności od
relacji z pivotem wstawia się przedeń lub zań. Wstawianie polega na tym, że
następuje przepięcie węzła w tym stylu:

a b c d e f
      ^
a b c e d f
        ^
A dodatkowo jeszcze wykonuje się operacje, które wstawiają całe zakresy w
miejsce wskazane iteratorem.

Tu nie o to chodzi, że odpowiednich metod swapujących nie dałoby się zrobić
dla iteratora listy. Dałoby się jak najbardziej. Problem polega na tym, że
takie przestawianie elementów jest efektywnym sposobem manipulowania
elementami tylko w przypadku elementów wiązanych łańcuchowo, co więcej,
przestawianie w ten sposób elementów nie narusza integralności iteratorów.

Jak sobie wyobrażasz zaimplementowanie takich operacji dla zbiorników, które
nie korzystają z takiego rozkładu elementów?

> >>>>Dlaczego map::iterator iteruje po parach a vector::iterator nie
> >>>
> >>>Np. dlatego, że elementami mapy są pary, a elementami wektora nie (chyba że
> >>>zrobisz vector<map<A,B>>).
> > 
> >>To jest błąd w projekcie std::map. Mapa tak jak wektor ma klucze i wartości.
> > 
> > Od kiedy to wektor ma klucze? Po czym to wnosisz, po tym, że oba zbiorniki
> > mają przeciążony operator [] ?

> Index jest kluczem.

Ooo ?

> >>>>-- przecież 
> >>>>oba są zbiornikami danych do których można się odwoływac po kluczu -- w 
> >>>>przypadku vectora kluczem jest indeks, w mapie obiekt dowolnej 
> >>>>porównowywalnego i przypisywalnego typu.
> >>>
> >>>No tak, oczywiście - popuśćmy wodze fantazji i piszmy bzdury bez
> >>>najdrobniejszego przemyślenia.
> >>>
> >>>Czy zastanowiłeś się odrobinę chociażby nad tym, co praktycznie wałkujemy od
> >>>początku tej dyskusji: usunięcie elementu "ze środka" vectora przetasuje owe
> >>>klucze dla pewnej liczby elementów, a w mapie nie?
> > 
> >>vektor spełnia inne niezmiennikni niż mapa. Co nie zmienia częstej 
> >>podstawialności jednego za drugie.
> > 
> > 
> > Sebek, skoro już mowa o kompromitacji: czy nie zauważyłeś takiego drobnego
> > szczegółu, że skoro mówimy o parach klucz-wartość, to w takim razie usunięcie
> > ze zbiornika dowolnego elementu powinno spójność powiązań kluczy z wartościami
> > zachować?

> Nie musi. To jest właśnie specyfika zbiornika. Inaczej byłaby tylk mapa.

Sam sens istnienia "klucza" polega na tym, że jest mu przypisana określona
wartość. W przypadku wektora ten "klucz" nadaje się jedynie do odwoływania się
do określonego miejsca w chwilowo nie zmienianym zbiorniku. Jedyne
zastosowanie tego jakie znam to równoległe przetwarzanie dwóch zbiorników
(jeden indeks służy do iterowania po dwóch zbiornikach równocześnie w jednej
pętli). Przy takim zastosowaniu mówienie o kluczu jest tym bardziej bez sensu.

> > W przypadku mapy definiując nowe powiązanie, określasz jaki klucz powinien
> > mieć przypisany jaką wartość. I to się nie powinno zmienić przy jakiejkolwiek
> > operacji na zbiorniku (innej, niż usunięcie powiązania z mapy lub przypisanie
> > kluczowi innej wartości).

> Tak. A w przypadku vectora już nie.

A co to takiego jest dla ciebie "klucz"? Bo na razie to wynika dla mnie, że
jest to wartość, której możesz użyć w operatorze [].

> >>>>Mapa powinna mieć dwa iteratory -- 
> >>>>jeden po wartościach
> >>>
> >>>Po co?
> > 
> >>Bo tak jest wygodniej i czytelniej? I *spójniej*?
> > 
> > Ale kto by tego do czego używał?

> Prawie nigdy nie zdarzyło msi się, bym potrzebowała na raz klucz i wartość. 
> Zwykle potrzebuję same wartości, rzadziej same klucze.

To bardzo ciekawe - bo ja u siebie zauważyłem ostatnio taką tendencję, że o
ile kiedyś w Tcl-u do iterowania po tablicy robiłem:

foreach key [array names arr] {
	rób coś tam z $arr($key)
}

O tyle bardzo szybko zarzuciłem ten sposób na rzecz:

foreach {key val} [array get arr] {
	rób coś tam z $val
}

I co możesz na to poradzić? Klucz masz, no bo jest - po cholere mi iterowanie
po samych wartościach po to, żeby jeszcze dodatkowo komplikować sobie
interfejs? Nie interesuje cię wartość klucza, to go po prostu nie używaj.

> >>>>i *inny* po kluczach (tylko stały).
> >>>
> >>>Przecież wystarczy w zupełności, że i->first jest stałe, a i->second
> >>>modyfikowalne.
> > 
> >>Ale i->first nie jest stałe :) BANG!
> > 
> > Od kiedy?
> > 
> > /usr/include/c++/4.1.1/bits/stl_map.h:
> > ...
> >  class map
> >     {
> >     public:
> >       typedef _Key                                          key_type;
> >       typedef _Tp                                           mapped_type;
> >       typedef std::pair<const _Key, _Tp>                    value_type;
> >       typedef _Compare                                      key_compare;
> >       typedef _Alloc                                        allocator_type;

> Szczegół jednej implementacji.

Sebek, czy ty jesteś masochistą, czy idiotą?

23.3.1 Class template map
...
2. map satisfies all of the requirements of a container and of a reversible
container (23.1) and of an associative container (23.1.2). A map also provides
most operations described in (23.1.2) for unique keys. This means that a map
supports the a_uniq operations in (23.1.2) but not the a_eq operations. For a
map<Key,T> the key_type is Key and the value_type is pair<const Key,T>.
                                                     ^^^^^^^^^^^^^^^^^


> >>>>Zbiór zaś powinien 
> >>>>mieć tylko stały iterator -- po kluczach. Nie stały interator w zbiorze to 
> >>>>jest w ogóle kompletna porażka.
> >>>
> >>>To chyba jest jakiś błąd specyfikacji - w gcc na przykład masz tak:
> >>>
> >>>      typedef typename _Rep_type::const_iterator iterator;
> >>>      typedef typename _Rep_type::const_iterator const_iterator;
> > 
> >>Szczegół implementacyjny. Szkoda że nieprawdziwy już dla mapy.
> > 
> > No bo iteratora nie można uczynić stałym, jeśli ma wskazywać na modyfikowalny
> > obiekt. Jakie to ma zresztą znaczenie?

> Takie że się kupy nie trzyma.

Co ci się znów przepraszam kupy nie trzyma?

Iterator zmienialny ma dawać dostęp do dwóch rzeczy: modyfikacji struktury
zbiornika oraz modyfikacji wskazanego elementu. Niestety w niektórych
przypadkach zbiornik nie jest modyfikowalny pod względem struktury (jak np.
set, bo trzyma ustalony porządek elementów), ewentualnie też wartości
elementów (jak również set, bo klucze nie są modyfikowalne).

Iterator zmienialny i niezmienialny to są wymagania przyjęte dla koncepcji,
które winny być przez zbiorniki odpowiednio spełniane. Zmienialny iterator
zatem nie ma sensu w przypadku set, owszem, ale to tylko dlatego, że nie ma
dla niego zestawu operacji, które można by przeprowadzić na takim iteratorze,
a istnienie tego zestawu dozwolonych operacji nie jest warunkiem koniecznym
dla spełnienia koncepcji. Możesz np. równie dobrze zrobić sobie
vector<const int> i też nie będziesz mógł zrobić *begin() = 0, niezależnie od
faktu, że vector<const int>::iterator i vector<const int>::const_iterator są
oddzielnymi typami.

> >>>Więc ja tu nie widzę problemu: on ma i tak zawsze stały iterator. Różnica jest
> >>>tylko taka, że POSIADA typ iterator. I bardzo dobrze, że posiada, bo niektóre
> >>>algorytmy się do takiego typu próbują odwoływać.
> >>>
> >>>Jest zatem typ iterator, ale operator* użyty na nim zwróci ci stałą
> >>>referencję. Czyli jest ok.
> > 
> >>Czyli jest dziwnie. Były zresztą na ten temat flejmy na c.s.c++
> > 
> > To nie czytałem.
> > 
> > 
> >>>>>A tu się zgadza - już nawet Seweryn podał implementację, chociaż mam poważne
> >>>>>wątpliwości, czy rzeczywiście jest sensowna.
> >>>>>
> >>>>>Tylko że akurat to jest dla mnie głupie. Nie po to pytam, żeby tylko zadać tak
> >>>>>sobie pytanie, tylko dlatego, że chciałbym następnie wykonać na znalezionych
> >>>>>danych jakąś operację - i to dla mnie robi equal_range.
> >>>
> >>>>Nie zawsze chcesz od razu robić jakąś operację. Całkiem często robi się np. 
> >>>>walidację danych, itp.
> >>>
> >>>To wtedy używasz binary_search.
> > 
> >>ROTFL!!!
> > 
> >>binary_search na mapie!
> > 
> > A co, bo nie rozumiem.

> Przeczytaj sobie jakich iteratorów wymaga binary_search...

Spełniającego koncepcję ForwardIterator, a koncepcję tą spełniają iteratory
zbiornika spełniającego koncepcję ForwardContainer, będącego jedną z podstaw
AssociativeContainer, a dalej mam nadzieję że doczytasz sam i nie będziesz
robił z siebie idioty.

Powiedz wprost, że dla ciebie po prostu stanowi ogromny problem użycie
binary_search z własnym komparatorem.

> >>>>>>>>>>>Poza tym nie wiem, dlaczego właściwie uważasz, że vector jest bardziej
> >>>>>>>>>>>uniwersalny, niż list.  To prawda, że vector nadaje się do tzw. "większości
> >>>>>>>>>>>zastosowań", ale ma jedną bardzo paskudną wadę: unieważnienie iteratorów
> >>>>>>>>>>>następuje tam po każdej modyfikacji liczebności zbiornika.
> >>>>>>>>>
> >>>>>>>>>>Po każdej po której zmienia się capacity. capacity zaś zmienia się tylko 
> >>>>>>>>>>czasami.
> >>>>>>>>>
> >>>>>>>>>Weź ty się z łaski swojej nie ośmieszaj, dobrze?
> >>>>>>>
> >>>>>>>>sam się ośmieszasz. Te gwarancje są po to, by można było określone 
> >>>>>>>>konstrukcje wykonać.
> >>>>>>>
> >>>>>>>Konkretnie które gwarancje?
> >>>>>
> >>>>>>Ważności iteratorów po określonych operacjach.
> >>>>>
> >>>>>Ty cały czas nie rozumiesz.
> >>>>>
> >>>>>Ile znasz algorytmów, w których ze zbiornika swobodnego dostępu usuwa się
> >>>>>elementy od końca? Ja znam tylko jeden przypadek - tylko wtedy, gdy ten
> >>>>>zbiornik jest stosem.
> >>>
> >>>>To cienki jesteś :-P. Od końca to nie znaczy kolejne od końca. Po prostu 
> >>>>jadąc od końca.
> >>>
> >>>Lol, czemu ty się aż tak kompromitujesz.
> > 
> >>Ja? skąd! Ty za to na całej linii :)
> > 
> >>>Czy fakt, że usuwasz elementy od końca, czy od początku zmienia ci w efekcie
> >>>końcowym cokolwiek nt. unieważniania iteratorów?
> > 
> >>Sektor ty jesteś expertem od C++??!?
> > 
> >>Weź że q.wa zajrzeyj w końcu do standardu tego twojego ukachanego, 
> >>popier.lonego języka!
> > 
> > Owszem, jestem.

> Zaczynam mieć wątpliwości.

> > 
> > O co chciałeś w tej wypowiedzi powyżej zapytać?

> To popatrz do tego standardu i przeczytaj sobie co i kiedy unieważania 
> iteratory i który iterarory.

Wiem, kiedy i które iteratory. O co chciałeś zapytać?

Chwilami mam wrażenie, że jesteś kobietą.

Załóżmy przykładowo najbardziej optymistyczny scenariusz ważności iteratorów.
Przy czym zdefiniujmy jeszcze odpowiednie pojęcia, żeby było wiadomo, o czym
rozmawiamy:
 - węzeł - jest wirtualnie określonym miejscem w zbiorniku, do którego
   przyczepiona jest wartość. Wartość do węzła jest przyczepiona raz na
   zawsze; zakładamy że jeśli np. wykonano operację, która przestawiła element
   w inne miejsce, przestawiła węzeł (nawet jeśli wewnętrznie po prostu
   przepisano wartość z jednego miejsca w drugie)

 - iterator ważny - taki, który wskazuje na określony element
 - iterator osobliwy - taki, którego nie wolno używać
 - iterator niewłaściwy - taki, który wskazuje na inny węzeł, niż powinien

Najbardziej optymistyczny sceariusz zatem wygląda tak, że robimy najpierw
reserve(), żeby ewentualny przydział pamięci na dodatkowe elementy nie
spowodował pobrania pamięci od systemu, a tym samym nie spowodował
unieważnienia iteratorów (przy czym za unieważnienie iteratorów uważamy
uzyskanie przez iterator zarówno wartości osobliwej, jak i niewłaściwej).

Jeśli więc dodajesz elementy, to musisz w celu utrzymania ważności iteratorów
utrzymać odpowiedni zapas pamięci. Jeśli ten zapas jest za mały, to go
przydzielasz. Operacja ta oczywiście powoduje unieważnienie iteratorów.

Z kolei jeśli usuwasz elementy, to powodujesz, że elementy te, które wskoczyły
na miejsce usuniętych i innych przesuniętych, otrzymują iteratory niewłaściwe.

Przypominam, że mówimy o sytuacji, w której koniecznością jest możliwość
szybkiego usuwania określonych elementów. Dla listy zapamiętuję wartości
iteratorów mając pewność, że ich wartość się nie zmieni w jakichkolwiek
operacjach, dopóki wskazywane przez nie elementy znajdują się w zbiorniku. Tak
samo, dodanie jakichkolwiek dodatkowych elementów nie zmieni ważności
iteratorów wskazujących na istniejące elementy zbiornika.

W jaki sposób chciałbyś uzyskać podobny efekt w przypadku wektora? Ile jesteś
w stanie uzyskać zapasu, aby to zapewnić, a także - co ciekawsze - co
właściwie powinieneś zrobić w przypadku, gdy stwierdzisz, że dla utrzymania
ważności iteratorów w przypadku dodawania elementów jesteś zmuszony wykonać
reserve()?

> >>>>Poza tym jak masz ze zbiornika 30 elementowego usunąć 
> >>>>elementy 5, 13, 17 i 28 to jadąc od końca możesz to zrobić.
> >>>
> >>>To TYLKO jadąc od końca możesz to zrobić. Bo w przeciwnym razie, po usunięciu
> >>>elementu #5, element 13 nagle stanie się 12 i podobnie reszta.
> >>>
> >>>Bardzo fajnie, że znasz algorytm selektywnego usuwania elementów z wektora,
> >>>ale wybacz, to nie ma nic zupełnie do tematu, który wałkujemy.
> > 
> >>Ma. Tematu nie udało ci się uściślić przez 5 postów...
> > 
> > Nie ma. I przestań z łaski swojej stosować wciąż taktykę "jesteś za głupi,
> > żeby zrozumieć, jaki ja jestem mądry".

> Sektor, ty widzisz swoje końcowe rozwiązanie i przez jego pryzmat patrzysz 
> na całość. Ale ani nie ma pernowści że ono jest optymalne ani też nikt poza 
> tobą nie zna całości.

Przecież przedstawiłem ci założenia. Podstawowe założenie jest takie, że nie
masz żadnych wewnętrznych danych żadnego obiektu, które pozwolą ci stwierdzić
jego unikalność, a tym samym wyszukać tego elementu po określonym kryterium.
Element po prostu masz dany w momencie jego tworzenia i tyle. W tym i tylko w
tym momencie możesz zapamiętać coś, co w przyszłości pozwoli ci na jego
szybkie zidentyfikowanie i usunięcie.

> > Przypomnę ci - skoro zapomniałeś najwyraźniej - że chodzi nam cały czas o
> > zbiornik, w którym usuwanie elementów pozwala na zachowanie ważności
> > iteratorów do pozostałych elementów, żeby można było je szybko usuwać.

> Patrzysz przez pryzmat swojego rozwiązania. Mówisz o konkternej drodze do 
> celu, a interesuje nas tylko cel fo którego drobi mogą być różne.

Przedstaw alternatywną - na razie poddajesz w wątpliwość moje rozwiązanie nie
przedstawiając nawet żadnych zajawek na inne pomysły.

> > Na razie bez większych sukcesów usiłujesz udowodnić, że nadaje się do tego
> > wektor.

> Ponieważ nadal nie podałeś wystarczająco kompletnych uwarunkowań to wektor 
> mioże się nadawać a może nie.
> Pamiętaj -- nikt poza tobą nie ma przed oczami twojego rozwiązania.

Przedstawiłem ci jak dotąd kompletne założenia tego rozwiązania - jak
koniecznie chcesz, możesz dalej udawać idiotę (choćby dlatego, że nawet nie
sprecyzowałeś, czego ewentualnie brakuje ci w moich wyjaśnieniach).

> >>>>I co ważne 
> >>>>zapewne okaże się, że tak jest lepiej niż użyć map (bo samo dodanie elementu 
> >>>>do map jest o 2 rzędy wolniejsze niż dodanie do vector).
> >>>
> >>>Zgadza się bezsprzecznie.
> >>>
> >>>Tyle że dodanie tego elementu na końcu wektora unieważnia ci od razu wszystkie
> >>>iteratory (co prawda, nie unieważnia ci indeksów, ale to niewiele zmienia, bo
> >>>unieważnia je przy usuwaniu). No chyba że na poważnie myślisz o tym, żeby
> >>>sprawdzać ilość zarezerwowanego miejsca przed każdym dodaniem elementu - na
> >>>upartego, owszem, masz gwarancję, że iteratory nie będą unieważnione, jeśli
> >>>dodanie elementu przydzieli miejsce z zapasu.
> >>>
> >>>Natomiast dodanie tego elementu do listy jest nieco wolniejsze od wektora (ale
> >>>bardzo nieznacznie - nie aż tyle, co w przypadku std::map),
> > 
> >>Bardzo znacznie. Zwykle też o 1-2 rzędy wielkości :) To jest lepiej niż o 
> >>2-3 rzędy wielkości dla mapy, ale też słabo.
> > 
> > Nie sądzę, żeby można było dywagować nt. różnic złożoności algorytmów w
> > przypadku, gdy w grę wchodzi alokacja pamięci.

> Owszem wchodzi. W przypadku listy za każdym dodaniem elementu, w przypadku 
> vectora tylko czasem (tak żeby amortyzowało się na coraz więcej dodań).

Zależy od alokatora pamięci. Co więcej, w krytycznych przypadkach można mieć
alokator specjalizowany, czyli taki mechanizm, który trzyma w zapasie pamięć
po zwolnionych obiektach i z nich przydziela pamięć na nowo tworzone.

Ale to akurat nie ma znaczenia. Podstawowym założeniem, które utrudnia
używanie czegokolwiek innego, niż listę, jest fakt, że nie ma żadnej
możliwości zindentyfikowania elementu po jego zawartości. Dwa elementy w
liście mogą mieć nawet identyczną zawartość i mimo to musisz wiedzieć który
jest który, jeśli byś chciał określony z nich usunąć.

> >>>>Nigdzie ci nie kazałem usuwać wszyskich elementów ze zbiornika. Mogłeś mieć 
> >>>>np. listę elementów do usunięcia i chcieć usunąć tylko te.
> >>>
> >>>Ok - załóży nawet, że spróbuję nieco potraktować poważnie to, co piszesz.
> >>>
> >>>Załóżmy. Mamy wektor z elementami opisującymi połączenia.
> >>>
> >>>Mamy cykliczne sprawdzanie połączeń. W jednym cyklu okazało się, że odpadły
> >>>trzy połączenia z 10: połączenia o numerach 2, 4 i 9.
> >>>
> >>>Każdy z obiektów połączenia trzymał swój indeks zapisany w polu. W związku z
> >>>tym, wiemy że należy wywalić ze zbioru połączeń połączenia o indeksach 2, 4 i
> >>>9. Możemy sobie nawet zrobić tymczasowo vector<int>, który będzie je
> >>>przechowywał.
> >>>
> >>>No więc wykonujemy naszą operację. Sortujemy nasz wektor z identyfikatorami
> >>>połączeń (indeksami do wektora z połączeniami) malejąco, a następnie po kolei
> >>>usuwamy nasze połączenia.
> >>>
> >>>Usuwamy najpierw #9. Jest to ostatni element, więc nikt na tym nie ucierpi.
> >>>
> >>>Usuwamy następnie #4 i #2.
> >>>
> >>>W tym momencie okazuje się, że musimy przenumerować wszystkie obiekty od #2
> >>>(ostatniego elementu z listy indeksów po posortowaniu) do końca zbiornika, bo
> >>>element #3 stał się teraz #2, #5 - #3, #6 - #4 i tak dalej.
> >>>
> >>>Nie jest to trudna operacja, ale wystarczy fakt, że w ogóle trzeba ją wykonać,
> >>>i że ma ona liniową złożoność.
> >>>
> >>>Uważasz, że to efektywny sposób gospodarowania zasobami?
> > 
> >>Może się okazać, że tak :)
> > 
> > Może jest szerokie i głembokie.

> Być może.

A teraz pomyśl jeszcze o złożoności programistycznej (już nie obliczeniowej).
Zaangażowanie dodatkowych procedur. Wrażliwości na błędy. I tak dalej.

> >>Brak odwołań do stery może przynieść zysk o 1-2 
> >>rzędy wielkości. I wtedy cudowanie może się opłacić.
> > 
> > Niestety nie w moim przypadku. Rozumiem, że dla powyższego rozwiązania można
> > by znaleźć określoną niszę, ale pomińmy na razie nisze.
> > 
> > Skoro już wspomniałem, że lista przechowuje obiekty z informacją o
> > utrzymywanych połączeniach TCP, jakie widzisz tu przeciwwskazania dla
> > std::list, zakładając że tworzenie nowego elementu następuje w momencie
> > wyjścia z accept()?
> > 
> > Bo ja przeciwwskazań dla wektora i mapy co nieco widzę.
> > 
> > 
> >>>>>>>A ty mi tu proponujesz jakieś śmieszne
> >>>>>>>usuwanie od końca?
> >>>>>>>
> >>>>>>>
> >>>>>>>
> >>>>>>>>Tyle że jest to mało wydajne i nie ma nic wspólnego z szybkim usuwaniem.
> >>>>>>>
> >>>>>>>To nie ma nic wspólnego z jakimkolwiek usuwaniem, ani z jakąkolwiek mającą
> >>>>>>>sens operacją, jeśli rozpatrujemy przestrzeń rozwiązań przemysłowych, a nie
> >>>>>>>akademickich rozważań.
> >>>>>
> >>>>>>W "przestrzeni rozwiązań przemysłowych" dla dużej liczby małych struktur to 
> >>>>>>sie może opłacać (struktury po kilkadziesiąt pozycji których jest wiele -- 
> >>>>>>pomagamy cache locality).
> >>>>>
> >>>>>Tak, ale nie stosowane w taki sposób. Jeśli już, to można kombinować z
> >>>>>std::deque, albo czymś podobnym (w sensie, lepiej kontrolowanym).
> >>>
> >>>>std::vector jest zupełnie dobrze kontrolowany i przy większej liczbie 
> >>>>operacji zachowuje ważność iteratorów.
> >>>
> >>>Czy jesteś w stanie podać mi przynajmniej JEDNĄ taką operację, która
> >>>modyfikuje wektor, nie unieważnia iteratorów, i która w tym celu nie wymaga
> >>>żadnych dodatkowych wstępnych założeń poza poprawnością danych wejściowych?
> > 
> >>A co to ma do rzeczy? Zobacz kiedy nie zachowuje iteratorów deque i porównaj 
> >>sobie co jest "bardzuiej kontrolowane".
> > 
> > Bardzo ładnie wykręcasz się od odpowiedzi - oczywiście, deque nie ma nawet
> > takich gwarancji, jak wektor, ale jakie to ma dla mnie znaczenie, skoro nawet
> > gwarancje, jakie daje wektor, dla powyższych wymagań można o kant dupy rozbić?
> > 
> > 
> >>>>>Jeśli każdy istniejący obiekt siedzi w liście, to każdy ma zapisany swój
> >>>>>iterator. W efekcie jestem w stanie każdy z nich usuwać z listy w czasie
> >>>>>stałym.
> >>>
> >>>>A skąd mam wiedzieć, że te obiekty są jeszcze trzymane przez co innego 
> >>>>(czyli jest do nich innny dostęp niż z kontenera je przechowującego)
> >>>
> >>>Nie ma do nich dostępu znikąd innąd, niż z kontenera je przechowującego. Skąd
> >>>ci to w ogóle przyszło do głowy?
> > 
> >>To po cholere ci trzymanie indeksów czy iteratorów w samych elementach? 
> > 
> > Z bardzo prostej przyczyny. Bo jest to jedyna możliwość zidentyfikowania tego
> > elementu w zbiorniku.

> 1. Nie wierzę, że jedyna.

Jedyna.

Ok, możesz na upartego stwierdzić, że nigdy dwa obiekty nie mają identycznej
zawartości. Ale to nic nie znaczy. Przykładowo mamy pola a, b, c, d. Mamy trzy
obieky. W pierwszy a i b są identyczne, drugi z trzecim ma wspólne b i c, a
pierwszy z trzecim wspólne d. Jak wyobrażasz sobie porównanie, jeśli są to
obiekty dość dużej wielkości? Będziesz robić memcmp? Zresztą, o czym my tu
rozmawiamy - wszystko rozbija się o to, że obiekt akurat mamy dany, widzimy
całą jego zawartość. I mamy zbiornik, który ten element trzyma. Mamy pełny
wgląd w obiekt. Mamy jedynie usunąć go ze zbiornika. Co masz zamiar w tym
przypadku zrobić? Przelecieć się po wszyskich elementach i przez memcmp
porównać ów obiekt z każdym napotkanym w zbiorniku?

> 2. Masz zakręconą strukturę własności: zbiornik ma elementy które z kolei 
> mają zbiornik

Nie mają zbiornika. Zadaniem zbiornika jest przetrzymywać elementy, grupować
je i podawać na tacy dla operacji, które wykonują zbiorcze operacje na
wszystkich elementach zbiornika (takie np. jak odpytywanie deskryptorów
połączeń i buforowanie).

> i się same z niego usuwają.

Nie do końca. One SĄ USUWANE. Tyle że do usunięcia elementu potrzebny jest
tylko ten jeden element (konkretnie referencja do niego). Na podstawie tego
pobieram iterator tego elementu w zbiorniku i usuwam za jednym zamachem.

> Jesteś pewien, że tak było 
> najprościej? (byc może faktycznie tak było najprościej, ale musisz mnie 
> przekonać).

A jaką widzisz alternatywę? Przecież nie twierdzę, że moje rozwiązanie jest
najlepsze możliwe, a tylko najlepsze, jakie udało mi się wykombinować.

> > Dotarło?

> Na razię widzę, że jesteś mocno przywiązany do swojego rozwiązania.

Nie. Ja tylko po prostu nie widzę nawet żadnych perspektyw na lepsze
rozwiązanie.

> >>Sektor -- albo projekt jest bezsensownie skomplikowany (a więc do kitu) albo 
> >>właśnie oszukujesz.
> > 
> > No dobrze, powyższe wyjaśnienie powinno cię naprowadzić.
> > 
> >>Jak kontener (lista czy vector) jest jedynym dojściem do przechowywanych 
> >>obiektów to iterator bądź indeks masz dany przez sam fakt sięgnięcia do tego 
> >>obiektu.
> > 
> > Zakładając oczywiście, że mówimy o zbiorniku intruzyjnym. 

> Ależ skąd. W chwili gdy odowłujesz się do a[x] musisz znać x. Ty jak 
> rozumiem tracisz tę informację po to, by ją ponownie odgrzebywać poziom 
> niżej. Tak?

Nie. Nie masz żadnego a[x]. Masz dane pewne p, które jest tożsame z a[x].
Teoretycznie znasz a. Ale nie znasz x.

> > Zbiornik std::list
> > niestety takowym nie jest, std::vector również. No, na upartego można przyjąć,
> > że jest tak w przypadku surowej tablicy, ale z niej usuwać elementów się nie
> > da.

> Nie ma znaczenia.

Tu już się pogubiłem.

> >>>>>Jeśli nie przedstawiłem żadnych szczególnych warunków, przy których
> >>>>>można poszukać odrębnego lub prostszego rozwiązania, to znaczy, że takowych
> >>>>>nie ma.
> >>>
> >>>>Nie przedstawiłeś warunków wystarczających.
> >>>
> >>>
> >>>Dobrze - skoro chcesz już uprawiać taką zabawę intelektualną, to proszę
> >>>bardzo: napisz mi tutaj dokładnie, jakie przedstawiłem warunki, gdzie te
> >>>warunki są niedokładne lub co jest nie sprecyzowane.
> > 
> >>Patrz wyżej :)
> > 
> > Nie widzę.
> > 
> > Proszę o drobne podsumowanie wątpliwości, bo na razie to mówisz, że "a, te
> > warunki są w ogóle niespójne".

> Nie wiadomo co trzyma te twoje obiekty poza zbiornikiem (a jakiś inny 
> kontakt ze światem zdaje się mają).

Wątek, który jest tworzony dla każdego takiego obiektu. Poza tym innego
dojścia niż poprzez zbiornik, nie ma.

> Nie wiadomo czy usuwasz po jednym czy 
> grupowo (jak się trochę zbierze).

Nie, to jest akurat robione najprostszą metodą. Odcięcie połącznia - wywalenie
klienta i asygnowanego mu obiektu.

> Kto inicujeje akcje prowadzącą do usunięcia. I peweni jeszcze torchę...

Błąd odczytu (lub stwierdzenie końca strumienia). Przez wątek obsługujący,
oczywiście.

> >>>>>>>Nadal czekam na propozycję rozwiązania tego w tym wszystkowyrażalnym Pythonie.
> >>>>>
> >>>>>>To już powiedziałem -- słownik
> >>>>>
> >>>>>Jest to - jak powiedziałem - rozwiązanie spełniające, owszem, wymagania (i -
> >>>>>co ciekawsze - w językach skryptowych wszyscy je stosują), niestety słabe w
> >>>>>stosunku do std::list z uwagi na:
> >>>>>- konieczność generowania kluczy (wartości iteratorów std::list są same z
> >>>>>  siebie unikalne na całą aplikację)
> >>>
> >>>>hash(object) działa całkiem dobrze.
> >>>
> >>>hash(object) tworzy unikalny klucz do obiektu? Od kiedy?
> > 
> >>Od zawsze? Dopóki nie zrobisz własnej implementacji którw to psuje.
> > 
> > 
> > A, ten hash.
> > 
> > No dobrze. Powiedzmy, że ten problem odpada, ale i ma on niewielkie znaczenie.
> > Gorzej z tym drugim.

> Drugi miał być logarytmiczny, a nie jest.


> >>>>>- logarytmiczny czas znajdowania węzła w zbiorniku (przy stałym czasie w
> >>>>>  przypadku std::list)
> >>>
> >>>>Ależ ten czas nie jest logarytmiczny -- jest stały (zamortyzowany) :)
> >>>
> >>>Amortyzacja polega na tym, że tylko jedna na kilka operacji ma złożoność
> >>>gorszą niż stałą. Tymczasem czas wyszukiwania elementu po danym kluczu będzie
> >>>miał określoną złożoność forever, za każdym razem, gdy jest wyszukiwany.
> > 
> >>Amortyzujesz po wyszukiwaniach wielu obiektów a nie wielokrotnym 
> >>wyszukiwaniu tego samego (bo to ma nikły sens).
> > 
> > 
> > No dobrze, nawet zakładając zamortyzowany stały, jego amortyzacja nie jest tym
> > samym, co amortyzacja w przypadku dodawania elementów do wektora (bo nie
> > możesz jej przewidywać, ani jej kontrolować). Wciąż jest to złożoność gorsza,
> > niż stała.

> Nieznacznie. Będę się martwił jak to będzie przeszkadzać. Nie będę się 
> martwił na zapas.

Ale pozostaje problem identyfikacji elementów.

> >>>>Btw w Pythonie każdy obiekt domyślnie 
> >>>>może być kluczem -- trzeba by mu tego jawnie zabronić.
> >>>
> >>>No, możliwe - ale co to ma do tematu? 
> > 
> >>To, że nie potrzebujesz mapy tylko set.
> > 
> > No dobrze, niech będzie set. Co to zmienia?
> > 
> >>>BTW ciekaw jestem jak w takim razie te
> >>>obiekty mają zdefiniowane porządkowanie.
> > 
> >>Porządkowanie nie jest potrzebne. Potrzebny jest dobry hash.
> > 
> > I trochę pamięci.

> To jest potrzebne tak czy siak. I tak jest lepiej niż parę innych rozwiązań.

O ile się orientuję, "dobry hash" nie jest od tego, żeby wygenerował ci
unikalny klucz do elementu, tylko do tego, żeby go powiesić na drabince.

Chyba, że python przyjął nazewnictwo hash z perla. Jeśli tak, to dla mnie nie
różni się to niczym od wartości iteratora z listy.

> >>>>>>>>>>Co do przykładu -- na sieci pełno.
> >>>>>>>>>
> >>>>>>>>>To znajdź i wklej - dopóki tego nie zrobisz, dla mnie bredzisz od rzeczy.
> >>>>>>>
> >>>>>>>>Nie jestem proxy do google. Oczywistości szukaj sobie sam.
> >>>>>>>
> >>>>>>>Twoje oczywistości to dla mnie brednie - i obaj wiemy, że tylko ja mam z tego
> >>>>>>>ubaw.
> >>>>>
> >>>>>>Ja tam mam niezły. Zwłaszcza gdy wymyślasz bzdury -- zrób sobie google 
> >>>>>>python container i nie ośmieszaj się.
> >>>>>
> >>>>>Zrobiłem. Tylko jestem za leniwy, żeby ci wkleić te pierwsze 10 linków i
> >>>>>udowodnić, że nic nie ma na temat wspomnianego zbiornika.
> >>>
> >>>
> >>>>Zrobiłeś? ROTFL! A 2, 5 i 6 link sprawdziłeś?
> >>>
> >>>
> >>>We wszystkich sprawach, w których uważasz, że masz rację, i chcesz to
> >>>udowodnić, potrafisz rzucić odpowiednim linkiem.
> >>>
> >>>W tej jednej tego nie robisz. Taktyka "jesteś za głupi, żeby zrozumieć, jaki
> >>>jestem mądry" to naprawdę tani blef.
> > 
> >>Podałem ci numery linków na stornie którą jakoby sprawdziłeś.
> > 
> > Wybacz, nie wierzę. Google potrafi nawet za dwoma sąsiadującymi wywołaniami
> > wyszukiwania zwrócić zupełnie inny zestaw linków.
> > 
> > Proszę o link - wklejenie linka nie jest trudne, natomiast uparte jego
> > niewklejanie oznacza niewiedzę.

> http://docs.python.org/ref/sequence-types.html
> http://www.eso.org/~almamgr/AlmaAcs/OnlineDocs/ACS_docs/py/Acspy.Container.html

Ok, bardzo ciekawe. Ale przypomnij mi, o czym rozmawialiśmy, bo się zatarło.

A, zapomniałbym - wyżej nie ma, a jak jest, to nie potrafię tego wyskubać z
gąszcza naszych dialogów.

> >>>>>Aha, o tym, że niektórym zdarzało się nazywać słownik również tablicą
> >>>>>dynamiczną, również nie słyszałeś?
> >>>
> >>>>Zapewne stosowali się do przyjętej terminologii jak autorzy STL (czyli marnie).
> >>>
> >>>Niewykluczone - to niewiele zmienia. A już na pewno nie zmienia niczego w
> >>>kwestii tego, czy istnieje coś takiego jak "ustalione konwencje nazewnictwa".
> > 
> >>Tak, istnienia takich konwencji "nowatorskie" podejście autorów STL nie zmienia.
> > 
> > Nie jest wcale takie nowatorskie, jak ci się wydaje.

> Zdążyli już zmulić całką dużą grupę ludzi...

Pojęcie "mapowania" istniało jeszcze grubo przed STL. A Smalltalkowcy ten typ
danej nazwali "słownikiem", bo w ogóle to miał być język dla dzieci (sic! Sam
się nieźle uśmiałem, jak się o tym dowiedziałem).

> >>>>>>>>Dałoby się, gdyby całość zaprojektowano a nie zrodzono z chaosu. Jak są 
> >>>>>>>>idiotyzmy w stylu vector<bool> to być może nie bardzo da się inaczej, by to 
> >>>>>>>>jeszcze było używalne jakkolwiek.
> >>>>>>>
> >>>>>>>A co złego jest w vector<bool>?
> >>>>>
> >>>>>>To, że nie jest kontenerem booli tylko pewnego śmiesznego typu 
> >>>>>>vector<bool>::reference?
> >>>>>
> >>>>>I co w tym złego?
> >>>
> >>>>Że to nie jest referencja.
> >>>
> >>>W jakim sensie nie jest to referencja?
> > 
> >>WE najbardziej podstawowm. To nie jest bool&
> > 
> > A po co musi być to bool& ? Referencją nie jest się poprzez posiadanie & w
> > nazwie, tylko poprzez spełnienie odpowiedniej koncepcji. Przynajmniej w
> > przypadku generycznego programowania.

> W przypadku C++ i referencji to nie bardzo -- o ile wskaźniki emulować da 
> się, to referencji nie.

Dlaczego? Czy referencja jest czymś więcej, niż typem danych, który ma
odpowiedni interfejs stworzony wedle określonych wymagań? Czego nie da się
twoim zdaniem "udawać" typowi, który próbuje udawać referencję (pytam, bo może
wiesz o czymś, co ja przeoczyłem).

> >>>Natomiast uważam, że można by to weryfikować skrośnie i nawet ewentualnie
> >>>umożliwiać uzyskiwanie listy propagowanych wyjątków dla każdej poszczególnej
> >>>funkcji.
> > 
> >>Tylko pod warunkiem pełnej dostępności źródeł lub wyjścia poza głupi linker 
> >>C. Oba są praktycznie niemożliwe.
> > 
> > 
> > Lub poprzez możliwość umieszczania tej informacji w plikach pośrednich i
> > wynikowych.

> Czyli wyjściem poza głupi linker C.

Tak, dokładnie.

Wiesz, ogólnie ja doceniam pomysł Stroustrupa, żeby do C++ był używany
standardowy, systemowy linker. Ale to było dobre na początkowym etapie, po to,
żeby koszty produkcji kompilatora nie były zbyt wysokie, bo to ograniczyłoby
rozprzestrzenianie się języka. Dzisiaj można zresztą z całą odpowiedzialnością
stwierdzić, że przy kosztach, jakie trzeba ponieść na sam parser i
interpreter, napisanie linkera specjalizowanego dla C++ to jak pączek na deser
po obiedzie w drogiej restauracji. A już na pewno nie zniechęci nikogo do
używania C++ - więcej, może nawet pomóc.

> >>>>>Anyway, nie wiem, czy nie wystarczyłoby coś w rodzaju platformy w podobnym
> >>>>>stylu, co robi C#. W sensie, że niby masz ograniczenia platformy, ale i tak
> >>>>>program wykonuje się na platformie natywnej.
> >>>
> >>>>???
> >>>>Program C# jest kompilowany do CIL i wykonuje się na VM z .Net.
> >>>
> >>>Nie ma czegoś takiego, jak VM z .NET, jeśli mówimy o powszechnym rozumieniu,
> >>>czym jest maszyna wirtualna.
> > 
> >>No właśnie w powszechnym rozumieniu to to jest VM. VM nie oznacza interpretera.
> > 
> > 
> > VM oznacza oddzielne środowisko wykonawcze, obojętnie jak zrealizowane.
> > 
> > Program w CIL-u nie jest wykonywany w oddzielnym środowisku wykonawczym,
> > przynajmniej tak to jest w powszechnym rozumieniu.

> Jak nie jak tak? Masz runtime .net który jest właśnie tym oddzielnym 
> środowiskiem wykonawczym.

Runtime, runtime! Runtime masz też w C++, a nawet też w C - i co, masz
oddzielne środowisko wykonawcze?

> >>>>Ta VM jest 
> >>>>realizowana całkiem wydajnie jako JIT ale wirtualizacja cały czas jest.
> >>>
> >>>
> >>>Wirtualizacja jest czysto teoretyczna - kod w CIL-u, który dochodzi już do
> >>>etapu wykonywania, jest kodem wyłącznie natywnym. Goście od .NET jasno piszą,
> >>>że język CIL nigdy nie był pisany z uwzględnieniem możliwości implementacji
> >>>jako VM. Od zawsze miał być tylko i wyłącznie kompilowany JIT-owo.
> > 
> > 
> >>To jest głeboko zaszyty szczegół implementacyjny. Współczesne JVMy też są 
> >>JITami -- ale to w najmniejszym stopniu nie zmienia faktu że są VMami.
> > 
> > 
> > Tak, ale pomijasz dość istotny szczegół: w C# możesz pisać kod sprawdzany i
> > niesprawdzany, możesz używać wskaźników i możesz przypinać obiekty w miejscu,
> > w którym siedzą w pamięci, żeby ich odśmiecacz nie przesunął.

> Ale to jest nadal część środowiska wykonawczego.

Nie. To już nie jest część środowiska wykonawczego.

Kod w Javie wykonuje się w zamkniętej skrzynce. To, co ewentualnie nie należy
do kodu pisanego w Javie, a się tam wykonuje (metody natywne), jest wyłącznie
"rozszerzeniem maszyny wirtualnej", a więc - znów - staje się częścią tego
oddzielnego środowiska wykonawczego.

Wszelkie zezwolenia na kod niesprawdzany, na wymknięcie się spod całkowitej
kontroli tego środowiska, łamie owe bariery hermetyczności środowiska. Nie ma
nawet żadnej możliwości, żeby ten kod był pod kontrolą tego środowiska - co
nie zmienia oczywiście faktu, że aplikację zawierającą taki kod można
uruchomić lub nie, jeśli są odpowiednie "security reasons", ale jeśli zostanie
już wykonana, to się wykonuje i nikt jej tu w niczym nie przeszkodzi.

> > Jeśli mamy program napisany z użyciem takiego ficzera, to znaczy że nam się
> > ta część wymyka spod kontroli VM. Efektywnie, program NIE JEST wykonywany
> > przez żadną VM, bo nie jest to już hermetycznie zamknięte środowisko
> > wykonawcze.

> To że coś nie jest odśmiecane nie oznacza że nagle wyszło poza VM. Znaczy 
> tylko tyle, że nie jest odśmiecane (a więc np. nie jest relokowane za plecami).

Mówię o wskaźnikach i bezpośrednich wywołaniach systemowych. Przypinanie to
tylko drobna usługa pozwalająca na bezpieczne posługiwanie się wskaźnikami.

> > Jest to - znów - wyłącznie kwestia tego, że istnieje bramka między maszyną
> > wirtualną, a platformą natywną.
> > 
> > Nadal nie jesteś w stanie napisać w Javie kodu natywnego.

> W C# tak samo...

Nie umiesz?

> >>>>Na wielu OS możesz mieć te same adresy logiczne po obu stornach -- wtedy 
> >>>>całkiem normalnie to się robi.
> >>>
> >>>Jeśli już stwierdzasz, że "na wielu OS", to znaczy że nie jest to rozwiązanie
> >>>przenośne.
> > 
> >>Działą na każdym nowoczesnym Posixie, nawet na archaicznych Linuksach 
> >>windach a także na bardziej wydumanych systemach typu OpenVMS. Dla mnie to 
> >>jest całkiem przenośne.
> > 
> >>Platformy na których to nie działa można zapewne spokojnie olać. Nekrofilię 
> >>zostawmy komu innemu.
> > 
> > No dobrze, nawet to załóżmy. Co to zmienia?

> Że masz wygodne obiekty "naturalne" ale tylko w obszarze okna między 
> proceseami. Że nie płacisz za wątki na kązdym kroku -- np. zwykłe operator 
> new() działa szybciej (bo nie jest synchronizowane), std::tr1::shared_ptr 
> takoż -- jest tak ze 2 razy szybszy. Jest lepsze rozdzielenie zadań. Do tego 
> dochodzą różne narzędzia dostępne tylko dla procesów a nie dla wątków, 
> narzędzia pozwalające lepiej zarządzić schedulingiem (z nietrywialnym 
> zyskienm wydajności). W sumie? Masz kod równocześnie szybszy i mniej 
> obawiasz się typowych dla wątków heisenbugów.

No, fajnie mi się to podoba, tylko czy ktoś to stosuje lub ma pomysł na
stosowanie?

> >>>>>Nie bez powodu stworzono normalny mechanizm wątków - gdyby komunikacja
> >>>>>międzyprocesowa wystarczała, nikt by tego nie tworzył.
> >>>
> >>>>Kiedyś wydawało się, że tak będzie super. Bo przełączanie ciężkich 
> >>>>kontekstów było wooolne, mechanizmy dzielonej pamięci bardzo ograniczone. 
> >>>
> >>>E tam ograniczone. Takie samo było jak jest teraz.
> > 
> >>No właśnie teraz jest całkiem nieźle.
> > 
> > Nie widzę akurat większych postępów w tej dziedzinie.

> Patrz wyżej.

Ojej, jeśli chodzi o to, to jak najbardziej, ale tu problem nie leży tak do
końca w tym, że przełączanie kontekstów jest wolne. Zresztą to już i tak nie
jest problem - każdy system ma w razie czego LWP. Chodzi głównie o to, która
forma równoległości jest wygodniejsza do zaprogramowania i ma sensowniejsze
metody wykorzystania wzajemnej komunikacji. Chodzi też o oddzielenie
równoległości w sensie systemu od równoległości w sensie aplikacji.

> >>>>Tak miało być dużo szybciej.
> >>>
> >>>>Dziś takie rzeczy jak MPI pokazują że szybciej nie jest. Lepsze wsparcie dla 
> >>>>pamięci dzielonej, np. poprzez memory mapped files
> >>>
> >>>I na czym polega owo "lepsze wsparcie" poza faktem, że jesteś w stanie tą
> >>>pamięć zidentyfikować poprzez ścieżkę do pliku? Problemy z tworzeniem obiektów
> >>>w takiej pamięci są dokładnie takie same, jak w shm.
> > 
> >>Na tym, że możesz wymusić zmapowanie pod określonym adresem. Takim samym w 
> >>różnych programach.
> > 
> > Ależ taka możliwość istniała od samego początku w IPC SHM! Nie zawsze
> > realizowalna, co prawda.

> Dziś poprawiła się ta realizowalność. Kiedyś w ogóle obszar dzielalny był 
> bardzo mały. Dziś jest lepiej.

No super, że się poprawiła, tylko dlaczego miałoby to powodować, że mmap jest
lepszy od shm?

> >>>>pozwala na zrobienie 
> >>>>wspólnego okna w przestrzeniach adresowych wielu procesów, gdzie wskaźniki 
> >>>>zachowują się normalnie.
> >>>
> >>>A pamięć dzielona z IPC działała źle lub nie spełniała któregokolwiek z tych
> >>>założeń?
> > 
> >>AFAIR może być kłopot ze zmapowaniem "na tej samej wysokości".
> > 
> > Ale to dotyczy wszystkich rozwiązań tego typu w równym stopniu.

> Ale teraz nad tym można łatwiej zapanować (więcej jest dostępne).

No super. Tylko ile się w obu tych rozwiązaniach trzeba martwić o zaalokowanie
obiektów w dzielonej pamięci?

> >>>>Nie bardzo zależy. W Javie volatile jest ściśle wyspecyfikowane -- odowłanie 
> >>>>do takiego pola oznacza na natywnej platformie wystosowanie odpwoiednich 
> >>>>barier pamięci (acquire przed i release po odwołaniu). W GCC nic takiego nie 
> >>>>ma. Jak architektura nie ma strict memory ordering to wszystko się rozjeżdża.
> >>>
> >>>Nie stawiałbym tutaj takich tez nt. gcc - chyba że wyraźnie tak piszą w
> >>>specyfikacji tego kompilatora na każdą platformę.
> > 
> >>To pokaż mi taką platformę, gdzie w GCC odwołania do zmiennych volatile są 
> >>owijane w bariery.
> > 
> >>Jak mi nie wierzysz, to spytaj się choćby Piotra Wyderskiego. On GCC używał 
> >>na paru platformach
> > 
> > Nie mówię, że nie wierzę, ani nie twierdzę, że tak nie jest. Po prostu
> > chciałbym zobaczyć jawną deklarację na ten temat (a swoją drogą, nic mi się
> > nie udało ntt. znaleźć).

> Bo AFAIR oni tego nigdzie nie robią. Trudniej jest znaleźć info że czegoś 
> nie ma niż, że coś jest.

No tak - "w domyśle" jest, że nic nie wiemy o barierach pamięci... :)

> pzdr i wesołych świąt!

Pozdro - ja akurat całe trzy fazy świąt spędziłem zdala od sieci, więc stąd to
opóźnienie :)

(trzecia to mój ślub :) )

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"Java is answer for a question that has never been stated"