6
\$\begingroup\$

I’m starting to learn C++ by doing a lot of exercises. I want you to point me to where/what improvements I can do to make my code better.

The exercise:

write a URLencode function that takes a string and searches for spaces and replace them with %20

My solution:

#include <iostream>
#include <string>
#include <cassert>

using namespace std;
string  urlEncode(const string &a) {
    string b;
    for (auto& ch : a) {
        if (ch == ' ') {
            b.append("%20");
        }
        else {
            b.push_back(ch);
        }
    }
    return b;
}

int main() {

    assert(urlEncode("first second") == "first%20second");
    
    return 0;
}

I included tag because most of the compiler nitty gritty optimization is done at that level, and I want to see the perspective of it from that side as well.

\$\endgroup\$
8
  • 3
    \$\begingroup\$ What x86 optimizations are you referring to? I see nothing in your code that is specific to x86. \$\endgroup\$ Aug 21, 2022 at 13:29
  • \$\begingroup\$ things like caches, write buffer, ... etc \$\endgroup\$ Aug 21, 2022 at 13:30
  • 4
    \$\begingroup\$ The performance tag might be better then. \$\endgroup\$
    – G. Sliepen
    Aug 21, 2022 at 13:52
  • \$\begingroup\$ It's quite rare that a C++ programmer targets just one instruction-set architecture - you might want to consider the embedded tag if you are developing for an embedded system, and don't care about PDP-11, ARM, MIPS, RISC-V, etc. \$\endgroup\$ Aug 23, 2022 at 7:06
  • 1
    \$\begingroup\$ @TobySpeight for you it is, for others it's not, as there are many people like me, looking for questions / answers / code review and instruction, using links will make it easy for them, otherwise it will be lost in the track of other question that aren't related \$\endgroup\$ Aug 24, 2022 at 8:45

3 Answers 3

7
\$\begingroup\$

Firstly, it's great to see that you have thought about testing your code. It's always a good idea to create as many automated tests as you can think up. I might add a couple more tests, that ensure that the conversion is correct when the first and/or last character is a space (sometimes things that work in the middle can go slightly wrong at the ends).

If you're concerned about efficiency, then for (auto& ch : a) might not be what you want. Because ch is a reference, then every access is indirect; for (auto ch: a) makes it a value, likely stored in a register. An optimising compiler will probably transform this code for you, but why take the chance? And why make it work harder, given that it's just as clear?

\$\endgroup\$
2
  • \$\begingroup\$ I was under the impression that for (auto& ch : a) would be faster as data won't have to be copied. Why is for (auto ch : a) faster here? \$\endgroup\$
    – csmathhc
    Aug 24, 2022 at 4:10
  • 1
    \$\begingroup\$ Because a reference is a level of indirection, similar to a pointer. It's generally faster to copy a small value (such as char) than to access it via a reference (which in principle requires two reads each time it's used - good optimisation will reduce that). \$\endgroup\$ Aug 24, 2022 at 5:16
6
\$\begingroup\$

General Observations

The code doesn't replace space with %20, it returns a second string with the correct value. While this does do the job of returning the proper string, it may waste memory. What did the original problem description really say? If you are writing code for embedded programming this may be a problem, since memory is limited on embedded devices.

Note optimization, the C++ compiler has 4 levels of optimization, O0 through O3, if you are writing code that manipulates hardware you may not be able to use all 4 levels of optimization. If you are not writing code that manipulates hardware O3 code provides the best level of optimization. The only way to really understand the optimization is to examine the intermediate assembly code that is generated.

Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

\$\endgroup\$
3
  • 4
    \$\begingroup\$ "The" C++ compiler? Nothing in the C++ standard says there must be 4 optimisation levels to choose from. \$\endgroup\$ Aug 21, 2022 at 14:37
  • 2
    \$\begingroup\$ dunno what compiler you're talking about, but for example g++ has 7: -O0 , -O1, -O2, -O3, -Ofast, -Os, -Og \$\endgroup\$
    – hanshenrik
    Aug 22, 2022 at 12:09
  • \$\begingroup\$ What did the original problem description really say? - This is an entry level interview question, so nothing special. geeksforgeeks.org/urlify-a-given-string-replace-spaces-with-%20 \$\endgroup\$
    – panik
    Aug 26, 2022 at 17:50
