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:
- Exactly which test failed (the test for “
urlEncode encodes correctly”).
- Exactly which file and line the failing test starts on (“
url_encode.test.cpp:5”).
- Exactly which file and line the failing assertion is on (“
url_encode.test.cpp:7”).
- What that assertion was (“
CHECK( urlEncode("first second") == "first%20second" )”).
- 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:
- The first character is
'f'.
- new memory in
b is allocated to hold "f"
'f' is copied into it
- 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
- 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
- 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
- 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
- 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-styleconst string& a: this is C++-stylestring 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.
