Merge bitcoin/bitcoin#29275: refactor: Fix prevector iterator concept issues

fad74bbbd0ab4425573f182ebde1b31a99e80547 refactor: Mark prevector iterator with std::contiguous_iterator_tag (MarcoFalke)
fab8a01048fc6cfcee7e89884a5af31385189c63 refactor: Fix binary operator+ for prevector iterators (MarcoFalke)
fa44a60b2bb5cb91bc411e5b625fc81bd84befff refactor: Fix constness for prevector iterators (MarcoFalke)
facaa66b49ef7eeefe1d57c1bfc1bbe5b3011661 refactor: Add missing default constructor to prevector iterators (MarcoFalke)

Pull request description:

  Currently prevector iterators have many issues:

  * Forward iterators (and stronger) must be default constructible (https://eel.is/c++draft/forward.iterators#1.2). Otherwise, some functions can not be instantiated, like `std::minmax_element`.
  * Various `const` issues with random access iterators. For example, a `const iterator` is different from a `const_iterator`, because the first one holds a mutable reference and must also return it without `const`. Also, `operator+` must be callable regardless of the iterator object's `const`-ness.
  * When adding an offset to random access iterators, both `x+n` and `n+x` must be specified, see https://eel.is/c++draft/random.access.iterators#tab:randomaccessiterator

  Fix all issues.

  Also, upgrade the `std::random_access_iterator_tag` (C++17) to `std::contiguous_iterator_tag` (C++20)

ACKs for top commit:
  TheCharlatan:
    ACK fad74bbbd0ab4425573f182ebde1b31a99e80547
  stickies-v:
    ACK fad74bbbd0ab4425573f182ebde1b31a99e80547
  willcl-ark:
    ACK fad74bbbd0ab4425573f182ebde1b31a99e80547

Tree-SHA512: b1ca778a31602af94b323b8feaf993833ec78be09f1d438a68335485a4ba97f52125fdd977ffb9541b89f8d45be0105076aa07b5726936133519aae832556e0b

1 files changed, 21 insertions, 16 deletions

diff --git a/src/prevector.h b/src/prevector.h
index bcab1ff00c..4776db789b 100644
--- a/src/prevector.h
+++ b/src/prevector.h
@@ -47,26 +47,28 @@ public:
     typedef const value_type* const_pointer;
 
     class iterator {
-        T* ptr;
+        T* ptr{};
     public:
         typedef Diff difference_type;
         typedef T value_type;
         typedef T* pointer;
         typedef T& reference;
-        typedef std::random_access_iterator_tag iterator_category;
+        using element_type = T;
+        using iterator_category = std::contiguous_iterator_tag;
+        iterator() = default;
         iterator(T* ptr_) : ptr(ptr_) {}
         T& operator*() const { return *ptr; }
         T* operator->() const { return ptr; }
-        T& operator[](size_type pos) { return ptr[pos]; }
-        const T& operator[](size_type pos) const { return ptr[pos]; }
+        T& operator[](size_type pos) const { return ptr[pos]; }
         iterator& operator++() { ptr++; return *this; }
         iterator& operator--() { ptr--; return *this; }
         iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
         iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
         difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
-        iterator operator+(size_type n) { return iterator(ptr + n); }
+        iterator operator+(size_type n) const { return iterator(ptr + n); }
+        iterator friend operator+(size_type n, iterator x) { return x + n; }
         iterator& operator+=(size_type n) { ptr += n; return *this; }
-        iterator operator-(size_type n) { return iterator(ptr - n); }
+        iterator operator-(size_type n) const { return iterator(ptr - n); }
         iterator& operator-=(size_type n) { ptr -= n; return *this; }
         bool operator==(iterator x) const { return ptr == x.ptr; }
         bool operator!=(iterator x) const { return ptr != x.ptr; }
@@ -77,18 +79,17 @@ public:
     };
 
     class reverse_iterator {
-        T* ptr;
+        T* ptr{};
     public:
         typedef Diff difference_type;
         typedef T value_type;
         typedef T* pointer;
         typedef T& reference;
         typedef std::bidirectional_iterator_tag iterator_category;
+        reverse_iterator() = default;
         reverse_iterator(T* ptr_) : ptr(ptr_) {}
-        T& operator*() { return *ptr; }
-        const T& operator*() const { return *ptr; }
-        T* operator->() { return ptr; }
-        const T* operator->() const { return ptr; }
+        T& operator*() const { return *ptr; }
+        T* operator->() const { return ptr; }
         reverse_iterator& operator--() { ptr++; return *this; }
         reverse_iterator& operator++() { ptr--; return *this; }
         reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; }
@@ -98,13 +99,15 @@ public:
     };
 
     class const_iterator {
-        const T* ptr;
+        const T* ptr{};
     public:
         typedef Diff difference_type;
         typedef const T value_type;
         typedef const T* pointer;
         typedef const T& reference;
-        typedef std::random_access_iterator_tag iterator_category;
+        using element_type = const T;
+        using iterator_category = std::contiguous_iterator_tag;
+        const_iterator() = default;
         const_iterator(const T* ptr_) : ptr(ptr_) {}
         const_iterator(iterator x) : ptr(&(*x)) {}
         const T& operator*() const { return *ptr; }
@@ -115,9 +118,10 @@ public:
         const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
         const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
         difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
-        const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
+        const_iterator operator+(size_type n) const { return const_iterator(ptr + n); }
+        const_iterator friend operator+(size_type n, const_iterator x) { return x + n; }
         const_iterator& operator+=(size_type n) { ptr += n; return *this; }
-        const_iterator operator-(size_type n) { return const_iterator(ptr - n); }
+        const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
         const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
         bool operator==(const_iterator x) const { return ptr == x.ptr; }
         bool operator!=(const_iterator x) const { return ptr != x.ptr; }
@@ -128,13 +132,14 @@ public:
     };
 
     class const_reverse_iterator {
-        const T* ptr;
+        const T* ptr{};
     public:
         typedef Diff difference_type;
         typedef const T value_type;
         typedef const T* pointer;
         typedef const T& reference;
         typedef std::bidirectional_iterator_tag iterator_category;
+        const_reverse_iterator() = default;
         const_reverse_iterator(const T* ptr_) : ptr(ptr_) {}
         const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {}
         const T& operator*() const { return *ptr; }