Jak zaimplementować iterator w stylu STL i uniknąć typowych pułapek?
Stworzyłem kolekcję, dla której chcę zapewnić iterator dostępu losowego w stylu STL. Szukałem przykładowej implementacji iteratora, ale żadnej nie znalazłem. Wiem o potrzebie przeciążenia operatorów []
i *
. Jakie są wymagania, aby iterator był "w stylu STL" i jakie są inne pułapki, których należy unikać (jeśli istnieją)?
Dodatkowy kontekst: jest to dla biblioteki i nie chcę wprowadzać żadnych zależności od niej, chyba że naprawdę muszę. Piszę własną kolekcję, aby móc zapewnić kompatybilność binarną między C++03 i C++11 z tym samym kompilatorem (więc nie ma STL, który prawdopodobnie by się zepsuł).
6 answers
Http://www.cplusplus.com/reference/std/iterator / ma poręczny wykres, który zawiera szczegóły specyfikacji § 24.2.2 standardu C++11. Zasadniczo Iteratory mają znaczniki opisujące poprawne operacje, a znaczniki mają hierarchię. Poniżej jest czysto symboliczne, klasy te nie istnieją jako takie.
iterator {
iterator(const iterator&);
~iterator();
iterator& operator=(const iterator&);
iterator& operator++(); //prefix increment
reference operator*() const;
friend void swap(iterator& lhs, iterator& rhs); //C++11 I think
};
input_iterator : public virtual iterator {
iterator operator++(int); //postfix increment
value_type operator*() const;
pointer operator->() const;
friend bool operator==(const iterator&, const iterator&);
friend bool operator!=(const iterator&, const iterator&);
};
//once an input iterator has been dereferenced, it is
//undefined to dereference one before that.
output_iterator : public virtual iterator {
reference operator*() const;
iterator operator++(int); //postfix increment
};
//dereferences may only be on the left side of an assignment
//once an output iterator has been dereferenced, it is
//undefined to dereference one before that.
forward_iterator : input_iterator, output_iterator {
forward_iterator();
};
//multiple passes allowed
bidirectional_iterator : forward_iterator {
iterator& operator--(); //prefix decrement
iterator operator--(int); //postfix decrement
};
random_access_iterator : bidirectional_iterator {
friend bool operator<(const iterator&, const iterator&);
friend bool operator>(const iterator&, const iterator&);
friend bool operator<=(const iterator&, const iterator&);
friend bool operator>=(const iterator&, const iterator&);
iterator& operator+=(size_type);
friend iterator operator+(const iterator&, size_type);
friend iterator operator+(size_type, const iterator&);
iterator& operator-=(size_type);
friend iterator operator-(const iterator&, size_type);
friend difference_type operator-(iterator, iterator);
reference operator[](size_type) const;
};
Możesz albo specjalizować się std::iterator_traits<youriterator>
, albo umieszczać te same typy w samym iteratorze, albo dziedziczyć z std::iterator
(który ma te typy). Wolę drugą opcja, aby uniknąć zmiany rzeczy w przestrzeni nazw std
i dla czytelności, ale większość ludzi dziedziczy z std::iterator
.
struct std::iterator_traits<youriterator> {
typedef ???? difference_type; //almost always ptrdiff_t
typedef ???? value_type; //almost always T
typedef ???? reference; //almost always T& or const T&
typedef ???? pointer; //almost always T* or const T*
typedef ???? iterator_category; //usually std::forward_iterator_tag or similar
};
Uwaga iterator_category powinien być jednym z std::input_iterator_tag
, std::output_iterator_tag
, std::forward_iterator_tag
, std::bidirectional_iterator_tag
, lub std::random_access_iterator_tag
, w zależności od wymagań, które spełnia Twój iterator. W zależności od iteratora możesz wybrać specjalizację std::next
, std::prev
, std::advance
, i std::distance
również, ale to rzadko jest potrzebne. W niezwykle rzadkich przypadkach możesz chcieć specjalizować się std::begin
i std::end
.
Twój kontener powinien prawdopodobnie mieć również const_iterator
, który jest (prawdopodobnie mutowalnym) iteratorem do stałych danych, które są podobne do twojego iterator
, z wyjątkiem tego, że powinien być niejawnie konstruowany z iterator
, a użytkownicy nie powinni być w stanie modyfikować danych. Często jego wewnętrzny wskaźnik jest wskaźnikiem do niestałych danych i ma iterator
dziedziczenie od const_iterator
, aby zminimalizować powielanie kodu.
Mój post na pisanie własnego kontenera STL ma więcej kompletny prototyp kontenera/iteratora.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-10-17 23:12:46
Dokumentacja iterator_facade z Boost.Iterator zapewnia coś, co wygląda jak ładny samouczek na temat implementacji iteratorów dla połączonej listy. Czy mógłbyś użyć tego jako punktu wyjścia do zbudowania iteratora o dostępie losowym nad Twoim kontenerem?
Jeśli nic innego, możesz spojrzeć na funkcje Członkowskie i typedefs dostarczone przez iterator_facade
i użyć go jako punktu wyjścia do budowania własnych.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-11-08 17:18:51
Thomas Becker napisał przydatny artykuł na ten temat tutaj .
Było też takie (być może prostsze) podejście, które pojawiło się wcześniej w SO: Jak poprawnie zaimplementować niestandardowe Iteratory i const_iteratory?
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:02:58
Oto próbka iteratora raw pointer.
Nie powinieneś używać klasy iterator do pracy z surowymi wskaźnikami!
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <assert.h>
template<typename T>
class ptr_iterator
: public std::iterator<std::forward_iterator_tag, T>
{
typedef ptr_iterator<T> iterator;
pointer pos_;
public:
ptr_iterator() : pos_(nullptr) {}
ptr_iterator(T* v) : pos_(v) {}
~ptr_iterator() {}
iterator operator++(int) /* postfix */ { return pos_++; }
iterator& operator++() /* prefix */ { ++pos_; return *this; }
reference operator* () const { return *pos_; }
pointer operator->() const { return pos_; }
iterator operator+ (difference_type v) const { return pos_ + v; }
bool operator==(const iterator& rhs) const { return pos_ == rhs.pos_; }
bool operator!=(const iterator& rhs) const { return pos_ != rhs.pos_; }
};
template<typename T>
ptr_iterator<T> begin(T *val) { return ptr_iterator<T>(val); }
template<typename T, typename Tsize>
ptr_iterator<T> end(T *val, Tsize size) { return ptr_iterator<T>(val) + size; }
Obejście pętli opartej na surowym zakresie wskaźników. Proszę, popraw mnie, jeśli istnieje lepszy sposób na zrobienie pętli opartej na zakresie z surowego wskaźnika.
template<typename T>
class ptr_range
{
T* begin_;
T* end_;
public:
ptr_range(T* ptr, size_t length) : begin_(ptr), end_(ptr + length) { assert(begin_ <= end_); }
T* begin() const { return begin_; }
T* end() const { return end_; }
};
template<typename T>
ptr_range<T> range(T* ptr, size_t length) { return ptr_range<T>(ptr, length); }
I prosty test
void DoIteratorTest()
{
const static size_t size = 10;
uint8_t *data = new uint8_t[size];
{
// Only for iterator test
uint8_t n = '0';
auto first = begin(data);
auto last = end(data, size);
for (auto it = first; it != last; ++it)
{
*it = n++;
}
// It's prefer to use the following way:
for (const auto& n : range(data, size))
{
std::cout << " char: " << static_cast<char>(n) << std::endl;
}
}
{
// Only for iterator test
ptr_iterator<uint8_t> first(data);
ptr_iterator<uint8_t> last(first + size);
std::vector<uint8_t> v1(first, last);
// It's prefer to use the following way:
std::vector<uint8_t> v2(data, data + size);
}
{
std::list<std::vector<uint8_t>> queue_;
queue_.emplace_back(begin(data), end(data, size));
queue_.emplace_back(data, data + size);
}
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-09-29 09:53:41
Po pierwsze możesz przejrzeć tutaj listę różnych operacji, które poszczególne typy iteratorów muszą obsługiwać.
Następnie, po utworzeniu klasy iteratora musisz albo specjalizować się std::iterator_traits
dla niego i dostarczyć kilka niezbędnych typów (takich jak Kategoria iteratora lub typ wartości) lub alternatywnie wywodzić go z std::iterator
, który definiuje dla Ciebie potrzebne typy i dlatego może być używany z domyślnym std::iterator_traits
.
Zastrzeżenie: I wiem, że niektórzy ludzie nie lubią cplusplus.com
aż tak bardzo, ale dostarczają naprawdę przydatnych informacji na ten temat.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-11-08 17:48:02
Byłem / jestem w tej samej łodzi co ty z różnych powodów (częściowo edukacyjnych, częściowo ograniczeń). Musiałem ponownie napisać wszystkie kontenery biblioteki standardowej i kontenery musiały być zgodne ze standardem. Oznacza to, że jeśli zamienię mój kontener na wersję stl, Kod będzie działał tak samo. Co również oznaczało, że musiałem ponownie napisać Iteratory.
W każdym razie, spojrzałem na EASTL . Oprócz nauki tony o pojemnikach, których nigdy nie nauczyłem się przez cały ten czas korzystając z kontenerów stl lub poprzez moje studia licencjackie. Głównym powodem jest to, że EASTL jest bardziej czytelny niż odpowiednik stl (znalazłem to po prostu z powodu braku wszystkich makr i prostego stylu kodowania). Jest tam kilka ohydnych rzeczy (takich jak #ifdefs dla wyjątków), ale nic cię nie przytłacza.
Jak inni wspominali, spójrz na cplusplus.com odniesienie do iteratorów i kontenerów.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-11-30 09:35:46