Lazy evaluation read-only std::vector (tools/virtual_vector.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-20 12:05:28+09:00
• Include: #include "tools/virtual_vector.hpp"

It is almost same as const std::vector{f(0), f(1), ..., f(n - 1)}, but evaluate values when needed. Hence, the time taken to construct it can be $o(n)$.

License

• CC0

Author

• anqooqie

Constructor

template <typename F>
virtual_vector<F> v(std::size_t n, F f);

Constraints

• $n \geq 0$
• $f$ takes std::size_t and returns const T& where T is any type.

Time Complexity

• Same as the time taken to copy f

Methods based on const std::vector<T>

virtual_vector<F>::const_iterator v.begin();
virtual_vector<F>::const_iterator v.end();
virtual_vector<F>::const_iterator v.cbegin();
virtual_vector<F>::const_iterator v.cend();
virtual_vector<F>::const_reverse_iterator v.rbegin();
virtual_vector<F>::const_reverse_iterator v.rend();
virtual_vector<F>::const_reverse_iterator v.crbegin();
virtual_vector<F>::const_reverse_iterator v.crend();

std::size_t v.size();
bool v.empty();

const T& v.operator[](std::size_t i);
const T& v.at(std::size_t i);
const T& v.front();
const T& v.back();

bool operator==(virtual_vector<F> v, virtual_vector<G> u);
bool operator!=(virtual_vector<F> v, virtual_vector<G> u);
bool operator<(virtual_vector<F> v, virtual_vector<G> u);
bool operator<=(virtual_vector<F> v, virtual_vector<G> u);
bool operator>(virtual_vector<F> v, virtual_vector<G> u);
bool operator>=(virtual_vector<F> v, virtual_vector<G> u);

They are methods based on const std::vector<T>.

Constraints

• Same as ones of const std::vector<T>

Time Complexity

• Same as ones of const std::vector<T>

Required by

• Bell numbers (tools/bell.hpp)
• Signed Stirling numbers of the first kind (tools/stirling_1st.hpp)
• Stirling numbers of the second kind (tools/stirling_2nd.hpp)
• Twelvefold way (tools/twelvefold_way.hpp)

Verified with

• tests/bell/all.test.cpp
• tests/bell/consistent.test.cpp
• tests/bell/diagonal.test.cpp
• tests/bell/fixed_n.test.cpp
• tests/stirling_1st/consistent.test.cpp
• tests/stirling_1st/fixed_k.test.cpp
• tests/stirling_1st/fixed_n.test.cpp
• tests/stirling_2nd/all.test.cpp
• tests/stirling_2nd/consistent.test.cpp
• tests/stirling_2nd/fixed_k.test.cpp
• tests/stirling_2nd/fixed_n.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_at_least_1.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_at_most_1.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_unrestricted.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_at_least_1.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_at_most_1.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_unrestricted.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_at_least_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_at_most_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_unrestricted.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_at_least_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_at_most_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_unrestricted.test.cpp
• tests/virtual_vector.test.cpp

Code

#ifndef TOOLS_VIRTUAL_VECTOR_HPP
#define TOOLS_VIRTUAL_VECTOR_HPP

#include <cstddef>
#include <type_traits>
#include <memory>
#include <iterator>
#include <cassert>
#include <algorithm>

namespace tools {
  template <typename F>
  class virtual_vector {
  public:
    using size_type = ::std::size_t;

    class iterator {
      const virtual_vector<F> *m_parent;
      size_type m_i;

    public:
      using reference = decltype(::std::declval<F>()(::std::declval<size_type>()));
      using value_type = ::std::remove_const_t<::std::remove_reference_t<reference>>;
      using difference_type = ::std::ptrdiff_t;
      using pointer = const value_type*;
      using iterator_category = ::std::random_access_iterator_tag;

      iterator() = default;
      iterator(const virtual_vector<F> * const parent, const size_type i) : m_parent(parent), m_i(i) {
      }

      reference operator*() const {
        return (*this->m_parent)[this->m_i];
      }
      pointer operator->() const {
        return &(*(*this));
      }

      iterator& operator++() {
        ++this->m_i;
        return *this;
      }
      iterator operator++(int) {
        const auto self = *this;
        ++*this;
        return self;
      }
      iterator& operator--() {
        --this->m_i;
        return *this;
      }
      iterator operator--(int) {
        const auto self = *this;
        --*this;
        return self;
      }
      iterator& operator+=(const difference_type n) {
        this->m_i += n;
        return *this;
      }
      iterator& operator-=(const difference_type n) {
        this->m_i -= n;
        return *this;
      }
      friend iterator operator+(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i + n);
      }
      friend iterator operator+(const difference_type n, const iterator self) {
        return self + n;
      }
      friend iterator operator-(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i - n);
      }
      friend difference_type operator-(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return static_cast<difference_type>(lhs.m_i) - static_cast<difference_type>(rhs.m_i);
      }
      reference operator[](const difference_type n) const {
        return *(*this + n);
      }

      friend bool operator==(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i == rhs.m_i;
      }
      friend bool operator!=(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i != rhs.m_i;
      }
      friend bool operator<(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i < rhs.m_i;
      }
      friend bool operator<=(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i <= rhs.m_i;
      }
      friend bool operator>(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i > rhs.m_i;
      }
      friend bool operator>=(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i >= rhs.m_i;
      }
    };

    using const_reference = decltype(::std::declval<F>()(::std::declval<size_type>()));
    using value_type = ::std::remove_const_t<::std::remove_reference_t<const_reference>>;
    using reference = value_type&;
    using const_iterator = iterator;
    using difference_type = ::std::ptrdiff_t;
    using allocator_type = ::std::allocator<value_type>;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using reverse_iterator = ::std::reverse_iterator<iterator>;
    using const_reverse_iterator = ::std::reverse_iterator<const_iterator>;

  private:
    size_type m_size;
    F m_selector;

  public:
    virtual_vector() = default;
    virtual_vector(const size_type n, const F& selector) : m_size(n), m_selector(selector) {
    }

    iterator begin() noexcept { return iterator(this, 0); }
    const_iterator begin() const noexcept { return const_iterator(this, 0); }
    const_iterator cbegin() const noexcept { return const_iterator(this, 0); }
    iterator end() noexcept { return iterator(this, this->size()); }
    const_iterator end() const noexcept { return const_iterator(this, this->size()); }
    const_iterator cend() const noexcept { return const_iterator(this, this->size()); }
    reverse_iterator rbegin() noexcept { return ::std::make_reverse_iterator(this->end()); }
    const_reverse_iterator rbegin() const noexcept { return ::std::make_reverse_iterator(this->end()); }
    const_reverse_iterator crbegin() const noexcept { return ::std::make_reverse_iterator(this->cend()); }
    reverse_iterator rend() noexcept { return ::std::make_reverse_iterator(this->begin()); }
    const_reverse_iterator rend() const noexcept { return ::std::make_reverse_iterator(this->begin()); }
    const_reverse_iterator crend() const noexcept { return ::std::make_reverse_iterator(this->cbegin()); }

    size_type size() const noexcept { return this->m_size; }
    bool empty() const noexcept { return this->size() == 0; }

    const_reference operator[](const size_type n) const { assert(n < this->size()); return this->m_selector(n); }
    const_reference at(const size_type n) const { return (*this)[n]; }
    const_reference front() const { return *this->begin(); }
    const_reference back() const { return *this->rbegin(); }

    template <typename G>
    friend bool operator==(const virtual_vector<F>& x, const virtual_vector<G>& y) { return ::std::equal(x.begin(), x.end(), y.begin(), y.end()); }
    template <typename G>
    friend bool operator!=(const virtual_vector<F>& x, const virtual_vector<G>& y) { return !(x == y); }
    template <typename G>
    friend bool operator<(const virtual_vector<F>& x, const virtual_vector<G>& y) { return ::std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
    template <typename G>
    friend bool operator<=(const virtual_vector<F>& x, const virtual_vector<G>& y) { return !(x > y); }
    template <typename G>
    friend bool operator>(const virtual_vector<F>& x, const virtual_vector<G>& y) { return y < x; }
    template <typename G>
    friend bool operator>=(const virtual_vector<F>& x, const virtual_vector<G>& y) { return !(x < y); }
  };
}

