DEV Community

Cover image for Let’s review some code #1: C++
pikoTutorial
pikoTutorial

Posted on • Edited on • Originally published at pikotutorial.com

Let’s review some code #1: C++

Welcome to the next pikoTutorial !

Below you can find the code that we will be reviewing today. Before you scroll down to section where I fix it, feel free to check how many mistakes you can find.

using namespace std;

vector<size_t> ContainsTwoSum(vector<uint8_t> input, uint8_t &target)
{
    unordered_map<uint8_t, size_t> m;

    for (int i=0; i<input.size(); i++) {
        uint8_t complement = target - input[i];

        if (m.find(complement) != m.end()) {
            return {m[complement], i};
        }

        m[input[i]] = i;
    }

    return {};
}
Enter fullscreen mode Exit fullscreen mode

This is a solution for one of the variants of the popular algorithmic tasks: given a vector of 1-byte unsigned integers and a 1-byte unsigned integer target value, return the indices of the two numbers that add up to the target. Although the code compiles and works properly, there's a lot to do in terms of its quality. Let's start with the first line:

using namespace std;
Enter fullscreen mode Exit fullscreen mode

This is never a good idea. std is a huge namespace and chances that one of the types defined within std namespace will collide with some other type are pretty big. You should always use std:: explicitly whenever you use something from the standard library. The next is function's signture:

vector<size_t> ContainsTwoSum(vector<uint8_t> input, uint8_t &target)
Enter fullscreen mode Exit fullscreen mode

There are couple of things to consider here:

  • What do we return here? In general, a vector of two indices, but what if sum doesn't exist? Do we return empty vector? A vector of two invalid numbers? The situation seems to be "all or nothing", either there is a sum or there isn't, but how will we communicate to the user of this API that some vectors mean "sum does not exist"? When such questions appear, it is most probably a good idea to use std::optional. By introducing it in a function signature, we tell the user "either there will be a vector of two indices or there will be no vector at all - you must check it first".
  • Second question is whether std::vector is a good choice for such application at all? In the end, if the sum exists, there will be always 2 numbers - let's then use std::pair (thanks @elvisoric for this suggestion).
  • Names beginning with words like "Contains...", "Has...", "Exists..." suggest that the function returns a boolean value because the answer to these words is either "yes" or "no".
  • The input vector is passed by mutable value. Do we really need to modify this vector inside the function? Do we really need to copy vector to pass it to the function? The answers for both of these questions seem to be "no", so it's a good idea to pass it by a const reference.
  • The last thing is target sum passed by reference. Despite the fact that it will prevent us from providing a number directly in the function call (e.g. ContainsTwoSum({}, 12U)) because the compiler won't be able to bind non-const lvalue reference to our rvalue 12, it also does not make sense from the efficiency point of view. Addresses are typically 32 or 64 bit (depending on the architecture), so by passing 1-byte input argument we are effectively increasing its size to 4 or 8 bytes. This is why it is better to pass primitive types by value, not by reference. After all these considerations, we end up with the following function signature:
using ResulingIndexes = std::optional<std::pair<size_t, size_t>>;
ResulingIndexes GetSummingIndexes(const std::vector<uint8_t> &input, const uint8_t target)
Enter fullscreen mode Exit fullscreen mode

Next there's an unordered map declaration:

unordered_map<uint8_t, size_t> m;
Enter fullscreen mode Exit fullscreen mode

What is m? What do we save by giving such a short, non-expressive name? We definitely loose readability and maintainability of the code. Don't be afraid of longer variable names and always make them self-explanatory. Here we could go for something like:

std::unordered_map<int16_t, size_t> number_to_index_mapping;
Enter fullscreen mode Exit fullscreen mode

After that we have a for loop.

for (int i=0; i<input.size(); i++)
Enter fullscreen mode Exit fullscreen mode

What are we iterating over? Over the indices of the vector. Indices are of type size_t which is an unsigned integer what means that we have an implicit casting here. To avoid it, we correct the type of i:

for (size_t i=0U; i<input.size(); i++)
Enter fullscreen mode Exit fullscreen mode

Now let's look at the very interesting line:

uint8_t complement = target - input[i];
Enter fullscreen mode Exit fullscreen mode

