A Simple Multi-dimensional Array

OCTOBER 27, 2019 | C++, UTILITY, ARRAY

Back when I was doing image-processing work with OpenCV, I had first-hand experience with how it accesses its data. While OpenCV is a heavily optimized library for image processing tasks, it does some things a bit strangely, and I thought I could do a bit better.

I wanted to make it a generic container with template parameters for type and dimensionality. I also wanted to have a large variety of composable array manipulation functions while never copying the data.

It can be found here on my GitHub:

A lot of the inner workings and design decisions is detailed in the documentation overview.

Data Access

An instance of the class "NArray<T, N>" will have a pointer, an array of integers for each dimension's size, and an array of integers for each dimension's stride. If you don't already know, a "stride" is simply how far to go in the array to reach the next index along a particular dimension. A basic multi-dimensional array will inherently know its stride based on its dimensions, but being able to manipulate the stride allows for a lot of different ways to read the data.

• want to skip every other element? half the dimension's size and double its stride
• want to reverse the order? move the pointer and reverse the stride
• want to access just a sub-range? move the pointer and reduce the size
• want to transpose a two-dimensional array? just swap the dimensions around (both size and stride)

These operations, along with more complicated like reshaping or windowing, can be chained as well to allow any number of access patterns. And of course, these operations extend to multiple dimensions.

This is not a novel idea. OpenCV's Mat and Boost's multi_array classes both keep track of size and stride information and use it for certain operations, but they are much more limited in my experience.

Shared Data

A key decision was to keep the data shared between the original array and transformations. Boost uses separate "view" classes for transformations and while it can be more performant, but I find the distinction annoying and chose to keep the data shared like OpenCV does.

Keep it Simple

I had originally added a lot of extra functions to the library that did typical image-processing stuff like filtering. However, I later acknowledged that those operations weren't going to be anywhere near as good as OpenCV or any other image-processing library. So I trimmed it down to just the array access and manipulation classes and perfected that.

Because of this, I was able to add many more convenience functions and make tests for most of the functions. I've looked at different use-cases, analyzed performance, and added a lot more documentation than any of my other programming projects. This is probably my most complete and polished library.

I used this library in many of my other projects whenever I need to do any non-trivial array transformations. I've also used it to make Sudoku and Picross solver.