在 C++ 中，有没有可能使用 O(1) 时间复杂度删除字符串的第一个字符？

Question

假设一个字符串

str = "Shajib"

； 我想从“Shajib”中删除第一个字符“S”。删除

str = "hajib"

后。 我想在 C++ 中以 O(1) 时间复杂度执行此任务

如果字符串是

str = "Shajib"

1. str = str.substr(1);

   //O(字符串大小)

2. str.erase(str.begin());

   //O(字符串大小)

我想在 C++ 中以 O(1) 的时间计算这个以重新排列索引。

Answer 1

使用

std::string

是不可能的 - 字符串需要释放为其析构函数中所包含的字符串分配的整块内存，因此需要知道该内存从哪里开始。

std::string

的大多数实现都被设计为分配的内存和包含的字符串的开头相同，因此将指针移动到字符串的开头必然意味着丢失分配的内存。

你可以做的是从字符串创建一个

std::string_view

，然后使用

remove_prefix

方法，这是O(1)，因为

std::string_view

只指向

std::string

包含的字符串，并且不创建副本。但是，这意味着您必须确保您创建的

std::string

对象在您使用字符串视图的整个过程中保持在范围内且位于同一位置，并且您也无法修改使用字符串视图的字符串。

或者，如果在删除第一个字符后移动或修改字符串绝对重要，您可能需要使用

std::dequeue<char>

来代替，这是唯一保证从任一端删除 O(1) 的 C++ 结构