2
\$\begingroup\$

This is actually a pretty good exercise for learning C++, and your swing at it is well done. The most important accomplishment is that your code is correct; it gives the right answer, always, for all input. That’s no small feat. The hardest part of learning coding is getting things correct. Once you can get things correct, you can always refactor for efficiency.

Before I get into reviewing the code, I want to suggest that you take the time to learn a bit about unit testing in C++.

Testing

Unfortunately, there’s no standard unit testing library, but there are a few nice ones out there you could use. A good choice for starting out might be Catch2. The easiest way to use Catch2 is to download catch_amalgamated.hpp and catch_amalgamated.cpp, drop both of those files in the source directory of your project, and make sure you compile and link with catch_amalgamated.cpp.

With Catch2, this is how you’d test your code:

First you’d put your code in its own header and source files. In your case, you probably want url_encode.hpp and url_encode.cpp. The header will just have the declaration:

#ifndef INCLUDE_GUARD_change_this_to_whatever_you_want_thats_unique
#define INCLUDE_GUARD_change_this_to_whatever_you_want_thats_unique

#include <string>

std::string urlEncode(std::string const&);

#endif // include guard

The source file will have the definition:

#include "url_encode.hpp"

using namespace std;
string  urlEncode(const string &a) {
    string b;
    for (auto& ch : a) {
        if (ch == ' ') {
            b.append("%20");
        }
        else {
            b.push_back(ch);
        }
    }
    return b;
}

Next you’d create a test file. In your case, probably name it url_encode.test.cpp, make it look something like this:

#include "catch_amalgamated.hpp"

#include "url_encode.hpp"

TEST_CASE("urlEncode encodes correctly")
{
    CHECK(urlEncode("first second") == "first%20second");
}

(You’ll notice there’s no main(). Catch2 provides that for you.)

As you can see, the actual test is exactly what you wrote in your assert in main(), so you may be wondering what the point was. When everything works, it’s hard to see the benefit of a proper test library. So to illustrate, let’s temporarily break your code; let’s replace b.push_back(ch) with b.push_back('x').

If you try to run your test program now, the test will fail and the assertion will fire… but all you’ll see is something like “urlEncode("first second") == "first%20second" is not true”. That’s good that it catches the problem… but it doesn’t really help much because it doesn’t tell you why the return value of urlEncode() doesn’t match.

Now try running the Catch2 version, and you will get output like this:

Randomness seeded to: 1305833654

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.out is a Catch2 v3.1.0 host application.
Run with -? for options

-------------------------------------------------------------------------------
urlEncode encodes correctly
-------------------------------------------------------------------------------
url_encode.test.cpp:5
...............................................................................

url_encode.test.cpp:7: FAILED:
  CHECK( urlEncode("first second") == "first%20second" )
with expansion:
  "xxxxx%20xxxxxx" == "first%20second"

===============================================================================
test cases: 1 | 1 failed
assertions: 1 | 1 failed

As you can see, it tells you:

  1. Exactly which test failed (the test for “urlEncode encodes correctly”).
  2. Exactly which file and line the failing test starts on (“url_encode.test.cpp:5”).
  3. Exactly which file and line the failing assertion is on (“url_encode.test.cpp:7”).
  4. What that assertion was (“CHECK( urlEncode("first second") == "first%20second" )”).
  5. Exactly why it failed (“"xxxxx%20xxxxxx" == "first%20second"” wasn’t true).

You can see that all the non-space characters are x, which would give you a clue what the problem is (if you didn’t already know).

The real power of this comes when you add more tests:

#include "catch_amalgamated.hpp"

#include "url_encode.hpp"

