Reverse string by separator

Question

Here is problem:
There is string (domain) divided by dots (like www.part1.partN.com)
Need to build reversed by dot string (like com.partN.part1.www)
Both strings are utf-8 encoded

My solution:

std::string reverseHost(const std::string& host)
{
 std::string ret;
 ret.reserve(host.size());
 size_t tail = host.size();
 size_t head = host.find_last_of('.');
 while (head != std::string::npos)
 {
 ret.append(host.c_str() + head + 1, tail - head - 1);
 ret += '.';
 tail = head;
 head = host.find_last_of('.', tail - 1);
 }
 ret.append(host.c_str(), tail);
 return ret;
}

Need to improve speed (or advice how to improve), raw memory and other tricks allowed. ty.

• SPD: what if the input string is just a ".", should you handle such case?

Answer 1

You've misspelt std::size_t.

Apart from that, the code seems reasonably straightforward if you always need to return a copy.

A two-pass algorithm (reverse the whole string, then reverse each of the individual components) might be faster, because you can operate in-place, without having to create a new string. Of course, you'll only get the speed benefit if the caller doesn't need to retain the original (pass by value, and use std::move to control copying).

Answer 2

If you're using Boost, one readable solution is:

#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/classification.hpp>
std::string reverseHost(const std::string& host)
{
 std::vector<std::string> parts;
 boost::algorithm::split(parts, host, boost::is_any_of("."));
 std::reverse(parts.begin(), parts.end());
 return boost::algorithm::join(parts, ".");
}

In short, we split the input into parts using dot as a delimiter, reverse them, and join in reverse order.

However, this is not designed with performance in mind. A faster alternative is likely the following:

std::string reverseHost(const std::string& str)
{
 std::string rev(str.crbegin(), str.crend());
 const std::size_t len = rev.size();
 for (std::size_t j, i = 0; i < len; ++i)
 {
 j = i;
 while ((i < len) && (rev[i] != '.'))
 ++i;
 std::reverse(rev.begin() + j, rev.begin() + i);
 }
 return rev;
}

• goldstar: i've tested your solution 100 launches with 1m iterations each. your solution ~148 ms (per 1m) mine ~95 ms
• goldstar: also boost is about ~700ms in same benchmark xD
• Juho: @goldstar I made a small optimization, but perhaps it won't matter much. A second step could be to try another method instead of std::reverse.
• Loki Astari: @goldstar: Is this function really a hotspot that needs such micro optimization? Unlikely; if not then go with the clearer solution. Which Juho has provided (the copy revered, then reverse each word) is the classic implementation. If this is the hot spot (you need the data to prove that), then go with your optimized version and add the extra documentation to make sure maintainers know that it needs to be optimized. But note the cost of this version can be optized in several ways. Do the work in place or making sure the space is pre-allocated (as in your version).
• goldstar: @MartinYork, yep, this function is bottleneck and part of library so i need optimize it as well.