#endif

#line 1 "tools/virtual_vector.hpp"



#include <cstddef>
#include <type_traits>
#include <memory>
#include <iterator>
#include <cassert>
#include <algorithm>

namespace tools {
  template <typename F>
  class virtual_vector {
  public:
    using size_type = ::std::size_t;

    class iterator {
      const virtual_vector<F> *m_parent;
      size_type m_i;

    public:
      using reference = decltype(::std::declval<F>()(::std::declval<size_type>()));
      using value_type = ::std::remove_const_t<::std::remove_reference_t<reference>>;
      using difference_type = ::std::ptrdiff_t;
      using pointer = const value_type*;
      using iterator_category = ::std::random_access_iterator_tag;

      iterator() = default;
      iterator(const virtual_vector<F> * const parent, const size_type i) : m_parent(parent), m_i(i) {
      }

      reference operator*() const {
        return (*this->m_parent)[this->m_i];
      }
      pointer operator->() const {
        return &(*(*this));
      }

      iterator& operator++() {
        ++this->m_i;
        return *this;
      }
      iterator operator++(int) {
        const auto self = *this;
        ++*this;
        return self;
      }
      iterator& operator--() {
        --this->m_i;
        return *this;
      }
      iterator operator--(int) {
        const auto self = *this;
        --*this;
        return self;
      }
      iterator& operator+=(const difference_type n) {
        this->m_i += n;
        return *this;
      }
      iterator& operator-=(const difference_type n) {
        this->m_i -= n;
        return *this;
      }
      friend iterator operator+(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i + n);
      }
      friend iterator operator+(const difference_type n, const iterator self) {
        return self + n;
      }
      friend iterator operator-(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i - n);
      }
      friend difference_type operator-(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return static_cast<difference_type>(lhs.m_i) - static_cast<difference_type>(rhs.m_i);
      }
      reference operator[](const difference_type n) const {
        return *(*this + n);
      }