TEST_CASE("urlEncode encodes correctly")
{
    CHECK(urlEncode("first second") == "first%20second");
    CHECK(urlEncode(" first second") == "%20first%20second");
    CHECK(urlEncode("first second ") == "first%20second%20");
    CHECK(urlEncode(" first second ") == "%20first%20second%20");
}

TEST_CASE("urlEncode handles empty strings")
{
    CHECK(urlEncode("") == "");
}

TEST_CASE("urlEncode input with no spaces")
{
    CHECK(urlEncode("a") == "a");
    CHECK(urlEncode("123") == "123");
    CHECK(urlEncode("a_longer-and_moreC0MPL3X_str") == "a_longer-and_moreC0MPL3X_str");
}

TEST_CASE("urlEncode input with only spaces")
{
    CHECK(urlEncode(" ") == "%20");
    CHECK(urlEncode("    ") == "%20%20%20%20");
}

// ... and so on...

With the broken function, the output is this:

Randomness seeded to: 4114723309

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.out is a Catch2 v3.1.0 host application.
Run with -? for options

-------------------------------------------------------------------------------
urlEncode encodes correctly
-------------------------------------------------------------------------------
url_encode.test.cpp:5
...............................................................................

url_encode.test.cpp:7: FAILED:
  CHECK( urlEncode("first second") == "first%20second" )
with expansion:
  "xxxxx%20xxxxxx" == "first%20second"

url_encode.test.cpp:8: FAILED:
  CHECK( urlEncode(" first second") == "%20first%20second" )
with expansion:
  "%20xxxxx%20xxxxxx" == "%20first%20second"

url_encode.test.cpp:9: FAILED:
  CHECK( urlEncode("first second ") == "first%20second%20" )
with expansion:
  "xxxxx%20xxxxxx%20" == "first%20second%20"

url_encode.test.cpp:10: FAILED:
  CHECK( urlEncode(" first second ") == "%20first%20second%20" )
with expansion:
  "%20xxxxx%20xxxxxx%20"
  ==
  "%20first%20second%20"

-------------------------------------------------------------------------------
urlEncode input with no spaces
-------------------------------------------------------------------------------
url_encode.test.cpp:18
...............................................................................

url_encode.test.cpp:20: FAILED:
  CHECK( urlEncode("a") == "a" )
with expansion:
  "x" == "a"

url_encode.test.cpp:21: FAILED:
  CHECK( urlEncode("123") == "123" )
with expansion:
  "xxx" == "123"

url_encode.test.cpp:22: FAILED:
  CHECK( urlEncode("a_longer-and_moreC0MPL3X_str") == "a_longer-and_moreC0MPL3X_str" )
with expansion:
  "xxxxxxxxxxxxxxxxxxxxxxxxxxxx"
  ==
  "a_longer-and_moreC0MPL3X_str"

===============================================================================
test cases:  4 | 2 passed | 2 failed
assertions: 10 | 3 passed | 7 failed

Two test cases passed—the empty string and the one with only spaces, because neither has any non-space characters—and two failed—the one with only non-spaces, and the one with both spaces and non-spaces. This would be a strong clue that the problem is with non-space characters.

If you fix the urlEncode() back to what it should be, the output becomes:

Randomness seeded to: 1565700796
===============================================================================
All tests passed (10 assertions in 4 test cases)

Because, as I mentioned at the beginning, your code is correct. Now, thanks to testing, you know… for sure… that it’s correct. (And if you have any doubts, you can always add more tests.)

For the record, here are the commands I used to get the output above:

# Start in a new, empty directory.

# Create the source and header files, and fill them with the code:
edit url_encode.hpp
edit url_encode.cpp

# Create the test file, and fill it with the code:
edit url_encode.test.cpp

# Download the Catch2 stuff.
wget https://raw.githubusercontent.com/catchorg/Catch2/devel/extras/catch_amalgamated.hpp
wget https://raw.githubusercontent.com/catchorg/Catch2/devel/extras/catch_amalgamated.cpp

# Compile Catch2 (this will take a while, but you only need to do it once):
g++ -pedantic -Wall -Wextra -c catch_amalgamated.cpp

