h*****n
发帖数: 209 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: hanuman (神猴), 信区: JobHunting
标 题: 设计一个string class，是应该用linked list还是array?
发信站: BBS 未名空间站 (Sun Oct 3 23:03:21 2010, 美东)
有两种方案，一种是用array来存放字符串，另一种是用linked list来存放字符串。
用array的话，访问string里面的某个字符会很快，但是执行两个字符串相加操作的时
候会比较慢。
用linked list的话，它访问string的某个字符比较慢，但执行字符串相加操作会比较
快。
那这个string class到底如何设计比较好呢？ | g*****g
发帖数: 34805 | 2 Of course array, and + operation is not faster with linked list,
as you have to duplicate the storage.
If A = B + C, A shouldn't share any storage with B or C
【在 h*****n 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: hanuman (神猴), 信区: JobHunting
: 标 题: 设计一个string class，是应该用linked list还是array?
: 发信站: BBS 未名空间站 (Sun Oct 3 23:03:21 2010, 美东)
: 有两种方案，一种是用array来存放字符串，另一种是用linked list来存放字符串。
: 用array的话，访问string里面的某个字符会很快，但是执行两个字符串相加操作的时
: 候会比较慢。
: 用linked list的话，它访问string的某个字符比较慢，但执行字符串相加操作会比较
: 快。
: 那这个string class到底如何设计比较好呢？
| s******e
发帖数: 493 | 3 It really depends on how often you want to do those operations and which
language.
If C/C++, or maybe any languages where array must be in a consective memory
space, as you said linked list will be faster on "+" operation. but random
access will be slow. I will vote for linked list if you must choose from two.
Or you can think from a different direction, like java, create a string
constant pool, and make string objects immutable. | w****i
发帖数: 964 | 4 Using linked list to stored string is really an unusual practice.
a bit shocked to see this idea. | g*****g
发帖数: 34805 | 5 As I say, you can't share storage between 2 string instances
unless it's the same immutable string.
If you want to use a linked list, you have to duplicate the
linked list, which negate all the benefits of faster concatenation.
And if you don't, let's say String a = b + c, now you make a change
to c, a is changed too, probably not what you want.
memory
two.
【在 s******e 的大作中提到】
: It really depends on how often you want to do those operations and which
: language.
: If C/C++, or maybe any languages where array must be in a consective memory
: space, as you said linked list will be faster on "+" operation. but random
: access will be slow. I will vote for linked list if you must choose from two.
: Or you can think from a different direction, like java, create a string
: constant pool, and make string objects immutable.
| t****u
发帖数: 8614 | 6 为啥要re-invent the wheel？
直接用std::string不行吗？
如果需要一些其它功能，做个wrapper class，弄个std::string的member不就行了。
【在 h*****n 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: hanuman (神猴), 信区: JobHunting
: 标 题: 设计一个string class，是应该用linked list还是array?
: 发信站: BBS 未名空间站 (Sun Oct 3 23:03:21 2010, 美东)
: 有两种方案，一种是用array来存放字符串，另一种是用linked list来存放字符串。
: 用array的话，访问string里面的某个字符会很快，但是执行两个字符串相加操作的时
: 候会比较慢。
: 用linked list的话，它访问string的某个字符比较慢，但执行字符串相加操作会比较
: 快。
: 那这个string class到底如何设计比较好呢？
| t****u
发帖数: 8614 | 7 这个东西，就算要reinvent the wheel。
最简单的方法就是refer to std::string，那边是array的。
如果linked list好，早就一大堆library用linked list来实现string了。
这些都是前人的智慧总结。
【在 g*****g 的大作中提到】
: As I say, you can't share storage between 2 string instances
: unless it's the same immutable string.
: If you want to use a linked list, you have to duplicate the
: linked list, which negate all the benefits of faster concatenation.
: And if you don't, let's say String a = b + c, now you make a change
: to c, a is changed too, probably not what you want.
:
: memory
: two.
| n******n
发帖数: 12088 | 8 托老也来这里？不是都转型了么？呵呵。
肯定是面试题。
【在 t****u 的大作中提到】
: 为啥要re-invent the wheel？
: 直接用std::string不行吗？
: 如果需要一些其它功能，做个wrapper class，弄个std::string的member不就行了。
| d*****u
发帖数: 43 | 9 一个字节的字符，耗用一个或两个指针，这样的字符串要用多少内存？
谁要用这样的字符串？ |
|
