DEV Community

René Sebastián Pucheta
René Sebastián Pucheta

Posted on • Updated on

Many ways to solve simple problems in modern C++

Just wanted to dive into new c++ features coming with a full-stack C# and javascript background. As a side note, I have 12 years as a professional developer writing code for a wide variety of languages, so that made me think that after all these years learning C++ would be easier. I was wrong: C++ has a tremendously high learning curve, so I decided to add new features to the extent that I incrementally increase the complexity of the problems. Beginning with the simplest bubbles sorting method I will try to find many ways to solve it using a different features taken from the latest C++ standards (C++11, C++17, C++2a).

The only motivation to do that is just the pleasure of learning, so taking advantage of this lockdown (let's try to see a silver lining here, that we have more time to do things) I'm dedicating it to learn C++ and see how far I can go with it before having a burnout :D.

disclaimer: I'm not a C++ professional, so most of this content can be wrong, I don´t have experience in C++, neither academic integrity to meet, but I accept the blame for whatever deficiencies you find, though.

Bubbles sort method.

This one is one of the simplest algorithms out there. It can be explained as an O(n2) algorithm, which means that the array containing unsorted numbers will be iterated two times. Then, whenever two consecutive elements are found they will be swapped with each other.

Lets first prepare the c++ template:

#include <bits/stdc++.h>

int main () {
    using namespace std;

    return EXIT_SUCCESS; // I will use this macro here, which represents de '0' value.
}

So, the first thing to do that comes to my mind is "how to fill this array (from now on I will call it a vector) with randomized, unsorted numbers?", I will just initialize it with hardcoded numbers for now.

vector<int32_t> vec = { 92, 23, 1, 6, 25, 72, 66, 10 };

With these two chunks of code I've learned a couple of things:

  • Make use of int32_t instead of int, long unsigned int, long. int32_t seems to be the convention nowadays. Don't know exactly why, but it seems that modern languages need very very (repeated twice on purpose) specific data types for the sake of consistency across platforms.
  • Scope level of using instead of outside the function main.
  • The macro EXIT_SUCCESS, which is not necessarily mandatory.

Now the two nested iterations of vec variable.

for (size_t i = 0; i < vec.size(); ++i) {
    for (size_t j = 0; j < vec.size() - 1; ++j) {
        if (vec[j] > vec[j + 1]) {
          swap(vec[j], vec[j + 1]);
        }
    }
}

Now, what can I see here?

  • The use of size_t instead of int since vec.size() returns an size_t and not int. If I use int, it will work, that seems obvious because size_t can be cast as int, but turns out that size_t can represent any type size in case that int is not enough. I can avoid the extra internal cast at runtime (or compile-time?).
  • Standard library already has a swap method.
  • The pre-increment operator ++i instead of the commonly used post-increment, i++. It turns out that i++ returns a stored original value before the addition is made, contrary to i++ that returns the addition. In other words i++ needlessly (at least in the for...loop case) uses additional memory to store the value.

Now another iteration of vec variable just to render in screen the results:

for (size_t i = 0; i < vec.size(); ++i) {
    cout << vec[i] << endl; // Replacement of "\n"
}

Lets compile and run:

g++ -std=c++2a -O2 -Wall sort.cpp -o sort

The results:

92
72
66
25
23
10
6
1

Now let's see what I can do with modern C++ features can we use with this simple problem.

Instead of initializing the vector with hardcoded data I will make use of Lambda Expressions so that I can generate random numbers. With this one I will try not to worry much about performance, the first solution seems to be faster so far.

vector<int32_t> vec(100); // This time let's make a bigger vector.
auto genRandomNumber = [](){ return (std::rand() % 100); };
std::generate(vec.begin(), vec.end(), genRandomNumber);

What do we have here?

Another way to initialize a vector is by setting its initial capacity, which in this case is 100. Then I create this genRandomNumber lambda expression containing just a random generated number between 0 and 100, which is later used in the std::generate function.

Smallest number that is evenly divisible by all of the numbers from 1 to 20.

The next problem will be even simpler, it just requires one single loop. From the top of my head I can think in a possible (and working) solution. Cycle between 0 to the infinity, or the maximum long value possible, and check if it can be divided by every number from 1 to 20 in a bunch of ugly if's.

using namespace std;

for (size_t i = 1; i < std::numeric_limits<size_t>::max(); ++i) {
        if (
            i % 1 == 0 &&
            i % 2 == 0 &&
            i % 3 == 0 &&
            i % 4 == 0 &&
            i % 5 == 0 &&
            i % 6 == 0 &&
            i % 7 == 0 &&
            i % 8 == 0 &&
            i % 9 == 0 &&
            i % 10 == 0 &&
            i % 11 == 0 &&
            i % 12 == 0 &&
            i % 13 == 0 &&
            i % 14 == 0 &&
            i % 15 == 0 &&
            i % 16 == 0 &&
            i % 17 == 0 &&
            i % 18 == 0 &&
            i % 19 == 0 &&
            i % 20 == 0
        ) {
            // Print result
            cout << "Result :: " << i << endl;
            break; 
        }
    }

Let's compile and run. It works!

Now let's make it a little less ugly by iterating from 1 to 20 inside the first loop, so I will make use of C++11's range-based for loop.


int32_t x = 1;

for (size_t i = 1; i < numeric_limits<size_t>::max(); ++i) {
    for (auto p: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}) {
      x = p;
      if (i % p != 0) break;
    }
    if (x == 20) {
        // Print result
        cout << "Result :: " << i << "\n";
        break;
    }
}

Compile and run. Still works!

Now let's make use again of lambda expressions to generate that vector.

vector<int32_t> vec(20);

auto funcGen = [counter = 0]() mutable -> int32_t { return ++counter; };
std::generate(vec.begin(), vec.end(), funcGen);

Let's analyze this:

  • In funcGen lambda expression, a parameter counter is passed, which allows us to store the returned number because we want to return the next number incremented by 1 on each iteration, and the only elegant way to do this is using this form.
  • mutable tells the lambda expression (insert more advanced way to explain this at a lower level) that can modify any variable captured, in this case counter.

So, that's it.

Latest comments (1)

Collapse
 
mmi profile image
Georg Nikodym

The specifically sized types (stdint.h / inttypes.h) arose in the C standard in response to the imprecision (and bugs) arising from terms like char, short, int, long (things came to a head when folks were tearing their hair out making sure that their 32-bit apps worked in 64-bit environments). It may seem weird but trust me, when software lives over decades, over-specifying is for the best.