Category: Tech

為了方便閱讀，分成兩個部分。可以往上翻閱來知道為什麼要這樣演進。
第一部分：Back in C & Temporary Materialization Conversion
第二部分：Modern C++ Value Category

上一部份停在 Temporary Materialization Conversion (TMC)。首先會從 reference binding 講起，再進入 Modern C++ 與例子。

As I start getting familiar with STL, it came to me that rather than just simply using the library, I should further more practice on writing my own libraries. It is a practice of the process to formulate my requirement, extract them into fundamentals, and lastly provide clear interface to users. This practice also helps me get more familiar with the language itself.

This post is a practice on writing a Cartesian Coordinate iterator using C++. I would explain my interfaces, you can check out the full implementation on my Github.

Before starting I would like to thank poyenc for your review and helpful comments. <(_ _)>

Requirement / Motivation

It is important know where the problems come from, to formulate them and sort out the requirements. I was recently dealing with coordinate mapping and iterating through multidimensional data.

Therefore I came out with 2 requirements:

1. To iterate lexicographically from (n, c, h, w) to (maxN, maxC, maxH, maxW)
2. During iteration, I can access the current coordinate or offset

Container vs. Iterator

Containers are abstraction of data structures with collection of items. Iterator gives access to a single element inside a container.

So starting from constructor of the iterator, it should allow the user to give whatever container as long as the container is sequential and of the correct datatype.

Declaring shape of the data (constructor)

Following the requirements above, the maximum coordinate shall be set. The constructor of CartesianCoordinate will first take maximum coordinate. The following is the revised-implementation.

CartesianCoordinate() = delete;
CartesianCoordinate(std::initializer_list<T> maxAxis)
  : m_maxAxis(maxAxis)
{
  static_assert(std::is_unsigned<T>::value && std::is_integral<T>::value, "T should be unsigned integral");
  initializeVolume(maxAxis);
}
template <typename ContainerT>
CartesianCoordinate(ContainerT maxAxis)
  : m_maxAxis(maxAxis)
{
  static_assert(std::is_unsigned<typename ContainerT::value_type>::value &&
                std::is_integral<typename ContainerT::value_type>::value,
                "ContainerT should be of unsigned integral");
  static_assert(std::is_same<T, typename ContainerT::value_type>::value, "ContainerT value type should match T");
  initializeVolume(maxAxis);
}

Further more this is a C++11 implementation, so I have to check datatype of the input containers. For C++14 or above there is std::integer_sequence or more for compile time integer sequences.

Underlying iterator

For iteration over coordinates it is rather simple, possible use-case includes functionalities like ++ , -- , += value , -= value . A former iterator also needs to implement pointer, reference, and operator member functions.

Iteration over coordinate (requirement 1)

The data structure abstracts coordinate as underlying elements. It gives interface like std::vector , letting users take begin , end , and at .

iterator begin() const { return iterator(0); }
iterator end() const { return iterator(m_maxOffset); }
iterator at(std::initializer_list<T> startAxis) const
{
  assert(startAxis.size() == m_maxAxis.size() && "argument should be match the dimension initialized");
  offset_type currOffset = calcOffset(m_maxAxis.size(), 
  std::begin(startAxis));
  return iterator(currOffset);
}
template <typename ContainerT>
iterator at(ContainerT startAxis) const
{
  static_assert(std::is_same<T, typename ContainerT::value_type>::value, "ContainerT value type should match T");
  assert(startAxis.size() == m_maxAxis.size() && "argument should be match the dimension initialized");
  offset_type currOffset = calcOffset(m_maxAxis.size(), 
  std::begin(startAxis));
  return iterator(currOffset);
}

Access during iterator (requirement 2)

User may want to know the coordinate or offset of the current iteration. The library shall give the user maximum ability to customize. Therefore, coordOf takes an iterator (OutputIterator), so the user is able to use any sequential container it desires.

offset_type offsetOf(iterator it) const { return it(); }
template <typename OutputIterator>
void coordOf(iterator it, OutputIterator out) const
{
  offset_type temp = it();
  typename container_type::size_type maxDim = m_maxAxis.size();
  for (typename container_type::size_type idx = 0; idx < maxDim; ++idx) {
    *out++ = temp / m_volume[idx];
    temp = temp % m_volume[idx];
  }
}

Use-case: for-loop

// from (0, 0, 0, 0) to (1, 1, 2, 2) 
CartesianCoordinate<unsigned> shape({2, 2, 3, 3}); 
for (decltype(shape)::iterator it = shape.begin(); it != shape.end(); ++it);
CartesianCoordinate<unsigned> coord({1, 1, 1, 1});
for (auto elem : coord);// from coord to shape.end()

Use-case: integration with STL

auto result =
    std::accumulate(std::begin(coord), std::end(coord), 0, [](const unsigned& a, const unsigned& b) { return a + b; });

Use-case: offset / coordinate

for (decltype(shape)::iterator it = shape.at({1, 1, 1, 1}); it != shape.end(); ++it) {
  std::vector<unsigned int> getCoord;
  shape.coordOf(it, std::back_inserter(getCoord));
  decltype(shape)::offset_type currOffset = shape.offsetOf(it);
}

Github

You can check out the full implementation on my Github.

如果你覺得有收穫，可以用 30 NTD 來支持我繼續創作更多內容。因為做自己喜歡的事而得到報酬，是再好不過的事了。（街口支付）

今天受 poyenc 開示關於物件的抽象化以至於真正的 type safe ，撰文以誌之。