🚀 go-pugleaf

Sektor van Skijlen wrote:
>>>>Nie, nie chodziło. Chodzi o to, że w Pythonie masz a = [1, 2, 3]
>>>>a w C++ masz:
>>>>std::list a;
>>>>a.push_back(1);
>>>>a.push_back(2);
>>>>a.push_back(3);
>>>
>>>Super - ale (skoro, jak mówisz, w Pythonie jest dużo fajnych zbiorników) czy
>>>można tak inicjalizować również dowolny, napisany przez siebie zbiornik?
> 
>>Tak.
> 
> Ok, to oznacza, że nie ma żadnego zbiornika specjalnie wpasowanego w język?

Nie, nie oznacza. Lista występuje jako literał. konstrukcja *arg to zamiana 
sekwencji nienazwanych argumentów na ... listę (**arg zamienia argumenty 
nazwane na słownik). Tupel, lista, słownik, napisy, itd występują 
bezpośrendio w konstrukcjach języka bardzo często i bardzo wszechstronnie.


>>>>>>Och i ach. Python nie.
>>>>>
>>>>>No to ma problem na własne życzenie. Żaden z języków skryptowych "starej
>>>>>szkoły" takich debilizmów nie robi.
>>>
>>>>Sektor zamiast chrzanić, przeczytaj sobie jaka jest różnica. Zostawiam jako 
>>>>zadanie domowe :)
>>>
>>>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.


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

>>A piszesz bzdury, bo np. te typy przez to, ze się różnią mają inne 
>>charakteryskytki wydajnościowe.
> 
> LOL, Python i wydajność. Weź ty mnie nie rozśmieszaj z łaski swojej.

Nie epatuj niewiedzą.
Różnice w asmymptotycznej złożoności są wystraczająco istotne, by na nich 
się oprzeć.


> Ani Perl, ani Tcl nie posiadają osobnego zbiornika do takich zastosowań i
> jakoś wcale ich Python przez to nie przegania.

Dla Perla jest Psyco? Dla TCL też? Porównaj sobie kod pod Psyco z jakimś 
męczeniem TCL-a. Jeśli kod nie wisi na IO albo na grubym kodzie z rantajmu 
to różnica o 2 rzędy wielkości jest całkiem prawdopodobna.


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

> iteratory z dereferencją i inkrementacją wspólne, to znaczy, że jawnie mijasz
> się z prawdą. Po co?

Trzeba było czytac uważnie.


>>>>>>map wyłazi zupełnie z jej iteracją po parach. list jest w ogóle 
>>>>>>w poprzek, itd...
>>>>>
>>>>>>O jakiś spójnych gwarancjach już lepiej nie myśleć.
>>>>>
>>>>>Nie rozumiem nadal. Nie podałeś ani jednego konkretu. Opisanie które zbiorniki
>>>>>są twoim zdaniem niejednolite nic nie znaczy.
>>>
>>>>popatrz sobie na interfejs list i vector. Zrób mi vector::sort(), czy 
>>>>vector::splice(whatever) list::at, itd...
>>>
>>>To ty do tej pory nie wiesz o tym, że do zbiorników swobodnego dostępu należy
>>>stosować algorytm introsort (czyli std::sort), a do zbiorników dwukierunkowych
>>>algorytm mergesort (czyli std::stable_sort),
> 
>>Sektor co ty za bzdury piszesz?!?!!
> 
> Doprawdy?

W rzeczy samej.

> 
> 
>>Standard *nigdzie* nie mówi jaki algorytm gdzie ma być użyty.
> 
> I CO Z TEGO???

I to że to są bzdury.

>>Podaje tylko minimalne wymagania wydajnościowe, i właśnie stabilności.
> 
> ROTFLOL.

Tak, twoja niewiedza, jako gościa mieniącego się jako expert od C++, jest 
porażająca


> Powiedz mi najpierw może, dlaczego poniższy program się nie kompiluje:
[błedny programik ciach]

Bo sort wymaga iteratora o dostępie swobodnym.


>>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. 
BTW w implementajach któ¶e znam to sortowowanie jest badziewne -- stosunkowo 
naiwny quicksort wychodzi o 20-30% lepiej.


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

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

> 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. I można mieć sortowanie bez obowiązku zachowania stabilności 
dla iteratorów sekwencyjnych. Łączenie dwu ortogonalnych cech jest błedem 
projektowym.

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

Zwłąszcza, że język pozwala na specjalizację szablonu dla różnych typów.


> Ale nie zaproponowałeś.
> 
> Taką propozycję można by jeszcze poddać pod dyskusję i ja nawet mam sporo
> argumentów przeciw.
> 
> 
>>>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ć.