      friend bool operator==(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i == rhs.m_i;
      }
      friend bool operator!=(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i != rhs.m_i;
      }
      friend bool operator<(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i < rhs.m_i;
      }
      friend bool operator<=(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i <= rhs.m_i;
      }
      friend bool operator>(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i > rhs.m_i;
      }
      friend bool operator>=(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i >= rhs.m_i;
      }
    };

    using const_reference = decltype(::std::declval<F>()(::std::declval<size_type>()));
    using value_type = ::std::remove_const_t<::std::remove_reference_t<const_reference>>;
    using reference = value_type&;
    using const_iterator = iterator;
    using difference_type = ::std::ptrdiff_t;
    using allocator_type = ::std::allocator<value_type>;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using reverse_iterator = ::std::reverse_iterator<iterator>;
    using const_reverse_iterator = ::std::reverse_iterator<const_iterator>;

  private:
    size_type m_size;
    F m_selector;

  public:
    virtual_vector() = default;
    virtual_vector(const size_type n, const F& selector) : m_size(n), m_selector(selector) {
    }

    iterator begin() noexcept { return iterator(this, 0); }
    const_iterator begin() const noexcept { return const_iterator(this, 0); }
    const_iterator cbegin() const noexcept { return const_iterator(this, 0); }
    iterator end() noexcept { return iterator(this, this->size()); }
    const_iterator end() const noexcept { return const_iterator(this, this->size()); }
    const_iterator cend() const noexcept { return const_iterator(this, this->size()); }
    reverse_iterator rbegin() noexcept { return ::std::make_reverse_iterator(this->end()); }
    const_reverse_iterator rbegin() const noexcept { return ::std::make_reverse_iterator(this->end()); }
    const_reverse_iterator crbegin() const noexcept { return ::std::make_reverse_iterator(this->cend()); }
    reverse_iterator rend() noexcept { return ::std::make_reverse_iterator(this->begin()); }
    const_reverse_iterator rend() const noexcept { return ::std::make_reverse_iterator(this->begin()); }
    const_reverse_iterator crend() const noexcept { return ::std::make_reverse_iterator(this->cbegin()); }

    size_type size() const noexcept { return this->m_size; }
    bool empty() const noexcept { return this->size() == 0; }

    const_reference operator[](const size_type n) const { assert(n < this->size()); return this->m_selector(n); }
    const_reference at(const size_type n) const { return (*this)[n]; }
    const_reference front() const { return *this->begin(); }
    const_reference back() const { return *this->rbegin(); }

    template <typename G>
    friend bool operator==(const virtual_vector<F>& x, const virtual_vector<G>& y) { return ::std::equal(x.begin(), x.end(), y.begin(), y.end()); }
    template <typename G>
    friend bool operator!=(const virtual_vector<F>& x, const virtual_vector<G>& y) { return !(x == y); }
    template <typename G>
    friend bool operator<(const virtual_vector<F>& x, const virtual_vector<G>& y) { return ::std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
    template <typename G>
    friend bool operator<=(const virtual_vector<F>& x, const virtual_vector<G>& y) { return !(x > y); }
    template <typename G>
    friend bool operator>(const virtual_vector<F>& x, const virtual_vector<G>& y) { return y < x; }
    template <typename G>
    friend bool operator>=(const virtual_vector<F>& x, const virtual_vector<G>& y) { return !(x < y); }
  };
}

Back to top page