Recursive template metaprogramming (Part III)

On the previous part, I went through some practice on abstractions when writing recursions.

This part would be the last part of the current topic. I would implement MergeSort with recursive template metaprogramming.

Continue reading “Recursive template metaprogramming (Part III)”

Value Category(值類別)- 1 / 2

這筆記從 C 原本對 lvalue 與 rvalue 的使用與,再到 C++ 11 標準時使用的 lvalue 與 rvalue 。我覺得 Value Category 是入門 Modern C++ 需要釐清的重要觀念。了解值類別也可以幫助了解編譯器與物件生命週期中的細節,在寫扣上也會有些幫助。

首先要記得的是 lvalue 和 rvalue 這種東西不是一種 C++ 語言中的 feature ,它們是 expression ,表達出特定的 semantic (語意),這樣的語意除了 C/C++ 之外也可以套用在其他程式語言上。

為了方便閱讀,分成兩個部分。
第一部分:Back in C & Temporary Materialization Conversion
第二部分:Modern C++ Value Category

Continue reading “Value Category(值類別)- 1 / 2”

Value Category(值類別)- 2 / 2

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

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

Continue reading “Value Category(值類別)- 2 / 2”

Cartesian Coordinate Iterator

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 來支持我繼續創作更多內容。因為做自己喜歡的事而得到報酬,是再好不過的事了。(街口支付)