Is there a STL/library method to reduce the string size (trim it) in constant time.
In C this this can be done in constant time by just adding the '\0' past the last index.
C++ resize compexity is undefined and mostly likely be O(N)
2 Answers
@SamVarshavchik is being coy in the comments, but it's worth spelling out: in many implementations, including libstdc++, std::string::resize() will reduce the size of a string in constant time, by reducing the length of the string and not reallocating/copying the data: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/basic_string.tcc . The estimate of O(n) is if you increase the size, forcing the string to be reallocated and copied over.
Alternatively, in C++17, std::string_view is rough immutable counterpart to "trimming" a C string by slapping a null byte. It takes a slice of a string (pointer + size) without copying its content, and you can then pass it around to various STL functions or print it from a stream.
std::string hello_world = "hello world"; auto hello = std::string_view(hello_world.data(), 5); std::cout << hello; // prints hello The caveat is that the string_view doesn't own the data, so you can't use it once the original string goes out of scope, and you don't want to modify the original string in a way that might cause it to reallocate.
Comments
The C++17 way, we can achieve the substr operation in O(1).
https://www.modernescpp.com/index.php/c-17-avoid-copying-with-std-string-view
std::string_view do not allocate the memory on heap for large string as well. std::string allocate memory on heap but exception is for std::string size is 15 for MSVC and GCC and 23 for Clang. std::string below above mentioned size are not allocated memory on heap.
std::string::resize's complexity is formallyO(n). Yet, if you were to actually examine your C++ library's implementation when the string's size is reduced, you will be very much surprised as to the actual complexity of that particular operation.