Tag Archives: C++

Dynamic stride in a matrix (1d mimics 2d)

Hey, so this is one of those posts I’m creating so I can link it to beginners when they ask about 2D arrays and creating arrays in C++ with a user defined size at runtime. C++, being a child of C, is very picky about how and when you ask for memory to use for storage. This int arr[10] creates a “c-style” static array on the stack. The size must be known at compile time and it can not be changed at runtime. If you try to do
std::cin >> size;
int arr[size];
you should get an error. Unfortunately GCC and CLang both ship with VLA (variable length arrays) turned on by default so unless you add a specific compiler flag the above code will compile. But, to the topic at hand. If you want to create an array using size determined at runtime you have to either use an stl container like std::vector (which is the smart thing to do 99% of the time) or you have to use new and delete to ask for some memory on the heap for your array and then to free that allocation when you’re done with it. Which is pretty straight forward:

int size = 0;
std::cin >> size;
int* arr = new int[size];
//... do stuff with arr
delete[] arr;

No big deal, but what if you want a matrix or some kind of 2D representation of data like
[0, 1, 2]
[3 ,4, 5]

[6, 7, 8]
again easy enough to create a static 2d array at compile time with
int arr[3][3];
and then fill it up but what if you need to find the sizes of your rows and columns at runtime? Welcome to the nightmare of allocating 2d dynamic arrays

int rows = 0, cols = 0;
std::cin >> rows >> cols;
int** my2Darr = new int*[rows];
for(int i = 0; i < cols; i++)
{
   my2Darr[i] = new int[cols];
}

and that’s just to get your array allocated, when you’re done with it you have to write a bunch of cleanup code like:

for(int i = 0; i < cols; i++)
{
    delete[] my2Darr[i];
}
delete[] my2Darr;

That’s no fun. It’s much easier to use a 1D array to emulate a 2D array and then use a stride(or offset) to navigate the structure. Basically you lay the 2 dimensions out in a line and the stride is the offset. If you use a nested loop the stride formula is i * cols + j or row * columns + column
So if we want a 5 * 5 array that hold the numbers 1 -25 in rows of 5 we can use this code

int rows = 5, cols = 5, count = 1;
int* matrix = new int[rows * cols];
for(int row = 0; row < rows; row++)
{
    for(int col = 0; col < cols; col++)
    {
        matrix[row * cols + col] = count++;
    }
}
// when we're done we clean up with a simple
delete[] matrix;

Again it’s generally best to use stl containers or a matrix library like glm but this often comes up when folks are learning the basic of C++ so I thought it good to write a post exploring dynamic 2D(and 1D) arrays.

Stride is a popular tool to navigate buffers in libraries like OpenGL
https://learnopengl.com/Advanced-OpenGL/Advanced-Data
And here is a link to Compiler Explorer with the complete code:
https://godbolt.org/z/bK69bW

Print unique values 6 ways

I participate in a couple of programming/C++ help forums on discord and the like. They’re fun, helping people is great and I also learn a lot. Often someone asks for a fairly simple algo like “Given a container of unsorted integers print only unique ones to the console.” There are some obvious solutions to this but in the spirit of inspiring others to think through the problem we often provide the asker with a convoluted solution in the hopes that that will help lead them to the basic ideas. Ideas like “I could store every new int I see in another container and then I could check for ones already seen with each element” or “What if I sorted the container….”
Which led me to come up with a variety of possible solutions to the problem using different things in the standard library and different techniques, I’ll discuss them briefly, show some code and link a benchmark at the end.

Obvious solution, use another vector of ints to hold values you’ve already seen and then only print new values, I’m going to use std::for_each for brevity but this is straightforward to write with a ranged based for or a raw loop. This solution is simple but it does take an extra allocation of unknown size that will reallocate several times if the original vector of ints is big so…

std::vector<int> seenVec;
std::for_each(vec.begin(), vec.end(),[&](auto& e){
    if(std::find(seenVec.begin(), seenVec.end(), e) == seenVec.end())
    {
        std::cout << e << ' ';
        seenVec.push_back(e);
    }
});

What if we do the same idea but in place? Basically we search the range behind the current element in the vector, no extra allocations, so that’s good. We use a static variable assuming this code will only be called once in the lifetime of the program, we’ll change that for the benchmark though…

std::for_each(vec.begin(), vec.end(),[&](auto& e){
        static auto end = vec.begin();
        if(std::find(vec.begin(), end, e) == end++)
        {
            std::cout << e << ' ';
        }
    });

Ok, that’s fine and good and does what we want but we’re doing an awful lot of searching through subranges of the vector or through another vector, what if we sorted? Then we can just output whenever the element changes…

std::sort(vec.begin(), vec.end());
for(const auto& e : vec)
{
    static auto compare = std::next(vec.begin(), 1);
    if(e != *(compare++))
    {
        std::cout << e << ' ';
    }
}