>>>To jest kwestia koncepcji, jakie te
>>>zbiorniki spełniają (polecam dokumentację do STL-a).
> 
>>To jest kwestia chaosu projektowego.
> 
> Twoje odpowiedzi sugerują, że w ogóle nie rozumiesz, o czym mowa. Podejmij
> dyskusję w tych kategoriach, a może do czegoś ciekawego dojdziemy, zamiast
> rzucać naokoło mięsem.



> 
> 
>>>Lista nie spełnia
>>>koncepcji zbiornika swobodnego dostępu, a jedynie zbiornika dwukierunkowego, a
>>>koncepcja zbiornika dwukierunkowego nie zawiera operator[] ani metody at().
> 
>>No i co to ma do sort czy splice?
> 
> To, że obie te operacje są specyficzne dla zbiornika std::list?
> 
> BYĆ MOŻE sort nie jest operacją LOGICZNIE specyficzną dla tego zbiornika, lecz
> sposób jej implementacji również ma znaczenie dla interfejsu.

Właśnie C++ pozwala to zrobić bez plątania w to interfejsu.

> Do czego chciałbyś zastosować "ogólny sort"? Jesteś w stanie napisać algorytm,
> który w środku zawiera sortowanie i pracuje na dowolnym zbiorniku?

Nie musze takiego pisać. Wystarczy skorzystać z możliwości specjalizacji 
szablonu dla konkretnego typu.

> list::sort sortuje CAŁY zbiornik i może działać tylko na jednym zbiorniku, bo
> przestawia węzły. Ale uwaga: tego algorytmu nie da się wykonać na części
> zbiornika.

Dałoby się bez problemu, gdyby to było do rzeczy wymyślone.

> A wszystkie algorytmy sortujące mają się dać wykonać na części
> zbiornika.

No i? Nie ma tu żadnego fundamentalnego problemu. Tu jest tylko krzywy 
design C++.


> Te algorytmy muszą pracować na części zbiornika, bo taka jest gwarancja dla
> wszystkich algorytmów (bezsensowna moim zdaniem, ale tak zdecydowano).
> 
> I nie przypadkiem algorytmy sortujące wymagają zbiornika swobodnego dostępu.
> 
> Wynika to stąd, że [ciach]

Plączesz się w szczegółach jakiegoś konkretnego algorytmu. Standard 
algorytmu nie determinuje


> Żebyś się zesrał, nie jesteś w stanie napisać procedury sortowania ZAKRESU
> elementów zbiornika std::list takiego, żeby nie wymagał jednocześnie podania
> referencji do samego zbiornika.

Nonsens. Wystarczy, żeby zbiornik i jego iterator był odpowiednio 
zaprojektowany.

> Co równocześnie oznacza, że nie jesteś w
> stanie napisać zewnętrznej funkcji, która przyjmie tylko granice zakresów, i
> będzie działała dla listy.

Dla takiej jaka jest teraz być może nie. Ale już powiedziłem, ża taka jeka 
jest, jest do dupy.


> Skoro tak, to nie jesteś w stanie napisać std::sort tak, żeby działało i dla
> vectora i dla listy.

Jestem.

> Czemu ja ci muszę takie podstawowe rzeczy tłumaczyć?

Twoje tłumaczenie że białe jest czarne na mnie nie działa.


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


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


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


>>>Może twoim zdaniem powinny one mieć wszystkie te same metody, wszystkie te
>>>same zależności, wszystkie te same wymagania, a nawet jeszcze niech mają taką
>>>samą implementację. Wtedy będą spójne. A nie, cholera, będą miały inne nazwy.
> 
>>Nonsens. Zgubiłeś problem.
>>Operacje robiące to samo mają mieć interfejs taki sam. A nie mają.
> 
> Teoretycznie masz rację, tylko pod warunkiem, że jesteś w stanie:
> a) zdefiniować wygodny interfejs
> b) zrobić implementację do tego interfejsu
> 
> W przypadku std::sort, skoro już o tym mowa, możesz zrobić interfejs, który
> wymaga podania, zbiornika, początku i końca, ale nie bęzie on wygodny. Można
> zrobić metodę sort dla zbiornika, również z zakresami, ale co wtedy ze
> zbiornikami, które nie mają metod, a są sortowalne (np. surowa tablica)?

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.


> Wspólny i jednolicie opisany interfejs ma sens, jeśli stosujemy go do typów,
> które chciałyby mieć ten interfejs jako część swojego generycznego interfejsu.
> Jeśli jednak generyczność tego interfejsu nie ma uzasadnienia, to i
> ujednolicać go na siłę nie ma po co.

Generyczność ma uzasadnienie. Ale została olana.

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

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


>>Mapa powinna mieć dwa iteratory -- 
>>jeden po wartościach
> 
> Po co?

Bo tak jest wygodniej i czytelniej? I *spójniej*?

