Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Whis is faster for getting a part of the string, std::string::erase or std::string::substr

Tags:

c++

stdstring

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);
}
like image 662
KK_35 Avatar asked May 29 '13 06:05

KK_35


People also ask

What is the time complexity of string erase?

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.

How do I get part of a string in C++?

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.

What is the difference between std::string and string?

There is no functionality difference between string and std::string because they're the same type.

When should you use string_view?

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.


2 Answers

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());
like image 62
Tony Delroy Avatar answered Sep 30 '22 19:09

Tony Delroy


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;
}
like image 44
yijiem Avatar answered Sep 30 '22 17:09

yijiem