如何在恒定时间内替换字符串中的单个字符并且不使用额外空间？

Question

这不是确切的用例,但它基本上是我想要做的:

let mut username = "John_Smith";
println!("original username: {}",username);
username.set_char_at(4,'.'); // <------------- The part I don't know how to do
println!("new username: {}",username);

我无法弄清楚如何在恒定时间内执行此操作并且不使用额外空间.我知道我可以使用"替换",但替换是O(n).我可以制作角色的矢量,但这需要额外的空间.

我认为你可以创建另一个使用像as_mut_slice这样的指针变量,但这被认为是不安全的.有一种安全的方法可以在恒定的时间和空间中替换字符串中的字符吗？

Answer 1

一般来说 ？对于任何一对角色？不可能.

甲串是不是一个数组.在某些有限的上下文中,它可以实现为数组.

Rust支持Unicode,这带来了一些挑战:

• Unicode代码点可能是0到2 ²⁴之间的整数
• 字形可以由多个Unicode代码点组成

为了表示这一点,Rust字符串(现在)是一个UTF-8字节序列:

• 单个Unicode代码点可能由1到4个字节表示
• 字素可能由1个或更多字节表示(无上限)

因此,"替换性格i"的概念带来了一些挑战:

• 字符的位置i在索引i和字符串的结尾之间,它需要从头开始读取字符串以确切知道哪里,即O(N)
• 将第i个字符就地切换到另一个字符要求两个字符占用完全相同的字节数

一般来说 ？不可能.

在特定且非常特殊的情况下,字节索引是已知的并且字节编码是已知的长度方式一致,可以通过直接修改由于您可能无意中损坏字符串as_mut_bytes而正确标记的字节序列返回来实现unsafe(请记住,这字节序列必须是UTF-8序列).

Answer 2

从Rust 1.27开始，您现在可以使用String::replace_range：

let mut username = String::from("John_Smith");
println!("original username: {}", username);  // John_Smith
username.replace_range(4..5, ".");
println!("new username: {}", username);       // John.Smith

（游乐场）

replace_range将无法使用&mut str。如果范围的大小和替换字符串的大小不同，则必须能够调整基础的大小String，因此&mut String是必需的。但是在您询问（用一个单字节字符替换一个单字节字符）的情况下，它的内存使用和时间复杂度均为O（1）。

有一个类似的方法Vec，Vec::splice。它们之间的主要区别是splice返回一个迭代器，该迭代器生成已删除的项目。