>>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!


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

> 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++


>>>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!


>>>>>>>>>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!


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


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


>>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 :) Brak odwołań do stery może przynieść zysk o 1-2 
rzędy wielkości. I wtedy cudowanie może się opłacić.


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


>>>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? 
Sektor -- albo projekt jest bezsensownie skomplikowany (a więc do kitu) albo 
właśnie oszukujesz.

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.

>>>>Nie. Dopiero teraz coś konkretnego jest, ale i tak mało.
>>>
>>>Przestawiłem ci nie wymagania co do działania programu, tylko wymagania co do
>>>zbiornika. 
> 
>>Nie przedstawiłeś żadnych wystarczających wymagań.
> 
> Nie wskazałeś mi, dlaczego wymagania są niewystarczające. Najpierw zacząłeś
> wymyślać rozwiązania i narzekasz dopiero gdy wytknąłem ci błędy.

Wskazuję cały czas. Teraz widzę, że te wymagania dodatkowo motasz.


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


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

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


> I pod warunkiem, że hash ci dobrze wyhaszuje obiekt, bo równie dobrze może ci
> zrobić "rzadkie drabinki" i cała "amortyzacja" weźmie w łeb.
> 
> No więc dobrze, załóżmy nawet teoretycznie, że jesteś w stanie uzyskać lepszy
> czas, niż logarytmiczny (kosztem większego zużycia pamięci swoją drogą) - ale
> stuprocentowo stałego czasu (co gwarantuje ci std::list) nie uzyskasz i tak.

Jeśli jest good eqough to się nie będę przejmował. Jeśli nie to się będę 
wtedy martwił. Zacznę od odpalenia psyco.


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

> BTW ciekaw jestem jak w takim razie te
> obiekty mają zdefiniowane porządkowanie.

Porządkowanie nie jest potrzebne. Potrzebny jest dobry hash.


>>>>>>Nie robię. Bezpieczna implementacja Pascala jest możliwa i jest naturalna. W 
>>>>>>odróżnieniu od bezpiecznej implementacji C czy C++.
>>>>>
>>>>>Jasne - po pozbawieniu Pascala np. wskaźników.
>>>
>>>>Akurat wskaźniki nie przeszkadzają w bezpiecznej implementacji jeśli nie 
>>>>masz na nich arytmetyki (a oryginalny Pascal AFAIR nie miał).
>>>
>>>Czyżby? I masz udokumentowaną obsługę sytuacji wyjątkowej w przypadku
>>>zerowego lub wiszącego wskaźnika?
> 
>>Mogę bez problemu mieć taką implementację. Bezpieczna implementacja C (oraz 
>>C++) jest praktycznie niemożliwa.
> 
> Z czego to wynika?

Z pomieszania tablic i wskaźników. Z wpuszczenia niekontrolowanych typów 
gdzie można biegac po ich reprezentacji, itd...


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


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


>>>>>>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&


>>>Ale nie SFINAE.
> 
>>To czemu SFINAE nie działało w tych częsciej używanych kompilatorach?
> 
> Prawdopodobnie z tych samych powodów, z których nie działają inne rzeczy
> zgodne ze standardem.

Wtedy nie było standardu. Twierdzę po prostu, że SFINAE doszło a nie było od 
początku.

[...]
>>Przy dynamicznej kontroli kompilator może co najwyżej postarać się -- ale 
>>niegdy nie odfiltruje każdej sytuacji. Żeby mógł, potrzebna byłaby statyczna 
>>kontrola specyfikacji (jak w Javie).
> 
> 
> Albo weryfikiacja skrośna.
[...]
> 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.


