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

user_3586940 0
Viewed 212

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.

string-view c++ string
1 Answers

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.

user_116387180
Related