An implementation of Levenshtein Distance algorithm in modern C++ Below is an implementation of Levenshtein Distance algorithm.

I am trying to use modern C++ features as much as I can, i.e. auto, no pointer / raw memory but I feel like it is a constant struggle.

Code:

#include &lt;string_view&gt;
#include &lt;memory&gt;
#include &lt;vector&gt;

namespace utils
{
    auto getLevenshteinDistance(std::string_view string_1, std::string_view string_2)
    {
        const auto size_1{ string_1.size() };
        const auto size_2{ string_2.size() };

        if (size_1 == 0) return size_2;
        if (size_2 == 0) return size_1;

        std::vector&lt;std::size_t&gt; costs(size_2);
        for (std::size_t k{ 0 }; k &lt;= size_2; ++k) costs[k] = k;

        std::size_t i{ 0 };
        for (const auto&amp; itr_1 : string_1)
        {
            ++i;
            costs[0] = i + 1;
            auto corner{ i };

            std::size_t j{ 0 };
            for (const auto&amp; itr_2 : string_2)
            {
                ++j;
                auto upper{ costs[j + 1] };

                if (itr_1 == itr_2)
                {
                    costs[j + 1] = corner;
                }
                else
                {
                    auto t{ upper &lt; corner ? upper : corner };
                    costs[j + 1] = (costs[j] &lt; t ? costs[j] : t) + 1;
                }

                corner = upper;
            }
        }

        return costs[size_2];
    }
}


For instance, I can't use auto when declaring my vector, because there is no std::make_vector (like make_tuple for instance).

Also I'm developing anxiety for implicit conversions; for instance I could have written

auto i{ 0 };


instead of 

std::size_t i{ 0 };


But given that the value will be put into an array containing type std::size_t, I'd rather just have it be of the right type immediately. Lots of stuff like that is bothering me.

Even looping through the array by const auto&amp; seems weird when I'm still having a count variable.. Doesn't advantage disappear, and I might as well just for (int i = 0; ..)

Any suggestions for improvements in the way of modern, good practice, and performance is appreciated.
Invalid access

There are several occurrences of out-of-range access as 1201ProgramAlarm's comment pointed out:


for (std::size_t k{ 0 }; k &lt;= size_2; ++k) costs[k] = k;

  
  

costs[j + 1]

  
  

return costs[size_2];



This problem can be fixed by increasing the size of costs by one.

Usage of the standard library


std::vector&lt;std::size_t&gt; costs(size_2);
for (std::size_t k{ 0 }; k &lt;= size_2; ++k) costs[k] = k;



Use std::iota:

std::vector&lt;std::size_t&gt; costs(size_2 + 1);
std::iota(costs.begin(), costs.end(), std::size_t{0}); // or 0_zu; see below



auto t{ upper &lt; corner ? upper : corner };
costs[j + 1] = (costs[j] &lt; t ? costs[j] : t) + 1;



Use std::min:

costs[j + 1] = std::min({upper, corner, costs[j]}) + 1;


auto

When you want the type of a variable to be deduced, auto is handy, because you don't have to write the type or expression twice.  When you want the type of a variable to be fixed, however, auto becomes cumbersome &mdash; so feel free to write

std::size_t i = 0;


An alternative is to use a user-defined literal: (there's a proposal P0330 Literal Suffix for (signed) size_t to add builtin literals for std::size_t)

namespace util_literals {
    constexpr std::size_t operator""_zu(unsigned long long number)
    {
        return static_cast&lt;std::size_t&gt;(number);
    }
}


So you can write:

using namespace util_literals;
auto i = 0_zu;


Also, instead of


for (const auto&amp; itr_1 : string_1)



it is more common to access characters by value.  Also, itr is a misleading name for characters:

for (char c_1 : string_1)


Simplification

This check is redundant:


if (size_1 == 0) return size_2;
if (size_2 == 0) return size_1;



because the algorithm works well with empty strings.



Here's my version:

#include &lt;algorithm&gt;
#include &lt;cstddef&gt;
#include &lt;iomanip&gt;
#include &lt;iostream&gt;
#include &lt;numeric&gt;
#include &lt;string&gt;
#include &lt;string_view&gt;
#include &lt;vector&gt;

std::size_t Levenshtein_distance(std::string_view string_a, std::string_view string_b)
{
    const auto size_a = string_a.size();
    const auto size_b = string_b.size();

    std::vector&lt;std::size_t&gt; distances(size_b + 1);
    std::iota(distances.begin(), distances.end(), std::size_t{0});

    for (std::size_t i = 0; i &lt; size_a; ++i) {
        std::size_t previous_distance = 0;
        for (std::size_t j = 0; j &lt; size_b; ++j) {
            distances[j + 1] = std::min({
                std::exchange(previous_distance, distances[j + 1]) + (string_a[i] == string_b[j] ? 0 : 1),
                distances[j] + 1,
                distances[j + 1] + 1
            });
        }
    }
    return distances[size_b];
}

int main()
{
    std::string string_a;
    std::string string_b;
    while (std::cin &gt;&gt; std::quoted(string_a) &gt;&gt; std::quoted(string_b)) {
        std::cout &lt;&lt; Levenshtein_distance(string_a, string_b) &lt;&lt; '\n';
    }
}


Input:

kitten sitting
corporate cooperation
123 ""
"" ""


Output:

3
5
0
0


(live demo)