>>>>>>>>Ani o tym ani o tym. Chodzi o to, by błędy wykonania były "contained". Niech 
>>>>>>>>sobie będzie abort, wyjątek, cokolwiek, ale niech po pierwsze będzie a po 
>>>>>>>>drugie niech będzie tylko to (a nie losowa poprawka do przetwarzanych danych).
>>>>>>>
>>>>>>>Dobrze, nawet się zgadzam. To teraz przystaw to do praktycznych możliwości
>>>>>>>realizacji powyższych założeń.
>>>>>>>
>>>>>>>Jeśli chodzi np. o odwołanie się do zerowego wskaźnika, to masz tu dwie
>>>>>>>możliwości: albo w języku sprawdzasz wskaźnik przed każdym odwołaniem
>>>>>>>(usuwając jedynie zbędne sprawdzenia, gdy jest to bezużyteczne), albo
>>>>>>>posiadasz platformę wirtualną, na której uruchamiany jest program, i która to
>>>>>>>platforma sama posiada odpowiednie właściwości pozwalające na wygenerowanie
>>>>>>>wyjątku w takim przypadku. W obu przypadkach mamy do czynienia z dodatkowym
>>>>>>>narzutem, który jest tylko czasem akceptowalny.
>>>>>
>>>>>>W większości systemów nie embedded masz tą wirtualizację daną z góry i nie 
>>>>>>masz wyboru.
>>>>>
>>>>>Ale to się do niczego nie nadaje.
>>>
>>>>Co się nie nadaje? To się zachowuje całkowicie deterministrycznie. Zarówno 
>>>>na windowsach, gdzie jest SEH jak i nauniksach, gdzie masz sygnały moża 
>>>>rzecz załatwić na poziomie runtime języka.
>>>
>>>
>>>Rzecz w tym, że to nie takie proste.
>>>
>>>Nie każdy system posiada systemową implementację takiej np. malloc. Czy dziś
>>>jakieś systemy nie mają - tego nie wiem, ale w którymś ze starszych
>>>posixowych systemów funkcja malloc była normalną funkcją użytkownika i sama
>>>zarządzała zasobami, w kwestii systemu poprzestając jedynie na sbrk().
> 
> 
>>Nadal malloc jest funkcją użytkownika tylko nie koniecze z systemu woła się 
>>sbrk(). Tylko co to ma do rzucania GPF przy odwołaniu pod adres 0? Na 
>>Windzie mie działa, na Linuksie takoż.
> 
> 
> Rzecz w tym, że nie działa spójnie, ani na jednym, ani na drugim.
> 
> Na Windowsie to nie wiem, czy daje się przechwycić (ale jakoś musi się dać,
> skoro Cygwin to tłumaczy na SIGSEGV).

Daje się. Tam masz systemowy SEH (Structured Exception Handling) i można to 
łapać jak zwykły wyjątek.


> Na posixach powiedzmy, że na upartego by się dało przechwytując SIGSEGV, ale
> odwołanie do zerowego wskaźnika to nie jedyna przyczyna tego sygnału i nie da
> się jej nijak wyodrębnić.

Kiedy leci sygnał w jego strukturę (dostępną również dla użytkownika) 
wpisywane są rozmaite informacje, zależne od typui sygnału. Tu masz np. 
wpisywany "faulting address", w przypadku null dereference to to jest po 
prostu 0.
To jak najbardziej można przechwycić i jest to wykorzystywane w różnych 
ciekawych miejscach (np. w wielowątkowych odśmiecaczach).


>>>Co
>>>oznacza np., że aplikacja nigdy nie oddawała do systemu przydzielonej pamięci,
>>>a także przydzielała przez sbrk() większe bloki i wydzielała kawałki tortu z
>>>jej środka. W takim przypadku niemożliwe jest określenie, czy odwołanie do
>>>określonego miejsca w pamięci odwołuje się do przydzielonego kawałka, czy nie.
> 
>>Mówiliśmy od odwołaniu do NULL a nie do dowolnego kawałka.
> 
> Tak, ale NULL to nie jest jedyny problem. Co więcej, nawet ten problem nie
> jest rozwiązywalny.

Ten jest rozwiązywalny łatwo. Inne nie tak łatwo (tzn. z dodatkowym 
kosztem). Ale jak ktoś potrzebuje silnego security to musi się na określone 
koszty zgodzić.


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

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

Albo zobacz takie Qemu+KQemu czy VMWare -- to jest znowu maszyna 
niewątpliwie wirtualny (caływ wirtualny pecet) a kod jest wykonywany w 
zdecydowanej większości natywnie.

>>Że są wyjścia unmanaged do poziomu platofrmy natywnej?
> 
> To akurat jest bez różnicy - jedyna różnica to jak zostaną skompilowane
> poszczególne operacje.
> 
> 
>>W Javie też możesz tak sobie zrobić.
> 
> Doprawdy? Jak? Czy istnieje jakieś unchecked/unsafe w Javie, o którym nie
> wiem, czy można metody natywne implementować w Javie? Nigdy o tym nie
> słyszałem.

Jest jak najbardziej interfejs do kodu natywnego. Tak działa choćby 
widgetset używany w Eclipse.


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


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

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


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

[...]
>>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


>>>>A w standardzie C++ volatile dotyczy tylko i wyłącznie sygnałów i nic 
>>>>więcej. O wątkach nie ma mowy bo takie pojęcie w C++ nie występuje
>>>
>>>To się akurat zgadza.
> 
>>I tu jest różnica w stosunku do Javy. Sygnały są wykonywane zawsze w tym 
>>samym kontekscie (na tym samym rdzeniu) co proces.
> 
> Pod warunkiem, że nie jest to sygnał, który dostaje wątek potomny w
> zastępstwie.

Ale wtedy wykonywany jest w kontekscie tego wątku potomnego.


pzdr
\SK