Nice, that works but it sorts the output which may not be what we want, do we have other standard library tools that can help us? What about a set? They only accept unique values after all, but they do sort. However there is an overload for std::set::insert that returns a std::pair of an iterator and a bool that indicates if the insertion succeeded, let’s try that.
[Note: there is also std::unordered_set but this was more fun :)]

std::set<int> seen;
for(const auto& e : vec)
{
    auto[vecIt, notSeen] = seen.insert(e);
    if(notSeen)
    {            
        std::cout << *vecIt << ' ';
    }   
}

that’s cool, and we can use a regular set constructor if we want it to be sorted like this

std::set<int> seenTwo {vec.begin(), vec.end()};
for(const auto& e: seenTwo)
    std::cout << e << ' ';

This also has the benefit of brevity, though I’m loathe to leave out the {} even on a single statement loop but hey, it’s slideware! (blogware?)
The set solutions are cool but they do require an additional allocation.

However there is one other standard library facility that also does not require any additional allocations, the aptly named std::unique . When this algo is applied to a sorted container it moves all the duplicates to the end and returns an iterator to the end of a range of sorted unique items. Just what we need! The only downfall is that is does mutate the original container so you may have to copy it first which is another allocation….

std::sort(vec.begin(), vec.end());
auto end = std::unique(vec.begin(), vec.end());
vec.erase(end, vec.end());
// you can erase the duplicate items at the end or use the
// end iterator to constrain the range when you print
for(const auto& e: vec)
    std::cout << e << ' ';

Alright, to the benchmarks, I’ll post a link at the bottom. I used a vector of 10000 randomly generated ints in the range 1-100 to make sure there was a lot of repetition and a stringstream to mimic standard out.
Predictably the for_each solutions fared the worst, surprisingly the one with extra allocation was faster than the one searching in place.
The set solutions were faster than the for_each solutions with a wider distribution but fared much worse when I decreased the range of random ints to create more duplicates.
sort and iterate came out on top or tied with the std::unique solution depending on the iteration of the benchmark.

So in closing the set solution that doesn’t sort is useful if you don’t want the output to be sorted or if you don’t want to mutate the original vector and sort and iterate and std::unique are the fastest.

https://quick-bench.com/q/jLgMY6qkOaAdjS-kVoRJ4eF4ehw

Structured bindings with simple aggregates

Structured bindings were introduced in c++17 as an easier way of getting data out of std::pair, std::tuple and the map containers. They are also quite handy to extract data from simple data aggregates, here is an example using the ubiquitous x,y Point struct

#include <iostream>
#include <type_traits>

struct Point
{
    int x = 1;
    int y = 1;
};

int main()
{
    Point point;
    auto [x, y] = point;
    std::cout << std::boolalpha << std::is_same_v<int, decltype(x)>;
}

Simple variadic constructor template

I don’t write a lot of templated code and haven’t really cracked template meta-programming yet but I thought this was a nice easy to read variadic template constructor using an initializer list and std::forward to move data into a member variable
https://godbolt.org/z/TYbEhq

#include <cstdint>   
#include <limits>
#include <array>

struct Foo 
{
   static constexpr auto size = 8;

   Foo(short n) noexcept 
   {
      for ( auto &e : data )
         e = n;
   }

   Foo( std::array<short,size> a ) noexcept 
   {
      for ( int i = 0;  i < size;  ++i )
         data[i] = a[i];
   }

   template <typename... Types>
   Foo( Types&&... t ) noexcept :
   data{static_cast<short>(std::forward<Types>(t))... }{}

private: 
  std::array<short, size> data;
};

int main() 
{
   Foo a = 1;         // initialize all to scalar value
   Foo b = {{1,2,3}}; // initialize with array... OK!
   Foo c =  {1,2,3};  // initialize with array... Variadic
}


chaining emplace_back

TIL that as of c++ 17 you can chain emplace_back when constructing a vector of objects, say you have a class Chain with an internal std::vector of std::pair<std::string, std::sting> called links, this code is viable

class Chain
{
  public: std::vector<std::pair<std::string, std::string>> link;
};
int main()
{ 
  std::vector<Chain> chain; 
  chain.emplace_back().link.emplace_back("0", "0");
}

compiler explorer link
https://godbolt.org/z/GPdboM

std::string functions for parsing lines

Typically if I’m reading text from a file that I want to parse, say a .csv file I’ve used a combination of an ifstream , std::getline and then a std::stringstream to parse the line into words or entries. Inspired by a suggestion in the c++ help discord I tried using std::string functions like std::string::find and substr instead and surprisingly it turned out to be much faster
code and benchmark here
https://quick-bench.com/q/W_8UPCi7BG7isXYsVZAgTSIlCDo