设计一个string class，是应该用linked list还是array? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

设计一个string class，是应该用linked list还是array?

设计一个string class，是应该用linked list还是array?# Programming - 葵花宝典

e*r2010-10-03 07:10

1 楼

本人现在F1 OPT, 在05／2016 过期。结婚一年多才开始准备申请婚姻绿卡，15年六月
份提交I485，但是USCIS 的状态自从八月份后就没有变化过。现在听说因为San
Bernardino shooting 所有的婚姻绿卡审查都会延迟。
请问现在我可以申请并且应该开始准备申请H1B 或者EAD吗？唯一是担心五月份以后就
不允许工作了，还有就是担心会影响找工作。
另外，如果在USCIS核准我的绿卡时我们结婚满两年了，是不是它一定会自动发放十年
的绿卡而不是临时绿卡了？
多谢！

l*e2010-10-03 07:10

2 楼

你最近变得比较敏锐，吃了什么药？能不能介绍一下经验。

s*e2010-10-03 07:10

3 楼

我年纪不大，但是发生在我身上的事不少，得过的病也不少，你们说的那些个让人觉得
可怕的，比如自闭，比如抑郁症我都得过，但是我从来就没想过自杀，不是说我有坚强
，是我觉得好死还不如赖活着，我这人太惜命
说自闭，我曾经自闭了两年，那是百分百的自闭症，但是我没吃过一次药，没看过一次
医生，我能康复是因为我觉得，够了！把自己糟蹋的够了
为什么自闭，是先是高考失败，而后就是恋爱告吹，那个年纪对于自尊心极强的我来说
，那种打击是我不能承受的，是我怎么都想不明白的，于是天空在我眼里就忽然的漆黑
一片
就是一夜之间的时间，我觉得这个世界对我来说，在么有什么能让我觉得有趣，觉得有
希望的事情了，我再也不想看到任何一个人，我只是想在自己的世界中，慢慢的分析和
回味这一切，究竟是什么造成的
把门一关，不到万不得已从不出屋，家里的人吓坏了，我很平静的说，让我一个人想想
，我为什么会变成这个样子，我不会疯也不会傻放心
整整两年零六天，我每天都在挣扎和思考，从开始的怎么都想不明白，到后来的已经无
所谓明白不明白，再到后来觉得自己真傻，自闭症不需要治疗的，最需的就是安静和自由

h*n2010-10-03 07:10

4 楼

【以下文字转载自 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到底如何设计比较好呢？

e*r2010-10-03 07:10

5 楼

查了一下，好像需要申请EAD C9? 大概需要多久能收到EAD卡？多谢了！

m*e2010-10-03 07:10

6 楼

谁，谁吃药了？

【在 l*********e 的大作中提到】

: 你最近变得比较敏锐，吃了什么药？能不能介绍一下经验。

g*g2010-10-03 07:10

7 楼

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到底如何设计比较好呢？

l*e2010-10-03 07:10

8 楼

你啊，马宏波

【在 m*******e 的大作中提到】

: 谁，谁吃药了？

s*e2010-10-03 07:10

9 楼

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*F2010-10-03 07:10

10 楼

你咋知道他姓马？

【在 l*********e 的大作中提到】

: 你啊，马宏波

w*i2010-10-03 07:10

11 楼

Using linked list to stored string is really an unusual practice.
a bit shocked to see this idea.

m*e2010-10-03 07:10

12 楼

我前几天吃了几片儿银翘

【在 l*********e 的大作中提到】

: 你啊，马宏波

g*g2010-10-03 07:10

13 楼

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.

l*e2010-10-03 07:10

14 楼

他姓马，你姓王

【在 w****F 的大作中提到】

: 你咋知道他姓马？

t*u2010-10-03 07:10

15 楼

为啥要re-invent the wheel？
直接用std::string不行吗？
如果需要一些其它功能，做个wrapper class，弄个std::string的member不就行了。

【在 h*****n 的大作中提到】

w*F2010-10-03 07:10

16 楼

那你姓李？

【在 l*********e 的大作中提到】

: 他姓马，你姓王

t*u2010-10-03 07:10

17 楼

这个东西，就算要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.

m*e2010-10-03 07:10

18 楼

错了，姓田

【在 w****F 的大作中提到】

: 那你姓李？

n*n2010-10-03 07:10

19 楼

托老也来这里？不是都转型了么？呵呵。
肯定是面试题。

【在 t****u 的大作中提到】

: 为啥要re-invent the wheel？
: 直接用std::string不行吗？
: 如果需要一些其它功能，做个wrapper class，弄个std::string的member不就行了。

w*F2010-10-03 07:10

20 楼

越来越深凹了
不懂了

【在 m*******e 的大作中提到】

: 错了，姓田

d*u2010-10-03 07:10

21 楼

一个字节的字符，耗用一个或两个指针，这样的字符串要用多少内存？
谁要用这样的字符串？

m*e2010-10-03 07:10

22 楼

男人要有长度和广度

【在 w****F 的大作中提到】

: 越来越深凹了
: 不懂了

j*y2010-10-03 07:10

23 楼

我呢我呢？

【在 l*********e 的大作中提到】

: 他姓马，你姓王

m*e2010-10-03 07:10

24 楼

刘

【在 j**********y 的大作中提到】

: 我呢我呢？