STL list.size（）操作 - O（1）还是O（n）？ [英] STL list.size() operation - O(1) or O(n) ?

问题描述

我无法确定STL list.size（）操作

是O（1）还是O（n）。我知道这个列表是一个双向链表，所以如果

size（）操作从头开始，那么算到最后 -

显然它的O（n ）。然而，跟踪插入和删除

并不是那么难，所以可以想象（对我来说）那个size（）可能是
O（1）。对于我的应用程序，列表可能很长（数百万

元素），因此答案会极大地影响我的设计决策。


OR依赖于此编译器？ （我使用的是gcc 3.2.2。）


谢谢，Brett

Hi,

I have had trouble determining whether the STL list.size() operation
is O(1) or O(n). I know the list is a doubly-linked list, so if the
size() operation begins at the head, then counts to the end -
obviously its O(n). However, keeping track of inserts and deletes
isn''t that tough, so its conceivable (to me!) that size() could be
O(1). For my application, the lists can be quite long (millions of
elements), so the answer greatly impacts my design decisions.

OR is this compiler dependent? (I am using gcc 3.2.2.)

Thanks, Brett

推荐答案

" Brett L 。摩尔 <峰; br ********* @ ttu.edu>写了...

"Brett L. Moore" <br*********@ttu.edu> wrote...

我无法确定STL list.size（）操作是否为O（1）或O（n）。我知道列表是一个双向链表，所以如果
size（）操作从头开始，那么算到最后 - 显然它的O（n）。然而，跟踪插入和删除
并不是那么难，所以可以想象（对我来说）那个size（）可能是O（1）。


实际上，标准要求它具有复杂性。

见表65和注释在它之后。

对于我的应用程序，列表可能很长（数百万个元素），所以答案会极大地影响我的设计决策。

OR是这个编译依赖？ （我使用的是gcc 3.2.2。）

I have had trouble determining whether the STL list.size() operation
is O(1) or O(n). I know the list is a doubly-linked list, so if the
size() operation begins at the head, then counts to the end -
obviously its O(n). However, keeping track of inserts and deletes
isn''t that tough, so its conceivable (to me!) that size() could be
O(1).
Actually, the Standard requires it to be of constant complexity.
See table 65 and "Notes" after it.
For my application, the lists can be quite long (millions of
elements), so the answer greatly impacts my design decisions.

OR is this compiler dependent? (I am using gcc 3.2.2.)

不，它不应该依赖于编译器。


Victor

No, it should not be compiler-dependent.

Victor

" Victor Bazarov"

"Victor Bazarov"

" Brett L. Moore"

"Brett L. Moore"

我无法确定STL list.size（）操作是否为O（1）或O（n）。我知道列表是一个双向链表，所以如果
size（）操作从头开始，那么算到最后 - 显然它的O（n）。然而，跟踪插入和删除并不是那么难，所以可以想象（对我来说）那个size（）可能是O（1）。

I have had trouble determining whether the STL list.size() operation
is O(1) or O(n). I know the list is a doubly-linked list, so if the
size() operation begins at the head, then counts to the end -
obviously its O(n). However, keeping track of inserts and deletes
isn''t that tough, so its conceivable (to me!) that size() could be
O(1).

实际上，标准要求它具有恒定的复杂性。
见表65和注释。在它之后。

Actually, the Standard requires it to be of constant complexity.
See table 65 and "Notes" after it.

你确定吗？这将放弃恒定的时间拼接。这不是

与有效STL第4项中的Iread相对应。

Are you sure? This would forsake constant time splicing. This does not
correspond with waht Iread in Effective STL Item 4.

对于我的应用程序，列表可能很长（数百万个元素），因此答案会极大地影响我的设计决策。

OR是否依赖于编译器？ （我正在使用gcc 3.2.2。）

For my application, the lists can be quite long (millions of
elements), so the answer greatly impacts my design decisions.

OR is this compiler dependent? (I am using gcc 3.2.2.)

不，它不应该依赖于编译器。

No, it should not be compiler-dependent.

再次这与我在有效STL项目4中读到的内容。


Fraser。

Again this does not correspond with what I read in Effective STL Item 4.

Fraser.

文章< 12 ******* *******************@posting.google.com> ;, Brett L.

Moore< br ******* **@ttu.edu>写道：


|

|

|我无法确定STL list.size（）操作是否为
|是O（1）或O（n）。我知道列表是一个双向链表，所以如果

| size（）操作从头开始，然后计算到最后 -

|显然它的O（n）。但是，跟踪插入和删除

|不是那么难，所以可以想象（对我来说）那个尺寸（）可能是

| O（1）。对于我的应用程序，列表可能很长（数百万

|元素），所以答案会极大地影响我的设计决策。

|

| OR是否依赖于此编译器？ （我使用的是gcc 3.2.2。）


它依赖于编译器（不幸的是）。


标准说明这个大小（）在所有容器上：


|应该有不变的复杂性


实际上同样的注释适用于成员交换函数，以及

max_size（）成员函数。


应该在上面的引用中并不意味着必须。在标准版中

表示可能，也许不是。


在list :: swap的情况下，有一些实现具有

O（N）大小。我不是积极的，但我认为gcc可能就是其中之一。我相信Dinkumware，我知道Metrowerks有一个复杂的常数

list :: size（）。


主题有多年来，我们一直在争论

comp.std.c ++。您可以尝试在该新闻组中搜索单词

" list"，" size"并且可能是复杂性更多信息。


一个恒定的时间大小（）放弃'的固定时间拼接在

中的一个可能的拼接情况：拼接一些元素来自

另一个清单。如果大小为O（1），则该操作（可能）为O（某些）。

O（某些）上的常量非常小。其他4个拼接

的情况仍为O（1），即使是O（1）大小：


拼接一个来自

从另一个拼接一个

拼接一些来自自己

拼接所有来自其他


-

Howard Hinnant

Metrowerks

In article <12**************************@posting.google.com >, Brett L.
Moore <br*********@ttu.edu> wrote:

| Hi,
|
| I have had trouble determining whether the STL list.size() operation
| is O(1) or O(n). I know the list is a doubly-linked list, so if the
| size() operation begins at the head, then counts to the end -
| obviously its O(n). However, keeping track of inserts and deletes
| isn''t that tough, so its conceivable (to me!) that size() could be
| O(1). For my application, the lists can be quite long (millions of
| elements), so the answer greatly impacts my design decisions.
|
| OR is this compiler dependent? (I am using gcc 3.2.2.)

It is compiler dependent (unfortunately).

The standard says this about size() on all of the containers:

| should have constant complexity

And actually the same note applies to the member swap function, and the
max_size() member function.

The "should" in the above quote does not mean "must". In standardeze
it means "maybe, maybe not".

In the case of list::swap, there are some implementations that have
O(N) size. I''m not positive, but I think gcc may be one of them. I
believe Dinkumware, and I know Metrowerks have a constant complexity
list::size().

The subject has been debated on and off again over the years on
comp.std.c++. You might try a search of that newsgroup for the words
"list", "size" and maybe "complexity" for more information.

A constant time size() forsake''s constant time splicing in one out of
the 5 possible splicing situations: splicing some elements from
another list. That operation is (probably) O(some) if size is O(1).
And the constant on the O(some) is quite small. The other 4 splicing
situations remain O(1) even with an O(1) size:

splice one from self
splice one from other
splice some from self
splice all from other

--
Howard Hinnant
Metrowerks

这篇关于STL list.size（）操作 - O（1）还是O（n）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！