4
\$\begingroup\$

I have the following:

#include <string>
#include <string_view>
#include <vector>
#include <unordered_map>


#include <iostream>

namespace utils
{
    void replace_all(std::string& string, const std::string_view from, const std::string_view to)
    {
        std::size_t start_pos{ 0 };
        while ((start_pos = string.find(from)) != std::string::npos)
        {
            string.replace(start_pos, from.length(), to);
            start_pos += to.length();
        }
    }

    void replace_all(std::string& string, const std::unordered_map<std::string_view, std::string_view>& map) // Warning 2 here
    {
        for (const auto [from, to] : map) // Warning 1 here
        {
            replace_all(string, from, to);
        }
    }
}

int main()
{
    std::unordered_map<std::string_view, std::string_view> my_map{ {"this", "that"}, {"hes", "her"}, {"my", "yours"} };
    std::string my_string{ "This is hes chocolate and my aswell" };
    utils::replace_all(my_string, my_map);
    std::cout << my_string << std::endl;

    return 0;
}

It works and outputs: This is her chocolate and yours aswell as expected.

Analysing this in MSVC 2019 with C++ Core guidelines turned on I do get the following warnings though:

C:\dev\MyVSProjects\AE\AE\include\AE\Main.cpp(23): warning C26486: Don't pass a pointer that may be invalid to a function. Parameter 0 '$S1' in call to '<move><std::pair<std::basic_string_view<char,std::char_traits<char> > const ,std::basic_string_view<char,std::char_traits<char> > > const & __ptr64>' may be invalid (lifetime.3).

C:\dev\MyVSProjects\AE\AE\include\AE\Main.cpp(21): warning C26487: Don't return a pointer '(*(*map))' that may be invalid (lifetime.4).

I'd like to remove these warnings and make the code as clean as possible.

\$\endgroup\$
  • \$\begingroup\$ Can you post your complete code, including #include directives, so that we can find what the line numbers point to? \$\endgroup\$ – L. F. Mar 23 at 10:49
  • \$\begingroup\$ I have updated the code to have the includes aswell as highlighted the lines with comments. \$\endgroup\$ – Cortex Mar 23 at 11:03
6
\$\begingroup\$

This code is nicely written and clear in both code and description. Good job! I think there are still some things that might be improved.

Fix the bug

The updated value of start_pos is not being used for each iteration of the loop. Instead, it should be, so the while loop should be this:

while ((start_pos = string.find(from, start_pos)) != std::string::npos)

Avoid creating copies if practical

I don't have MSVC 2019 available, but I suspect that it's pointing out that you've asked it to make copies of from and to. That is, instead of this:

for (const auto [from, to] : map)

Write this:

for (const auto& [from, to] : map)

And see if that helps. Another alternative would be to create a version of replace_all that takes a std::pair<std::string_view, std::string_view> and rewrite the loop as:

for (const auto& pr: map) {
    replace_all(string, pr);
}

Consider using a different data structure

The std::unordered_map used here may seem like a logical and intuitive structure to use but it has some potential problems. First, the iterator has no defined ordering. That is, the ordering is implementation defined so the programmer has no control of it. That might be a problem if we want to do things in a specific order. For example, replacing literal characters with their corresponding predefined XML entities, such as > to &gt; we typically want to do the & to &amp; conversion first for obvious reasons. There's no way to do that with the existing version of the code. Second, we can't create a constexpr version of the map because it has a non-trivial destructor. I'd suggest allowing something like a std::array of std::pair<std::string_view, std::string_view>. This is the approach that is used in conjunction with the next few suggestions.

Use using to simplify code

The existing code could be simplified a bit by using using like so:

using MapContainer = std::unorded_map<std::string_view, std::string_view>;
void replace_all(std::string& string, const MapContainer& map)  { /* etc. */ }

Now any place we use the rather long name we can simply write MapContainer.

Use templates for flexibility

Instead of tying the replace_all function to a specific kind of structure, we could pass it a pair of templated iterators instead for flexibility:

template <class ForwardIt>
void replace_all(std::string& string, ForwardIt first, ForwardIt last) {
    for ( ; first != last; ++first) {
        replace_all(string, *first);
    }
}

Now all we need is any forward iterator that returns something that can be used by the inner replace_all. In fact, we can simplify even further because this is exactly like the definition of std::for_each.

Don't use std::endl if '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Consider creating a parallel version

The current version is simple and straightforward, but makes multiple passes through the string. It's possible to create a version that makes a single pass through or that makes multiple passes in parallel. The single pass version could be general purpose, but the parallel version would require that patterns be completely independent (unlike the entity-replacing example I mentioned).

Consider eliminating return 0

You don't need to explicitly provide a return 0; at the end of main -- it's created implicitly by the compiler. Some people apparently feel very strongly both for and against this. I advocate omitting it but you can decide for yourself.

Alternate version

Here's what I came up with using all of these suggestions:

#include <string>
#include <string_view>
#include <array>
#include <algorithm>
#include <iostream>

namespace utils
{
    using WordPair = std::pair<std::string_view, std::string_view>;
    void replace_all(std::string& string, const WordPair &pr) {
        for (std::size_t start_pos{ 0 };
            (start_pos = string.find(pr.first, start_pos)) != std::string::npos;
            start_pos += pr.second.length())
        {
            string.replace(start_pos, pr.first.length(), pr.second);
        }
    }
}

int main()
{
    constexpr std::array<utils::WordPair, 5> my_map{{ 
        {"&", "&amp;"}, 
        {"<", "&lt;"}, 
        {">", "&gt;"}, 
        {"'", "&apos;"}, 
        {"\"", "&quot;"} 
    }};
    std::string my_string{ "This & that aren't \"<>\"." };
    // use a lambda for clarity
    auto repl = [&my_string](const utils::WordPair &p){
            utils::replace_all(my_string, p);
    };
    std::for_each(my_map.cbegin(), my_map.cend(), repl);
    std::cout << my_string << '\n';
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Is there any reason why you sometimes put the ampersand next to the type and sometimes next to the variable? e.g. std::string& string, const WordPair &pr? \$\endgroup\$ – ades Mar 25 at 11:18
  • 1
    \$\begingroup\$ No. I’m trying to change my style to always do type& but don’t always remember. It’s hard to break a decades old habit! \$\endgroup\$ – Edward Mar 25 at 11:21
3
\$\begingroup\$

One drawback of this implementation is that, when from and to are of different lengths, it works in quadratic time. Consider

auto attack = "12324252627";
replace_all(attack, "2", "42");

How many times most characters are copied to only be copied or, even worse, replaced later?

(Coincidentally, when pattern and replacement are of equal lengths this shouldn't be an issue.)

More reasonable would be to give up on in-place modification and return a freshly constructed string, with all the proper replacements done, in linear time.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Had not considered that. Interesting. For my use case it wont matter though, as I will be looking for very specific non 'replicating' keywords. Good to note though. \$\endgroup\$ – Cortex Mar 23 at 21:42
  • \$\begingroup\$ This issue is addressed in the "Fix the bug" section of my answer. \$\endgroup\$ – Edward Mar 23 at 23:46
  • \$\begingroup\$ @Edward How exactly? \$\endgroup\$ – bipll Mar 24 at 2:13
  • \$\begingroup\$ @Edward suggest skipping ahead by the size of the replacement word, which means the replacement wouldn't be re-parsed. \$\endgroup\$ – ades Mar 25 at 11:20
  • \$\begingroup\$ @ades So what? All the quadratic copies still remain. \$\endgroup\$ – bipll Mar 25 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.