StringBuffer上insert（0，c）操作的复杂性：它是O（1）吗？ [英] Complexity of insert(0, c) operation on StringBuffer: is it O(1)?

问题描述

我知道StringBuffer的append（）操作花费O（1）时间，与String连接相比，它避免了创建String对象的多个副本的开销。

I am aware that the append() operation for StringBuffer takes O(1) time and it avoids the overhead of creating multiple copies of String objects as compared to String concatenation.

插入（int offset，char c）怎么样？

What about insert(int offset, char c)?

我需要重复调​​用此操作，以便以相反的顺序逐个添加新字符到StringBuffer对象。例如，

I need to repeatedly call this operation so as to add in new characters one by one in a reversed order to the StringBuffer object. For example,

StringBuffer sb = new StringBuffer();
sb.insert(0, 'c');
sb.insert(0, 'b');
sb.insert(0, 'a');
System.out.println(sb.toString()); //prints out "abc";

在理想情况下，每个插入（0，c）应该是O（1）在内部，StringBuffer对象看起来像一个链接的字符列表。我想确认是否真的如此。

In an ideal situation, each insert(0, c) is supposed to be O(1) if internally that StringBuffer object looks like a linked list of characters. I wish to confirm if this is really the case.

推荐答案

嗯，这是一个实现细节 - 但我不会期待它是一个链接的字符列表。我希望它是一个带有长度的 char [] ，基本上 - 就像 ArrayList ，但对于字符。因此，在缓冲区的开头插入一个字符意味着复制所有其余数据。

Well, it's an implementation detail - but I wouldn't expect it to be a linked list of characters. I'd expect it to be a char[] with a length, basically - like an ArrayList, but for characters. So inserting a character at the start of the buffer means copying all the rest of the data.

这是我见过的每个实现的基础 - 链接列表与更常见的实现相比，字符将具有巨大的内存（和分配时间）成本。包含对部分字符串的引用的列表或树结构（请参阅绳子）不会有相同的成本，但我个人没见过 java.lang.StringBuilder 或 java.lang.StringBuffer 使用绳索。

That's been the basis of every implementation I've seen - a linked list of characters would have huge memory (and allocation time) costs compared with the more common implementation. A list or tree structure comprising of references to portions of strings (see "rope") wouldn't have the same costs, but I haven't personally seen a Java implementation of java.lang.StringBuilder or java.lang.StringBuffer which uses ropes.

这篇关于StringBuffer上insert（0，c）操作的复杂性：它是O（1）吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！