Multi-dimensional view of a one-dimensional object

Question

Sometimes, we create a one-dimensional object, but want to access it in a multi-dimensional way. For example, you can access an int[8] array object in a 2x2x2 way. So, I made a multi_view class template to make this easy. Any comments are welcome. Original code can be found here and documentation here.

template <typename Iterator>
class multi_view {
public:
  static constexpr std::size_t max_dim = 10;

dimensions.
  template <typename... Ts>
  multi_view(Iterator base, Ts... extents)
      : base_(base) {
    constexpr auto n = sizeof...(extents);
    static_assert(0 < n && n <= max_dim, "");
    auto init_list = { extents... };
    std::copy(init_list.begin(), init_list.end(), steps_);
    auto i = n - 1;
    std::size_t acc = 1;
    do {
      acc *= std::exchange(steps_[i], acc);
    }
    while (i-- > 0);
    assert(acc);
    num_elements_ = acc;
  }

  template <typename... Ts>
  auto begin() const {
    return base_;
  }

  template <typename... Ts>
  auto begin(Ts... indices) const {
    auto idxes = std::begin({ indices... });
    std::size_t offset = 0;
    for (std::size_t i = 0; i < sizeof...(indices) && steps_[i]; ++i) {
      assert(idxes[i] >= 0);
      offset += idxes[i] * steps_[i];
    }
    return (base_ + offset);
  }

  template <typename... Ts>
  auto end() const {
    return base_ + num_elements_;
  }

  template <typename... Ts>
  auto end(Ts... indices) const {
    return end_impl(std::make_index_sequence<sizeof...(Ts) - 1>{}, indices...);
  }

  template <typename... Ts>
  auto operator ()(Ts... indices) const {
    return *begin(indices...);
  }

private:
  template <std::size_t... seq, typename... Ts>
  auto end_impl(std::index_sequence<seq...>, Ts... indices) const {
    auto tup = std::tie(indices...);
    return begin(std::get<seq>(tup)..., std::get<sizeof...(Ts) - 1>(tup) + 1);
  }

  Iterator base_;
  std::size_t steps_[max_dim + 1]{};
  std::size_t num_elements_ = 0;
};

template <typename Iterator, typename... Ts>
auto make_multi_view(Iterator base, Ts... extents) {
  return multi_view<Iterator>(base, extents...);
}

A usage example:

std::vector<int> vec{ 1, 2, 3, 4 };
auto view2x2 = make_multi_view(vec.begin(), 2, 2);
assert(view2x2(0, 0), 1);
assert(view2x2(0, 1), 2);
assert(view2x2(1, 0), 3);
assert(view2x2(1, 1), 4);
assert(view2x2(), 1);
assert(view2x2(1), 3);
assert(std::distance(view2x2.begin(), view2x2.end()), 4);
assert(std::distance(view2x2.begin(1), view2x2.end(1), 2);
assert(std::distance(view2x2.begin(1, 1), view2x2.end(1, 1), 1);

Enter the proposed std::view. You might find it interesting :) — Morwenn
– Morwenn, Commented Jan 27, 2016 at 16:19
@Morwenn std::view seems static. multi_view is dynamic. You can specify the dimensions at runtime. — Lingxi
– Lingxi, Commented Jan 27, 2016 at 16:24
It's ony optionally static. If you don't specify the dimensions at compile time, you pass them to the constructor at runtime. — Morwenn
– Morwenn, Commented Jan 27, 2016 at 16:27
@Morwenn Guess I will have to read the proposal through. I don't know std::view yet. Thanks for the mention :) — Lingxi
– Lingxi, Commented Jan 27, 2016 at 16:30
From C++23 onwards, std::mdspan may be a good replacement for this code, if your underlying iterator is contiguous. BTW, where is the two-argument assert() function defined? — Toby Speight
– Toby Speight, Commented Sep 15, 2024 at 8:04

Toby Speight · Accepted Answer · 2024-09-16 14:12:16Z

We're missing definitions of std::size_t,std::copy, std::exchange, assert, std::begin, std::make_index_sequence, std::index_sequence, std::tie and std::get.

Solve that using

#include <cassert>
#include <iterator>
#include <tuple>
#include <utility>
#include <vector>

We have a syntax error here, which makes me worry that this code has not been built, never mind tested:

dimensions.
  template <typename... Ts>
  multi_view(Iterator base, Ts... extents)

The test code is also uncompilable, due to missing ) and its need of a two-argument assert(). This can be changed to something that builds and runs, but I'd have more confidence if it worked first time.

I don't really like this interface:

    assert(view2x2(1) == 3);

It would be more useful if single-level indexing returned a multi_view of the {3, 4} row, rather than its first element.

Looking into the implementation, I see this assert:

constexpr auto n = sizeof...(extents);
static_assert(0 < n && n <= max_dim, "");

I think it's better use use the form of static_assert() with no message than to provide an empty message.

But better than that would be to remove the arbitrary limit, perhaps by changing steps_ to be a std::vector instead of an array (a more modern alternative might be to make the dimensionality part of the type, and provide a deduction guide to help).

Then we could initialise steps_ directly and simplify the whole constructor:

    template <typename... Ts>
    multi_view(Iterator base, Ts... extents)
        : base_{base},
          steps_{extents...},
          num_elements_{std::accumulate(steps_.begin(), steps_.end(), 1uz, std::multiplies<>{})}
    {
        std::array<std::size_t, sizeof...(extents) + 1> ini{{ extents..., 1 }};
        std::partial_sum(ini.rbegin(), ini.rend()-1, steps_.rbegin(), std::multiplies<>{});
    }

This is confusing:

  auto begin(Ts... indices) const {
    auto idxes = std::begin({ indices... });

indices and idxes can be tricky to talk about distinctly when discussing this code (and actually sound alike in my head).

It's worrying that if supplied with too many arguments we just ignore the excess rather than throwing an exception or otherwise failing. We ought to be able to fail at build time with a static_assert().

It's surprising that the const versions of begin() and end() return mutable iterators. Normally these functions (and cbegin() and cend()) return iterators to const elements, and only the non-const functions return iterators to mutable elements.

We could easily provide the set of six rbegin() and rend() functions to return reverse iterators.

Stack Exchange Network

Multi-dimensional view of a one-dimensional object

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

Multi-dimensional view of a one-dimensional object

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions