Main Suggestion
I think it will be useful to have couple of overloaded functions, one for working with const std::string
s and one for regular std::string
s.
With a const std::string
, pay the cost of making a copy, reversing the copy, and returning the copy.
With a std::string
, you can avoid all the above costs. You make all modifications to the string in place.
std::string& reverse(std::string& str)
{
// Don't pay the cost of making copies for regular strings.
std::reverse(str.begin(), str.end());
int size = str.size();
int start = 0;
int end = 0;
while (end != size + 1) {
if (str[end] == '.' || end == size) {
std::reverse(str.begin() + start, str.begin() + end);
start = end + 1;
}
++end;
}
return str;
}
std::string reverse(std::string const& str)
{
std::string copy = str;
return reverse(copy);
}
Now, you can reverse regular std::string
s as well as temporary std::string
s, i.e. const std::string
s, while paying the cost of making copies only for const std::string
s.
int main()
{
std::string examples[] = {
"hello.world",
"com.domain.something",
"..a"
};
int size = sizeof(examples) / sizeof(examples[0]);
for (int i = 0; i < size; ++i) {
std::cout << examples[i] << " -> " << reverse(examples[i]) << std::endl;
}
std::cout << "abc.com" << " -> " << reverse("abc.com") << std::endl;
return 0;
}
Use right type names
Don't use int
where other type names are more appropriate. You can use auto
to avoid such issues. I would recommend replacing
int size = str.size();
int start = 0;
int end = 0;
with
auto size = str.size();
decltype(size) start = 0;
decltype(size) end = 0;
Using std::reverse
vs hand crafted function to reverse a string
You can reverse a string or part of the string using std::reverse
like you have in your code:
std::reverse(str.begin(), str.end());
and
std::reverse(str.begin() + start, str.begin() + end);
You can also reverse a string or part of the string using a hand crafted function:
void reverse_string(std::string& str, size_t start, size_t end)
{
for ( --end; start <= end; ++start, --end )
{
char c = str[start];
str[start] = str[end];
str[end] = c;
}
}
and use it as:
reverse_string(str, 0, str.size());
and
reverse_string(str, start, end);
I noticed that the hand crafter version performs 50% faster than std::reverse
.
Sample program:
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
#include <cstdlib>
void timeFunction(void (*fun)(int, std::string&), int N, std::string& str)
{
clock_t start = std::clock();
fun(N, str);
clock_t end = std::clock();
double secs = 1.0*(end-start)/CLOCKS_PER_SEC;
std::cout << "Time taken: " << secs << std::endl;
}
void test_reverse_string_1(int N, std::string& str)
{
for (int n = 0; n < N; ++n )
{
std::reverse(str.begin(), str.end());
}
}
void reverse_string(std::string& str, size_t start, size_t end)
{
for ( --end; start <= end; ++start, --end )
{
char c = str[start];
str[start] = str[end];
str[end] = c;
}
}
void test_reverse_string_2(int N, std::string& str)
{
for (int n = 0; n < N; ++n )
{
reverse_string(str, 0, str.size());
}
}
int main(int argc, char** argv)
{
int N = atoi(argv[1]);
std::string str = argv[2];
timeFunction(test_reverse_string_1, N, str);
timeFunction(test_reverse_string_2, N, str);
return 0;
}
Command to build (under Linux, using g++ 4.8.4) :
g++ -Wall -std=c++11 socc.cc -o socc
Execution and ouput:
>> ./socc 1000000 "The quick brown fox jumped over the lazy dog."
Time taken: 0.484501
Time taken: 0.297132
>> ./socc 4000000 "The quick brown fox jumped over the lazy dog."
Time taken: 1.92211
Time taken: 1.02913
Standard Disclaimer
Your mileage may vary depending on your compiler and run time environment.