Three things in here:

  • complement is calculated and then saved what means that it is not modified anywhere. It means that it should be marked const.
  • There are unsigned integers everywhere in this function, so someone put it here as well, but target may be equal to e.g. 2 and num[i] may be equal to 3. What is the result of 2-3 when stored in a 1-byte unsigned integer? 255 because of underflow error! To correct this, we must change that type to a signed integer. What size should it be? Well, the lowest value of the target could be 0 and the highest value of the vector element could be 255, so we need a type which can hold -255 value, which is int16_t (int8_t lowest value is -128, so 0-255 would give us 1).
  • Accessing vector member with square brackets is a bad practice and at() should be used instead. If you accidentally go beyond the vector size, at() will throw an exception which you can catch and handle somehow, but if you go beyond the vector size using square brackets, you get a segmentation faul and there's nothing you can do about it. Some could say that at() causes performance overhead because it has to additionally compare the index with the vector's size. I would say that you must have a really good reason to not to use at() (for example, results from a profiling tool showing that at() calls are the real bottleneck in your algorithm).

Combining all these 3 points together, we get the following line:

const int16_t complement = target - input.at(i);
Enter fullscreen mode Exit fullscreen mode

The next in line is the if statement checking presence of a complement in the map:

if (m.find(complement) != m.end()) {
    return {m[complement], i};
}
Enter fullscreen mode Exit fullscreen mode

Firstly, when we want to check if a key exists in the map, find is ok, but the because it has to be compared to the end iterator, the statement becomes unnecessarily long. To make it shorter, we can use count function which returns the number of occurrences of the given key and thus every number greater than 0 will be evaluated to true. Both find and count have time complexity O(1), so the change does not impact the overall performance.

Secondly, accessing map member with square brackets brings the same problems as accessing vector elements described above. Map also delivers at() member function, so let's just use it here.

As the last step, we need to adjust returned value to the new function's signature basing on the std::optional.

if (number_to_index_mapping.count(complement)) {
    return std::make_pair(number_to_index_mapping.at(complement), i);
}
Enter fullscreen mode Exit fullscreen mode

At the end, we have a line adding an element to the map which can be rewritten using insert() member function:

number_to_index_mapping.insert({input.at(i), i});
Enter fullscreen mode Exit fullscreen mode

Note for beginners: When assigning values to a map, remember that insert() and [] are not equivalent! The insert() method adds a key-value pair to the map only if the key does not already exist in the container. This means insert() will not overwrite an existing value for a key. In our case it doesn't matter, but if you need behavior where the value for an existing key should be updated, you should use the [] operator.

Eventually, we end up with the whole function looking like this:

#include <iostream>
#include <vector>
#include <optional>
#include <unordered_map>

using ResulingIndexes = std::optional<std::pair<size_t, size_t>>;
ResulingIndexes GetSummingIndexes(const std::vector<uint8_t> &input, const uint8_t target)
{
    std::unordered_map<int16_t, size_t> number_to_index_mapping;

    for (size_t i=0U; i<input.size(); i++) {
        const int16_t complement = target - input.at(i);

        if (number_to_index_mapping.count(complement)) {
            return std::make_pair(number_to_index_mapping.at(complement), i);
        }

        number_to_index_mapping.insert({input.at(i), i});
    }

    return std::nullopt;
}
Enter fullscreen mode Exit fullscreen mode

Top comments (2)

Collapse
 
elvisoric profile image
Elvis Oric • Edited

In my opinion ContainsTwoSum name is bad, it indicates that function returns boolean value and that's it, but we are returning more than that. Naming is always hard, but it should clearly communicate the intent :)

You are returning a std::vector and when you see that in the interface, it's not clear that only two values will be there. Why not using std::pair or just POD to describe it?

Also you can use emplace instead of insert.

Collapse
 
pikotutorial profile image
pikoTutorial

Good point, such refactoring should most probably include refactoring of the original function name and its return type as well - updated the post:)

However, when it comes to using emplace instead of insert it is not obvious in my opinion if it would bring actual benefit in this particular use case.

First thing is that here we deal with trivially constructible types and compilers are especially good in optimizing copy/move operations of such types, so there's a great chance that the temporary copy involved in passing values to insert would be "optimized away" and would never create any overhead in practice.

The second thing is more interesting - notice, that the input vector may contain duplicated values (potentially many of them) what means that the value we're about to construct (vector index) may be discarded multiple times because vector element values are here keys of the map. CppReference dedicated to emplace says that:

The element may be constructed even if there already is an element with the key in the container, in which case the newly constructed element will be destroyed immediately.

So with insert we first construct the value and then discard it while attempting to put it inside the map and with emplace we construct the value in the map and then destroy it if the key already exists. To be honest, I can't tell with 100% confidence which one would be faster without profiling it. I'm just saying that it is in my opinion not that obvious and it seems like this depends on which of these operations is better optimized by the compiler.

The best solution for this may be neither insert nor emplace, but try_emplace which guarantees no temporary copy (as in case of insert) and no construction if the key exists (as in case of emplace).