Hi 我是 eop 。 畢業於台灣大學資訊工程系(NTU CSIE), 現在是 Sifive 的 Compiler Engineer。 (Ex-Skymizer Compiler Engineer) 你可以在 eopxd.com 找到我! 我會發布一些對技術的整理、閱讀或觀影的心得或是生活的感悟。 如果覺得這些創作有價值,歡迎支持我。 希望人生能一直過得有趣又有挑戰。
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:
- To iterate lexicographically from
(n, c, h, w)
to(maxN, maxC, maxH, maxW)
- 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.
Original link: eopXD
喜欢我的文章吗?
别忘了给点支持与赞赏,让我知道创作的路上有你陪伴。
发布评论…