Is there any possible way to remove the 1st character of a String using O(1) time complexity in C++?

Question

Suppose a String str = "Shajib"; I want to remove the first character 'S' from "Shajib". After removing str = "hajib". I want to perform this task in O(1) Time complexity in C++

If a string is str = "Shajib"

1. str = str.substr(1); //O(string size)
2. str.erase(str.begin()); //O(string size)

I want to calculate this in O(1) time in C++ to rearrange the index.

Answer 1

This isn't possible using a std::string - the string needs to deallocate the entire piece of memory allocated for the contained string in it's destructor and therefore needs to know where that memory starts. Most implementations of std::string are designed such that the start of the allocated memory and the start of the contained string are the same (which keeps the size of the std::string object small), so moving the pointer to the start of the string would necessarily mean losing track of the allocated memory.

What you can do is create a std::string_view from the string and then use the remove_prefix method, which is O(1) because std::string_view only points to the string contained with the std::string and does not create a copy. However, that means you would have to make sure that the std::string object you created it from is kept in scope and in the same location for the entire time that you're using the string view, and you also can't modify the string using the string view.

Alternatively, if it's absolutely vital that the string be moved or be modified after removing the first character, you may want to use a std::deque<char> instead, which is the only C++ structure which guarantees O(1) deletion from either end.