Czy iterator kontenera może dać coś innego niż l-wartość?

Question

Doszedłem do wniosku, że nie da się napisać zgodnego kontenera, którego value_type nie był zapisany bezpośrednio w kontenerze. Myślę, że to niefortunne, ponieważ często kończę, żałując, że nie mam pojemników, w których typ wartości jest albo częściowo obliczony, albo złożony z nieistotnych elementów (przykłady poniżej, ale nie bezpośrednio związane z pytaniem). Wiem, jak pisać iteratory, które używają obiektów proxy, chociaż jest to dość denerwujące. Ale teraz zastanawiam się, czy naprawdę istnieje przestrzeń w standardzie C++ dla takich zwierząt. Jest tu prawdopodobnie zbyt dużo słownictwa; wersja tl; dr jest prosta: co naprawdę oznaczają akapity 1 i 6 z § 24.2.5 iw jakim stopniu naruszenie oczywistego znaczenia przerwie standardowe algorytmy? Lub, mówiąc inaczej, jak można je interpretować, aby umożliwić iteratory proxy?

Jak zauważa Pete Becker, tak naprawdę nic nie zmusza moich pojemników do spełnienia wymagań określonych dla standardowych pojemników bibliotecznych. Aby jednak użyć kontenera z wieloma standardowymi algorytmami, musi on mieć iterator zgodności z co najmniej forward_iterator_tag, lub musi kłamać, ale wciąż udaje mu się spełnić operacyjne (jeśli nie formalne) wymagania, które konkretny algorytm nakłada na jego iteratory.

Oto moje rozumowanie:

Tabela 96 (§ 23.2.1), wymagania kontenerów, obejmuje:

Expression  Return type   Assertion/note 
------------ -------------  --------------------- 
X::iterator iterator type  any iterator category 
       whose value   that meets the 
       type is T   forward iterator 
            requirements. 
            Convertible to 
            const_iterator. 

a.begin()  iterator; 
       const_iterator for 
       constant a. 

Teraz naprzód iterator:

§ 24.2.5, para. 1:

Typ lub wskaźnik typu X spełnia wymagania przyszłego iteratora, jeśli & hellip;

- jeśli X jest zmiennym iteratorem, reference jest odniesieniem do T; jeśli X jest const iterator, reference jest nawiązaniem do const T

To prawda, że ​​nie ma bezpośredniego wymogu *a wrócić reference (gdzie a jest typu X). Te wymagania są następujące:

z Tabeli 107 (iteratorami wejściowe) *a musi być „zamienny do T”, jeśli a jest dereferencable.

z Tabeli 106 (iteratorami) *r musi typu reference gdzie r jest typu X& i dereferencable.

Jednakże, tabela 106 określa, że ​​++r powraca X& tak *++r musi reference. Ponadto (zgodnie z Tabelą 107), *a++ musi być reference, chociaż (Tabela 109) a[n] wymaga jedynie "wymienialności na odniesienie". Muszę powiedzieć, że nie rozumiem, jak *a gdzie jest typu X i *r gdzie r jest innego typu, ale może brakuje mi jakiejś subtelności.

Może jest tu mały pokoik do skakania, ale nie za wiele; w pewnym momencie musisz być przygotowany do utworzenia T, jeśli nie masz go w kontenerze, abyś mógł podać do niego odniesienie.

Ale kicker jest

§ 24.2.5, ust. 6 (a i b są wartościami typu X): Jeśli a i b oba dereferenceable, następnie a == b wtedy i tylko wtedy, gdy *a i *b są przyłączone do tego samego obiektu.

nie mogę znaleźć formalną definicję bound to, ale wydaje mi się, że zwykle strategia dokonywania iteratory non-adresowalnych obiektów jest utworzyć obiekt proxy, zwykle przechowywany wewnątrz samego iteratora. W tym przypadku wymagałoby to niezwykle hojnego zrozumienia tego, co "związany" oznacza interpretowanie 24.2.5/6 w jakikolwiek sposób inny niż zakazywanie porównań równości pomiędzy dwoma różnymi obiektami iteracyjnymi, nawet jeśli logicznie wskazują one tę samą pozycję w pojemniku.

Z drugiej strony zauważam, że Dietmar Kühl, którzy powinni wiedzieć, w swojej odpowiedzi do this question mówi, że:

C++ 2011 dostał wymagania zrelaksowany i iteratory niekoniecznie są wymagane w celu uzyskania lwartością

Czy zatem iterator może zwrócić proxy, czy nie? Jeśli tak, jaki jest charakter takiego proxy? Gdzie moje rozumowanie, że taki iterator nie jest zgodny, nie działa?

---

Zgodnie z obietnicą, kilka pojemników, których skuteczne value_types nie będą przechowywane w sposób zwarty w pojemniku:

1) Kompaktowy pojemnik asocjacyjne którego klucz i wartość typy mogą być bardziej efektywnie przechowywane w dwóch oddzielnych wektorach. (Prowadzenie klucze w wektor może również zwiększyć przyjazność cache, jak również zmniejszenie narzutu przydziału.)

2) vector<T> które udający map<integer_type, T> upraszcza interoperacyjność z innymi map<X, T> typów.

3) Kontener logiczny utworzony przez zapakowanie kilku innych kontenerów, tworząc logiczny typ wartości, który jest tuple odniesień do typów wartości spakowanych pojemników. (W niektórych aplikacjach jeden lub więcej spakowanych pojemników może być całkowicie wyliczonych, jako funkcja innych wartości lub jako numer kolejny.)

4) Widok kontenera typu agregatowego, który ma tylko niektóre wartości. (Całkiem możliwe, zarówno podstawowy kontener, jak i widok są krotkami, gdzie lista widokowa krotki widoku jest podzbiorem, prawdopodobnie w innej kolejności, typów bazowych kontenerów).

Jestem pewien, że inni ludzie mogliby łatwo dodać do tej listy; to tylko te, które w ciągu ostatnich miesięcy włamałem się w jakiś sposób.

Answer 1

Nie ograniczaj się, myśląc o "zgodnym pojemniku": nie ma nic w standardzie, który zależy od posiadania.Pomyśl o wymaganiach kontenera jako skrótowym opisie wymagań dla kontenerów zdefiniowanych w standardzie. Nic więcej. Dopóki iteratory, które twój kontener produkuje, są poprawne, nie ma problemu z wszystkimi odpowiednimi algorytmami i, prawdopodobnie, z algorytmami, które sam piszesz.

Answer 2

Najlepszy model to std::vector<bool>. Jest to tak bliskie jak to tylko możliwe, ale jego iteratory dostarczają serwerów proxy.

Standard nawet określa, że ​​std::vector<bool>::reference jest klasą. Jednak tabela wymagań dotyczących kontenera określa, że ​​X::reference daje "l-wartość T." W związku z tym jest ściśle niezgodny.

Ale iteratory nie są powiązane z T. Iterator value_type musi być i sprawdzając wymagania dotyczące Iteratora wejść, reference musi zostać przekonwertowany na value_type.

Jak wspomina Pete Becker, tabele wymagań są raczej szerokimi koce, a indywidualne algorytmy określają, czego potrzebują. Jedynie algorytm, który wymaga, aby reference rzeczywiście był referencją, zostanie przerwany, co jest po prostu stwierdzeniem oczywistości.