# --------------------------------------------------------------
# Everything above here only needs to be done once.
# Everything below here has to be done every time you make a change.
# --------------------------------------------------------------

# Each time I changed either the function or the tests:
g++ -pedantic -Wall -Wextra -c url_encode.cpp
g++ -pedantic -Wall -Wextra -c url_encode.test.cpp
g++ -pedantic -Wall -Wextra url_encode.test.o url_encode.o catch_amalgamated.o

# And then to run the tests:
./a.out

Of course, in practice I’d use a makefile or a build tool to automate all this. Not sure what you’re using or even what platform you’re on, but you can probably figure it all out.

Design review

Okay, once you have testing down, fiddling with code becomes trivially easy. If you break anything, the tests will tell you right away, and you can always undo what you did.

std::string_view

The first thing I would suggest is that instead of taking a const std::string& argument, you should use std::string_view.

Why? Because when you do urlEncode("first second"), that string literal is used to construct an actual std::string… which is often not cheap, and may involve memory allocations… and that std::string is then passed (by reference) to the function, and then… simply thrown away afterwards. What a waste.

If you used std::string_view instead, there are no string constructions, and no memory allocations. Instead, only a view of that string literal is passed to the function. Under the hood, only a pointer to the string data stored in the binary is passed along, which is super fast, and cheap.

And if you already have a std::string and want to pass that to the function, passing a view to that string is just as fast as passing a reference. So you lose nothing by switching to std::string_view, and gain a lot.

One warning though: std::string_view is sometimes called a parameter-only type. That means you can use it as a parameter to a function… but you cannot return it. (Well, that’s technically not true, but knowing when it’s safe is complex, expert-level stuff. Better to just not do it, for now.) So even if you change the parameter from std::string const& to std::string_view, you still need to return a std::string.

Avoiding unnecessary allocations

The second thing I would suggest is reserving memory in the output string.

The way your code is written, it theoretically reallocates the entire string every time you add another character (or the "%20"). In other words, when transforming "first second", what happens is:

  1. The first character is 'f'.
    • new memory in b is allocated to hold "f"
    • 'f' is copied into it
  2. The next character is 'i'.
    • new memory in b is allocated to hold "fi"
    • the current content—"f"—is copied to the new memory
    • 'i' is copied to the end of the new memory
    • the old memory is freed
  3. The next character is 'r'.
    • new memory in b is allocated to hold "fir"
    • the current content—"fi"—is copied to the new memory
    • 'r' is copied to the end of the new memory
    • the old memory is freed
  4. The next character is 's'.
    • new memory in b is allocated to hold "firs"
    • the current content—"fir"—is copied to the new memory
    • 's' is copied to the end of the new memory
    • the old memory is freed
  5. The next character is 't'.
    • new memory in b is allocated to hold "first"
    • the current content—"firs"—is copied to the new memory
    • 't' is copied to the end of the new memory
    • the old memory is freed
  6. The next character is a space, so "%20" will be appended.
    • new memory in b is allocated to hold "first%20"
    • the current content—"first"—is copied to the new memory
    • "%20" is copied to the end of the new memory
    • the old memory is freed

… and so on.

That’s 6 allocations, 5 de-allocations, and a ton of copies… and we haven’t even got to "second" yet.

(I’m exaggerating here, because no-one in their right mind would implement std::string to reallocate this much. Usually, each time std::string has to grow, it doesn’t necessarily grow by the minimum amount it needs to to fit the new data. In practice, it will grow by a factor of 2 or 1.5 (depending on the library). That means a lot fewer allocations… but it means wasted memory, so it’s a trade-off.)

Consider this strategy instead. First get the size of the string (a.size()). Then count the number of spaces in the string (std::ranges::count(a, ' ')). Multiply the number of spaces by the size of the replacement string minus one (why minus one? try to reason that out!). Then reserve that much memory in the output string.

So, something like this:

using namespace std::string_view_literals; // to get ""sv

constexpr auto replacement = "%20"sv;

auto b = std::string{};

