Time complexity of converting std::string to std::string_view

Question

Minimal Reproducible example:

using namespace std;

#include<string>
#include<string_view>
#include<iostream>

int main()
{
    string s = "someString";
    string_view sV = string_view(s);
    string_view sVTwo = string_view(begin(s), end(s));
    return 0;
}

Is the time complexity of creating the string_view sV linear relative to the number of chars in the string s or is it irrelevant how long the string s is? Likewise, is the time complexity of the construction of sVTwo linear or constant depending on how many chars are in the string?

The reason I am confused is I cannot tell which of these constructors here: https://en.cppreference.com/w/cpp/string/basic_string_view/basic_string_view is being used to construct the string.

Doesn't the link state that the complexity is constant? A std::string knows its own length since it has a const size() function. It's when a raw char * is used where the length of the string comes into play, since a character pointer knows nothing about the length of the string, and must iterate until a null is reached. — PaulMcKenzie
– PaulMcKenzie, Commented Oct 17, 2021 at 3:19
It's not using any of the string_view constructors. It's using the "string to string_view" conversion operator. — Raymond Chen
– Raymond Chen, Commented Oct 17, 2021 at 3:19
Protip: never put using namespace std; above #include directives, and ideally never use using namespace, instead import specific type-names. — Dai
– Dai, Commented Oct 17, 2021 at 3:19

康桓瑋 · Accepted Answer · 2021-10-17 03:31:54Z

8

Is the time complexity of creating the string_view sV linear relative to the number of chars in the string s or is it irrelevant how long the string s is?

string_view(s) will call the string's operator std::string_view(), which is equivalent to return string_view(data(), size()), and since string's data() and size() are both O(1), so the complexity has nothing to do with the length of the string.

Likewise, is the time complexity of the construction of sVTwo linear or constant depending on how many chars are in the string?

It will call string_view(It first, End last) and use std::to_address(first) and last - first to initialize the string_view's member variables. Since the former and pointer arithmetic are both constant time, this is also constant time. Please note that this function was introduced in C++20, and calling string_view(begin(s), end(s)) in C++17 is ill-formed.

edited Oct 17, 2021 at 3:31

answered Oct 17, 2021 at 3:19

康桓瑋

46.8k5 gold badges69 silver badges135 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Time complexity of converting std::string to std::string_view

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related