I am retrieving and storing a part of the string for which I can use either std::string::erase or std::string::substr.
I would like to know which of the following approach is faster (less time to complete) and efficient (less memory allocation/reallocation). Also, any info about how the memory is allocated/reallocated by the erase and substr would be very helpful. Thanks!
std::string nodeName("ABCD#XYZ#NodeName");
const std::string levelSeparator("#");
Option 1: Using std::string::substr
std::string::size_type nodeNameStartPosition = nodeName.rfind(levelSeparator);
if (nodeNameStartPosition != std::string::npos)
{
nodeNameStartPosition += levelSeparator.length();
nodeName = nodeName.substr(nodeNameStartPosition);
}
Option 2: Using std::string::erase
std::string::size_type nodeNameStartPosition = nodeName.rfind(levelSeparator);
if (nodeNameStartPosition != std::string::npos)
{
nodeNameStartPosition += levelSeparator.length();
nodeName = nodeName.erase(0, nodeNameStartPosition);
}
Its time complexity is O(1). erase(): Deletes a substring of the string. Its time complexity is O(N) where N is the size of the new string.
In C++, a substring is a segment of a string, and you use the substr() function to extract a substring from a specified string. This substr() function extracts a substring from a string beginning at the specified position and going up to the length specified in characters from the starting position.
There is no functionality difference between string and std::string because they're the same type.
string_view is useful when you want to avoid unnecessary copies. String_views are less memory-intensive to construct and copy. The creation of string_view from literals does not require a dynamic allocation.
If you really care, always benchmark.
You don't need to do a self assignment ala nodeName = nodeName.erase(0, nodeNameStartPosition);
- just use:
nodeName.erase(0, nodeNameStartPosition);
This works because erase
already modifies the string nodeName
in place.
Any speed difference is overwhelmingly likely to be in erase
's favour, as there's definitely no memory allocation going on - just the copying within the buffer. substr()
is likely to create a temporary string - you can tell that from the by-value return type in the std::string::substr function prototype:
string substr (size_t pos = 0, size_t len = npos) const;
This by-value return may require heap allocation unless short-string optimisation kicks in. I'm sceptical whether optimisers can remove those overheads.
Separately, nodeNameStartSeparator
is clearly a misnomer as you're pointing it at the start of the level separator. It all boils down to:
std::string::size_type levelSeparatorPos = nodeName.rfind(levelSeparator);
if (levelSeparatorPos != std::string::npos)
nodeName.erase(0, levelSeparatorPos + levelSeparator.length());
Here is a benchmark which includes erase and substr operations for string, the use case is a little bit different as I am trying to remove 1 letter from a word for every letters in the word. Erase turns out to be faster than substr in this case.
#include <chrono>
#include <iostream>
#include <sstream>
using namespace std;
static const string STR(1000, 'a');
/*
* remove 1 letter from STR to create a shorter string
* every letter will be a candidate to remove
* eg: bcda -> cda, bda, bca, bcd
*
* result:
*
* stream way takes 63394.1 us
* append way takes 21007.5 us
* erase way takes 199.563 us
* substr way takes 416.735 us
*/
void stream_way() {
for (int skip = 0; skip < STR.size(); ++skip) {
stringstream ss;
for (int i = 0; i < STR.size(); ++i) {
if (i != skip) {
ss << STR[i];
}
}
(void) ss.str();
}
}
void append_way() {
for (int skip = 0; skip < STR.size(); ++skip) {
string s;
for (int i = 0; i < STR.size(); ++i) {
if (i != skip) {
s += STR[i];
}
}
(void) s;
}
}
void erase_way() {
for (int i = 0; i < STR.size(); ++i) {
string copy = STR;
copy.erase(i, 1);
(void) copy;
}
}
void substr_way() {
for (int first_part = 0; first_part < STR.size(); ++first_part) {
string s = STR.substr(0, first_part) + STR.substr(first_part + 1, STR.size() - first_part - 1);
(void) s;
}
}
int main() {
auto start = chrono::steady_clock::now();
stream_way();
auto end = chrono::steady_clock::now();
chrono::duration<double, micro> diff = end - start;
cout << "stream way takes " << diff.count() << " us\n";
start = chrono::steady_clock::now();
append_way();
end = chrono::steady_clock::now();
diff = end - start;
cout << "append way takes " << diff.count() << " us\n";
start = chrono::steady_clock::now();
erase_way();
end = chrono::steady_clock::now();
diff = end - start;
cout << "erase way takes " << diff.count() << " us\n";
start = chrono::steady_clock::now();
substr_way();
end = chrono::steady_clock::now();
diff = end - start;
cout << "substr way takes " << diff.count() << " us\n";
return 0;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With