auto const number_of_spaces = std::ranges::count(a, ' ');

b.reserve(
    a.size()
    + ((replacement.size() - 1) * number_of_spaces)
);

// rest of function is unchanged

Now all those push_back()s and append()s to b won’t need to allocate more memory, because you already pre-allocated all you’ll need.

Don’t use raw loops

Using naked for loops—even range-for loops—is bad practice in modern C++. Instead, you should use algorithms.

At the very least, you should use std::ranges::for_each() (or std::for_each() before C++20). But even better would be to figure out which of the standard algorithms is the best fit.

For now, we’ll just stick with std::ranges::for_each():

auto urlEncode(std::string const& a) -> std::string
{
    auto b = std::string{};

    std::ranges::for_each(a, [&b](auto&& ch)
    {
        if (ch == ' ') {
            b.append("%20");
        }
        else {
            b.push_back(ch);
        }
    });

    return b;
}

As you can see, there’s not really much difference—except you need to get used to the lambda syntax. But under the hood, there are actually a lot of improvements. The compiler can optimize the version with std::ranges::for_each() much easier than the naked-for loop version, for a number of reasons. (In practice, compilers are so freaking good at optimizing, that they’ll do the same job for both, at least for this simple case.) The real improvements will come when you start using more advanced algorithms—for_each() is the most absolute basic algorithm.

Code review

using namespace std;

Never, ever, ever do this. It’s just not worth all the problems it causes.

