KSS Utility
C++ general utilities
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends
iterator.hpp
Go to the documentation of this file.
1 //
2 // iterator.hpp
3 // kssutil
4 //
5 // Created by Steven W. Klassen on 2014-10-24.
6 // Copyright (c) 2014 Klassen Software Solutions. All rights reserved.
7 //
8 // This file provides iterator implementations based on common operations that need to
9 // be provided by the container classes. In most cases there are two template types that
10 // must be provided: Container which specifies the container class which provides the
11 // necessary operations, and T which specifies the type of data that the iterator
12 // provides access to.
13 //
14 // Licensing follows the MIT License.
15 //
16 
23 #ifndef kssutil_iterator_hpp
24 #define kssutil_iterator_hpp
25 
26 #include <algorithm>
27 #include <cstddef>
28 #include <iterator>
29 #include <memory>
30 #include <utility>
31 
32 #include "add_rel_ops.hpp"
33 #include "utility.hpp"
34 
35 namespace kss { namespace util { namespace iterators {
36 
60  template <typename Container, typename T>
62  : public std::iterator<std::forward_iterator_tag, T, ptrdiff_t, const T*, const T&>
63  {
64  public:
65 
76  ForwardIterator() : _cont(nullptr) {}
77  explicit ForwardIterator(Container& cont) {
78  if (cont.hasAnother()) {
79  _cont = &cont;
80  operator++();
81  }
82  else {
83  _cont = nullptr;
84  }
85  }
86 
87  ForwardIterator(const ForwardIterator& it) = default;
89  : _cont(it._cont), _value(std::move(it._value))
90  {
91  it._cont = nullptr;
92  }
93 
94  ForwardIterator& operator=(const ForwardIterator& it) = default;
96  if (&it != this) {
97  _cont = it._cont;
98  _value = std::move(it._value);
99  }
100  return *this;
101  }
102 
109  bool operator==(const ForwardIterator& it) const noexcept {
110  if (&it == this) { return true; }
111  if (_cont == it._cont) { return true; }
112  return false;
113  }
114  inline bool operator!=(const ForwardIterator& it) const noexcept {
115  return !operator==(it);
116  }
117 
122  const T& operator*() const { return _value; }
123  const T* operator->() const { return &_value; }
124 
138  // preconditions
139  if (!_cont) {
140  _KSSUTIL_PRECONDITIONS_FAILED
141  }
142 
143  if (_cont->hasAnother()) {
144  _cont->next(_value);
145  }
146  else {
147  _cont = nullptr;
148  }
149 
150  return *this;
151  }
153  ForwardIterator it = *this;
154  operator++();
155  return it;
156  }
157 
161  void swap(ForwardIterator& b) noexcept {
162  if (this != &b) {
163  std::swap(_cont, b._cont);
164  std::swap(_value, b._value);
165  }
166  }
167 
168  private:
169  Container* _cont;
170  T _value;
171  };
172 
173 
200  template <typename Container>
202  : public kss::util::AddRelOps<RandomAccessIterator<Container>>,
203  public std::iterator<
204  std::random_access_iterator_tag,
205  typename Container::value_type,
206  typename Container::difference_type,
207  typename Container::pointer,
208  typename Container::reference >
209  {
210  public:
211  RandomAccessIterator() = default;
212 
213  explicit RandomAccessIterator(Container& container, bool isEnd = false)
214  : _container(&container), _pos(isEnd ? container.size() : 0)
215  {}
216 
217  RandomAccessIterator(const RandomAccessIterator&) = default;
218  ~RandomAccessIterator() noexcept = default;
219  RandomAccessIterator& operator=(const RandomAccessIterator& it) noexcept = default;
220 
221  // Two iterators are considered equal if they are both pointing to the same position
222  // of the same container. The inequality comparisons only check the positions, they do
223  // not check the container. Note that the "missing" comparison operators are added
224  // via the AddRelOps declaration.
225  bool operator==(const RandomAccessIterator& rhs) const noexcept {
226  return (_container == rhs._container && _pos == rhs._pos);
227  }
228  bool operator<(const RandomAccessIterator& rhs) const noexcept {
229  return (_pos < rhs._pos);
230  }
231 
232  // Dereference the iterators. Note that to obtain maximum efficiency (since this
233  // is expected to be done a lot) we do not check if _container and _pos are
234  // valid. If they are not, you can expect a SEGV or something similarly bad
235  // to happen.
236  typename Container::reference operator*() { return (*_container)[_pos]; }
237  const typename Container::reference operator*() const { return (*_container)[_pos]; }
238  typename Container::pointer operator->() { return &(*_container)[_pos]; }
239  const typename Container::pointer operator->() const { return &(*_container)[_pos]; }
240  typename Container::reference operator[](size_t i) { return (*_container)[_pos+i]; }
241  const typename Container::reference operator[](size_t i) const { return (*_container)[_pos+i]; }
242 
243  // Pointer arithmetic. For efficiency reasons we do not check if the resulting
244  // position is valid.
245  RandomAccessIterator& operator++() noexcept { ++_pos; return *this; }
247  RandomAccessIterator tmp(*this);
248  operator++();
249  return tmp;
250  }
251  RandomAccessIterator& operator+=(typename Container::difference_type n) noexcept {
252  (n >= 0 ? _pos += size_t(n) : _pos -= size_t(-n));
253  return *this;
254  }
255  RandomAccessIterator operator+(typename Container::difference_type n) const noexcept {
256  RandomAccessIterator tmp(*this);
257  tmp += n;
258  return tmp;
259  }
260 
261  RandomAccessIterator& operator--() noexcept { --_pos; return *this; }
262  RandomAccessIterator& operator-=(typename Container::difference_type n) noexcept {
263  (n >= 0 ? _pos -= size_t(n) : _pos += size_t(-n));
264  return *this;
265  }
266  RandomAccessIterator operator-(typename Container::difference_type n) const noexcept {
267  RandomAccessIterator tmp(*this);
268  tmp -= n;
269  return tmp;
270  }
271  typename Container::difference_type operator-(const RandomAccessIterator& rhs) const noexcept {
272  return typename Container::difference_type(_pos >= rhs._pos ? _pos - rhs._pos : -(rhs._pos - _pos));
273  }
274 
278  void swap(RandomAccessIterator& b) noexcept {
279  if (this != &b) {
280  std::swap(_container, b._container);
281  std::swap(_pos, b._pos);
282  }
283  }
284 
285  private:
286  Container* _container = nullptr;
287  size_t _pos = 0;
288  };
289 
290  template <typename Container>
291  inline RandomAccessIterator<Container> operator+(typename Container::difference_type n,
292  const RandomAccessIterator<Container>& c) noexcept
293  {
294  return (c + n);
295  }
296 
297 
304  template <typename Container>
306  : public kss::util::AddRelOps<ConstRandomAccessIterator<Container>>,
307  public std::iterator<
308  std::random_access_iterator_tag,
309  typename Container::value_type,
310  typename Container::difference_type,
311  typename Container::const_pointer,
312  typename Container::const_reference >
313  {
314  public:
315  ConstRandomAccessIterator() = default;
316 
317  explicit ConstRandomAccessIterator(const Container& container, bool isEnd = false)
318  : _container(&container), _pos(isEnd ? container.size() : 0)
319  {}
320 
322  ~ConstRandomAccessIterator() noexcept = default;
323  ConstRandomAccessIterator& operator=(const ConstRandomAccessIterator& it) = default;
324 
325  // Two iterators are considered equal if they are both pointing to the same position
326  // of the same container. The inequality comparisons only check the positions, they do
327  // not check the container. Note that the "missing" comparison operators are added
328  // via the AddRelOps declaration.
329  bool operator==(const ConstRandomAccessIterator& rhs) const noexcept {
330  return (_container == rhs._container && _pos == rhs._pos);
331  }
332  bool operator<(const ConstRandomAccessIterator& rhs) const noexcept {
333  return (_pos < rhs._pos);
334  }
335 
336  // Dereference the iterators. Note that to obtain maximum efficiency (since this
337  // is expected to be done a lot) we do not check if _container and _pos are
338  // valid. If they are not, you can expect a SEGV or something similarly bad
339  // to happen.
340  typename Container::const_reference operator*() const { return (*_container)[_pos]; }
341  typename Container::const_pointer operator->() const { return &(*_container)[_pos]; }
342  typename Container::const_reference operator[](size_t i) const { return (*_container)[_pos+i]; }
343 
344  // Pointer arithmetic. For efficiency reasons we do not check if the resulting
345  // position is valid.
346  ConstRandomAccessIterator& operator++() noexcept { ++_pos; return *this; }
348  ConstRandomAccessIterator tmp(*this);
349  operator++();
350  return tmp;
351  }
352  ConstRandomAccessIterator& operator+=(typename Container::difference_type n) noexcept {
353  (n >= 0 ? _pos += size_t(n) : _pos -= size_t(-n));
354  return *this;
355  }
356  ConstRandomAccessIterator operator+(typename Container::difference_type n) const noexcept {
357  ConstRandomAccessIterator tmp(*this);
358  tmp += n;
359  return tmp;
360  }
361 
362  ConstRandomAccessIterator& operator--() noexcept { --_pos; return *this; }
364  ConstRandomAccessIterator tmp(_pos);
365  operator--();
366  return tmp;
367  }
368  ConstRandomAccessIterator& operator-=(typename Container::difference_type n) noexcept {
369  (n >= 0 ? _pos -= size_t(n) : _pos += size_t(-n));
370  return *this;
371  }
372  ConstRandomAccessIterator operator-(typename Container::difference_type n) const noexcept {
373  ConstRandomAccessIterator tmp(*this);
374  tmp -= n;
375  return tmp;
376  }
377  typename Container::difference_type operator-(const ConstRandomAccessIterator& rhs) const noexcept {
378  return typename Container::difference_type(_pos >= rhs._pos ? _pos - rhs._pos : -(rhs._pos - _pos));
379  }
380 
384  void swap(ConstRandomAccessIterator& b) noexcept {
385  if (this != &b) {
386  std::swap(_container, b._container);
387  std::swap(_pos, b._pos);
388  }
389  }
390 
391  private:
392  const Container* _container = nullptr;
393  size_t _pos = 0;
394  };
395 
396  template <typename Container>
397  ConstRandomAccessIterator<Container> operator+(typename Container::difference_type n, const ConstRandomAccessIterator<Container>& c) noexcept {
398  return (c + n);
399  }
400 
401 
416  template <typename Container>
418  : public kss::util::AddRelOps<CopyRandomAccessIterator<Container>>,
419  public std::iterator<
420  std::random_access_iterator_tag,
421  typename Container::value_type,
422  typename Container::difference_type,
423  std::shared_ptr<const typename Container::value_type>,
424  void >
425  {
426  public:
427  CopyRandomAccessIterator() = default;
428 
429  explicit CopyRandomAccessIterator(const Container& container, bool isEnd = false)
430  : _container(&container), _pos(isEnd ? container.size() : 0)
431  {}
432 
434  ~CopyRandomAccessIterator() noexcept = default;
435  CopyRandomAccessIterator& operator=(const CopyRandomAccessIterator&) = default;
436 
437  // Two iterators are considered equal if they are both pointing to the same position
438  // of the same container. The inequality comparisons only check the positions, they do
439  // not check the container. Note that the "missing" comparison operators are added
440  // via the AddRelOps declaration.
441  bool operator==(const CopyRandomAccessIterator& rhs) const noexcept {
442  return (_container == rhs._container && _pos == rhs._pos);
443  }
444  bool operator<(const CopyRandomAccessIterator& rhs) const noexcept {
445  return (_pos < rhs._pos);
446  }
447 
448  // Dereference the iterators. Note that to obtain maximum efficiency (since this
449  // is expected to be done a lot) we do not check if _container and _pos are
450  // valid. If they are not, you can expect a SEGV or something similarly bad
451  // to happen.
452  typename Container::value_type operator*() const { return (*_container)[_pos]; }
453  std::shared_ptr<const typename Container::value_type> operator->() const {
454  return std::shared_ptr<const typename Container::value_type>(new typename Container::value_type((*_container)[_pos]));
455  }
456  typename Container::value_type operator[](size_t i) const {
457  return (*_container)[_pos+i];
458  }
459 
460  // Pointer arithmetic. For efficiency reasons we do not check if the resulting
461  // position is valid.
462  CopyRandomAccessIterator& operator++() noexcept { ++_pos; return *this; }
464  CopyRandomAccessIterator tmp(*this);
465  operator++();
466  return tmp;
467  }
468  CopyRandomAccessIterator& operator+=(typename Container::difference_type n) noexcept {
469  (n >= 0 ? _pos += size_t(n) : _pos -= size_t(-n));
470  return *this;
471  }
472  CopyRandomAccessIterator operator+(typename Container::difference_type n) const noexcept {
473  CopyRandomAccessIterator tmp(*this);
474  tmp += n;
475  return tmp;
476  }
477 
478  CopyRandomAccessIterator& operator--() noexcept { --_pos; return *this; }
480  CopyRandomAccessIterator tmp(_pos);
481  operator--();
482  return tmp;
483  }
484  CopyRandomAccessIterator& operator-=(typename Container::difference_type n) noexcept {
485  (n >= 0 ? _pos -= size_t(n) : _pos += size_t(-n));
486  return *this;
487  }
488  CopyRandomAccessIterator operator-(typename Container::difference_type n) const noexcept {
489  CopyRandomAccessIterator tmp(*this);
490  tmp -= n;
491  return tmp;
492  }
493  typename Container::difference_type operator-(const CopyRandomAccessIterator& rhs) const noexcept {
494  return typename Container::difference_type(_pos >= rhs._pos ? _pos - rhs._pos : -(rhs._pos - _pos));
495  }
496 
500  void swap(CopyRandomAccessIterator& b) noexcept {
501  if (this != &b) {
502  std::swap(_container, b._container);
503  std::swap(_pos, b._pos);
504  }
505  }
506 
507  private:
508  const Container* _container = nullptr;
509  size_t _pos = 0;
510  };
511 
512  template <typename Container>
513  inline CopyRandomAccessIterator<Container> operator+(typename Container::difference_type n,
514  const CopyRandomAccessIterator<Container>& c) noexcept
515  {
516  return (c + n);
517  }
518 
519 }}}
520 
521 
528 namespace std {
529  template <typename Container, typename T>
532  {
533  a.swap(b);
534  }
535 
536  template <typename Container>
539  {
540  a.swap(b);
541  }
542 
543  template <typename Container>
546  {
547  a.swap(b);
548  }
549 
550  template <typename Container>
553  {
554  a.swap(b);
555  }
556 }
557 
558 #endif
ForwardIterator & operator=(ForwardIterator &&it) noexcept
Definition: iterator.hpp:95
CopyRandomAccessIterator & operator++() noexcept
Definition: iterator.hpp:462
ConstRandomAccessIterator operator+(typename Container::difference_type n) const noexcept
Definition: iterator.hpp:356
RandomAccessIterator(Container &container, bool isEnd=false)
Definition: iterator.hpp:213
ConstRandomAccessIterator & operator+=(typename Container::difference_type n) noexcept
Definition: iterator.hpp:352
void swap(kss::util::iterators::ForwardIterator< Container, T > &a, kss::util::iterators::ForwardIterator< Container, T > &b)
Definition: iterator.hpp:530
Base implementation of a forward iterator.
Definition: iterator.hpp:61
CopyRandomAccessIterator & operator-=(typename Container::difference_type n) noexcept
Definition: iterator.hpp:484
CopyRandomAccessIterator & operator+=(typename Container::difference_type n) noexcept
Definition: iterator.hpp:468
CopyRandomAccessIterator operator++(int) noexcept
Definition: iterator.hpp:463
void swap(ForwardIterator &b) noexcept
Definition: iterator.hpp:161
Container::const_pointer operator->() const
Definition: iterator.hpp:341
ConstRandomAccessIterator & operator++() noexcept
Definition: iterator.hpp:346
RandomAccessIterator & operator+=(typename Container::difference_type n) noexcept
Definition: iterator.hpp:251
const Container::reference operator[](size_t i) const
Definition: iterator.hpp:241
Container::reference operator[](size_t i)
Definition: iterator.hpp:240
std::shared_ptr< const typename Container::value_type > operator->() const
Definition: iterator.hpp:453
RandomAccessIterator operator++(int) noexcept
Definition: iterator.hpp:246
RandomAccessIterator & operator-=(typename Container::difference_type n) noexcept
Definition: iterator.hpp:262
Container::difference_type operator-(const CopyRandomAccessIterator &rhs) const noexcept
Definition: iterator.hpp:493
bool operator==(const ForwardIterator &it) const noexcept
Definition: iterator.hpp:109
void swap(ConstRandomAccessIterator &b) noexcept
Definition: iterator.hpp:384
void swap(CopyRandomAccessIterator &b) noexcept
Definition: iterator.hpp:500
ForwardIterator & operator=(const ForwardIterator &it)=default
Container::value_type operator[](size_t i) const
Definition: iterator.hpp:456
CopyRandomAccessIterator operator+(typename Container::difference_type n) const noexcept
Definition: iterator.hpp:472
Base implementation of a const version of a random access iterator.
Definition: iterator.hpp:305
ConstRandomAccessIterator operator-(typename Container::difference_type n) const noexcept
Definition: iterator.hpp:372
void swap(RandomAccessIterator &b) noexcept
Definition: iterator.hpp:278
Auto-generation of relational operators.
ConstRandomAccessIterator operator--(int) noexcept
Definition: iterator.hpp:363
const Container::reference operator*() const
Definition: iterator.hpp:237
RandomAccessIterator & operator++() noexcept
Definition: iterator.hpp:245
CopyRandomAccessIterator operator--(int) noexcept
Definition: iterator.hpp:479
ForwardIterator(ForwardIterator &&it)
Definition: iterator.hpp:88
RandomAccessIterator operator+(typename Container::difference_type n) const noexcept
Definition: iterator.hpp:255
bool operator!=(const ForwardIterator &it) const noexcept
Definition: iterator.hpp:114
Base implementation of a random access iterator that generate elements as needed. ...
Definition: iterator.hpp:417
ConstRandomAccessIterator & operator--() noexcept
Definition: iterator.hpp:362
Container::value_type operator*() const
Definition: iterator.hpp:452
bool operator<(const CopyRandomAccessIterator &rhs) const noexcept
Definition: iterator.hpp:444
Base implementation of a random access iterator.
Definition: iterator.hpp:201
ConstRandomAccessIterator & operator-=(typename Container::difference_type n) noexcept
Definition: iterator.hpp:368
bool operator<(const ConstRandomAccessIterator &rhs) const noexcept
Definition: iterator.hpp:332
CopyRandomAccessIterator operator-(typename Container::difference_type n) const noexcept
Definition: iterator.hpp:488
RandomAccessIterator operator-(typename Container::difference_type n) const noexcept
Definition: iterator.hpp:266
bool operator<(const RandomAccessIterator &rhs) const noexcept
Definition: iterator.hpp:228
ConstRandomAccessIterator operator++(int) noexcept
Definition: iterator.hpp:347
CopyRandomAccessIterator(const Container &container, bool isEnd=false)
Definition: iterator.hpp:429
Container::const_reference operator*() const
Definition: iterator.hpp:340
Container::difference_type operator-(const ConstRandomAccessIterator &rhs) const noexcept
Definition: iterator.hpp:377
Container::difference_type operator-(const RandomAccessIterator &rhs) const noexcept
Definition: iterator.hpp:271
const Container::pointer operator->() const
Definition: iterator.hpp:239
CopyRandomAccessIterator & operator--() noexcept
Definition: iterator.hpp:478
Container::const_reference operator[](size_t i) const
Definition: iterator.hpp:342
ConstRandomAccessIterator(const Container &container, bool isEnd=false)
Definition: iterator.hpp:317
Add the operators !=, &lt;=, &gt; and &gt;= assuming the existance of == and &lt;.
Definition: add_rel_ops.hpp:31
RandomAccessIterator< Container > operator+(typename Container::difference_type n, const RandomAccessIterator< Container > &c) noexcept
Definition: iterator.hpp:291
RandomAccessIterator & operator--() noexcept
Definition: iterator.hpp:261