string  urlEncode(const string &a) {

In C++, the convention is to put the type modifier with the type. C++ is all about the types. In other words:

  • const string &a: this is C-style
  • const string& a: this is C++-style
  • string const& a: this is also C++-style, and has some benefits
    string b;

This is a style thing, so a lot of C++ coders will disagree (it’s not one of the core guidelines, for example), but there is a trend in modern C++ toward replacing that old, C-style of defining variables to using the “(almost) always auto” style.

In the (A)AA style, you would write the above as:

    auto b = std::string{};

This has some more characters, but avoids a lot of problems with the old-school style.

You could also do:

    using namespace std::string_literals; // to get ""s

    auto b = ""s;

If you have a bunch of strings, this can save a lot of typing… but since you only have the single string, it’s probably not worth it.

Incidentally, b is not a great name for a variable. Neither is a. Instead of a, a better name might be original. A better name for b might be transformed or encoded or result… really anything other than just b.

So if I were to rewrite your code, I would start by transforming it to:

auto urlEncode(std::string const& original) -> std::string
{
    auto result = std::string{};

    for (auto ch : original)
    {
        if (ch == ' ') {
            result.append("%20");
        }
        else {
            result.push_back(ch);
        }
    }

    return result;
}

Which, as you can see, isn’t really much change.

Next I might replace the std::string const& with std::string_view. That will give some performance gains.

Then I would probably replace the naked for loop with an algorithm. I’d probably just go with std::ranges::for_each().

The only other thing I might change is putting the magic constants (' ' and "%20") into a named constants. Maybe like so:

auto urlEncode(std::string const& original) -> std::string
{
    constexpr auto unencoded_space = ' ';
    constexpr auto encoded_space = "%20";

    auto result = std::string{};

    for (auto ch : original)
    {
        if (ch == unencoded_space) {
            result.append(encoded_space);
        }
        else {
            result.push_back(ch);
        }
    }

    return result;
}

Put altogether, the changes I would do might looks like:

auto urlEncode(std::string_view original) -> std::string
{
    using namespace std::string_view_literals;

    constexpr auto unencoded_space = ' ';
    constexpr auto encoded_space = "%20"sv;

    auto result = std::string{};

    result.reserve(
        original.size()
        + (
            (encoded_space.size() - 1)
            * std::ranges::count(original, unencoded_space)
        )
    );

    std::ranges::for_each(original, [&result, unencoded_space, encoded_space](auto&& ch)
    {
        if (ch == unencoded_space) {
            result.append(encoded_space);
        }
        else {
            result.push_back(ch);
        }
    });

    return result;
}

It’s quite a bit longer than yours mostly because of the reserve part in the middle, but I think that part is definitely worth it to avoid the repeated allocations.

If I were to go further, I might extract the part that calculates the encoded length out into its own function, because it could be quite useful. I might call it urlEncodedLength(). If I did that, then urlEncode() would simplify to:

auto urlEncode(std::string_view original) -> std::string
{
    auto result = std::string{};
    result.reserve(urlEncodedLength(original));

    std::ranges::for_each(original, [&result](auto&& ch)
    {
        if (ch == unencoded_space) {
            result.append(encoded_space);
        }
        else {
            result.push_back(ch);
        }
    });

    return result;
}

Which is pretty much exactly your function plus one extra line to do the reserve.

Future directions

URL-encode all the things!

URL-encoding is more than just turning spaces into "%20". There are more than a dozen characters that have to be transformed. I would suggest expanding urlEncode() to handle all of them.

The way I would suggest doing it is to first write the tests:

TEST_CASE("Reserved characters are transformed")
{
    CHECK(urlEncode(" ") == "%20");
    CHECK(urlEncode("!") == "%21");
    CHECK(urlEncode("#") == "%23");
    // ... and so on...
}

TEST_CASE("Only the reserved characters get transformed")
{
    CHECK(urlEncode("https://en.wikipedia.org/wiki/Percent-encoding")
        == "https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FPercent-encoding")
    // ... other checks with a mix of reserved/non-reserved characters...
}

They will fail, of course. That’s good; they should; they shouldn’t pass when you haven’t implemented the functionality yet.

Now you can start modifying urlEncode().

As a first pass, you can do a bunch of if tests:

if (ch == unencoded_space) {
    result.append(encoded_space);
}
else if (ch == unencoded_bang) {
    result.append(encoded_bang);
}
else if (ch == unencoded_pound) {
    result.append(encoded_pound);
}
// ... and so on...
else {
    result.push_back(ch);
}

Then, maybe try simplifying with a switch statement.

Then, I suggest getting really adventurous, and creating a map of reserved characters and encoded transformations. Something like:

auto const encoding_map = std::unordered_map<char, std::string>{
    {' ', "%20"},
    {'!', "%21"},
    // ... and so on...
};

Then use that to do the encoding, rather than a bunch of ifs or even a switch. (You can use the same map to do the length calculation, too.)

The neat thing about using a map, rather than a bunch of ifs, is that it’s really easy to change the encoding, or add new transforms. In fact, with a mapping, you could theoretically copy almost the entirety of urlEncode() to a new function that does C-string escaping (like transforming '"' to '\"') or shell-escaping or whatever… all you’d need to do is change the map data to reflect the new encoding.

And then, try replacing the very expensive unordered map with a highly efficient compile-time array of pairs (or tuples). Once you get to this point, you will pretty much be writing the kind of code I’d expect to see from a professional-class C++ coder.

Getting to this point won’t be easy, but if you take small steps, you should manage it. Just remember to always check your work with the tests, to see if you’ve improved things, or introduced bugs.

And you could go even further, to beyond professional-class C++ coder, by writing versions of urlEncode() that work on arbitrary ranges (not just strings and string views), and only reserving when you have at least forward ranges. You could maybe even make a coroutine generator version. That level of C++ mastery will take a long time to work up to.

I’d say don’t worry about going that far just yet, and don’t try to bite off too much challenge too quickly. Just take small steps, incremental improvements. You’ve already got really good code, which suggests you have really good coding instincts. In other words, you’re off to an excellent start. Build up those coding muscles slowly, bit-by-bit. Make small improvements, getting a deep understanding of what you’re improving and why it’s an improvement, each step. That will build you up toward being not just a good C++ coder, but one of the best.

\$\endgroup\$
1
  • \$\begingroup\$ The allocation part is debatable in the particular case due to the small string optimization. I would guess the "first second" is stored on stack. Nevertheless, It is a good point in general. \$\endgroup\$
    – panik
    Aug 26, 2022 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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