一个快速std :: list :: size（）*和*一个快速std :: list :: splice（）的解决方案 [英] A solution for a fast std::list::size() *and* a fast std::list::splice()
问题描述
如果我没有完全弄错，std :: list :: size（）
的唯一原因可能是（并且通常是）线性时间操作是因为他们想要
std :: list :: splice（）是一个恒定时间操作，如果你执行后者，那么结果列表的大小如果没有
明确计算新列表的大小。
我在想：如果size（）只是*（br）后的O（n）操作怎么办？ />
a splice（）操作已经执行（并且只有第一次调用大小（）
之后），但是否则为O（1）？
换句话说，在列表类中保留一个大小变量并根据需要更新
，并另外保留一个标志，告诉这个
size变量已验证。只要标志告诉它有效，
list :: size（）就可以返回变量的值。只有当标志
表示它无效时，才会执行O（n）计数，更新
变量，之后标志可以设置为有效。
splice（）操作会在两个列表中将标志设置为无效。
这样splice（）将始终为O （1）和size（）在splice（）之后只有一次O（n）
，否则为O（1）。在所有情况下你都会得到速度优惠
，除非你反复调用splice（）和size（）
（在这种情况下你会得到与大多数情况相同的行为）
当前列表实现，所以它不会像结果那样更糟糕的是。
If I''m not completely mistaken, the only reason why std::list::size()
may be (and usually is) a linear-time operation is because they want
std::list::splice() to be a constant-time operation, and if you execute
the latter, the size of the resulting lists cannot be known without
explicitly counting the sizes of the new lists.
I was thinking: What if size() was an O(n) operation only *after*
a splice() operation has been performed (and only the first time size()
is called after that), but O(1) otherwise?
In other words, keep a size variable in the list class and update
it as necessary, and additionally keep a flag which tells if this
size variable is valid. As long as the flag tells that it''s valid,
list::size() can return the value of the variable. Only if the flag
says it''s invalid, then the O(n) counting will be performed, updating
the variable, after which the flag can be set to valid.
A splice() operation would set the flag to invalid in both lists.
This way splice() will always be O(1), and size() will be O(n) only
once after a splice(), but O(1) otherwise. You will get speed benefits
in all cases except if you alternatively call splice() and size()
repeatedly (in which case you just get the same behavior as in most
current list implementations, so it''s not like the result would be
worse).
推荐答案
10月10日上午9:50，Juha Nieminen< nos ... @ thanks.invalidwrote：
On Oct 10, 9:50 am, Juha Nieminen <nos...@thanks.invalidwrote:
换句话说，保持一个大小列表类中的变量并根据需要更新
，并另外保留一个标志，告诉该
size变量是否有效。只要标志告诉它有效，
list :: size（）就可以返回变量的值。只有当标志
表示它无效时，才会执行O（n）计数，更新
变量，之后标志可以设置为有效。
splice（）操作会在两个列表中将标志设置为无效。
In other words, keep a size variable in the list class and update
it as necessary, and additionally keep a flag which tells if this
size variable is valid. As long as the flag tells that it''s valid,
list::size() can return the value of the variable. Only if the flag
says it''s invalid, then the O(n) counting will be performed, updating
the variable, after which the flag can be set to valid.
A splice() operation would set the flag to invalid in both lists.
所有明智且在我看来都很有用，但有些人已经使用了不会想要它们的列表为了维持这种额外的状态，减慢或增加他们的数据成员大小 - 甚至一点点。
你可以在STL的包装类中轻松提供这个，并且如果您认为其他人想要它，则会发布它。甚至可以提交给
提升....
Tony
All sensible and in my opinion useful, but there are people who''re
already using lists who wouldn''t want them to slow down, or grow their
data member size - even a little bit - to maintain this extra state.
You can easily provide this in a wrapper class around the STL, and
publish it if you think others would want it. Maybe even submit it to
boost....
Tony
在文章< 47 *********************** @ news.song.fi>，
没有**** @ thanks.inva 盖子说...
In article <47***********************@news.song.fi>,
no****@thanks.invalid says...
如果我没有完全弄错的话，std :: list :: size（）
可能（通常是）线性时间操作的唯一原因是因为他们想要
std :: list :: splice（）是一个恒定时间操作，如果你执行后者，那么如果没有
明确计算尺寸，则无法知道结果列表的大小新的清单。
我在想：如果size（）只是*（*）$ * *
a splice（）操作后怎么办？已执行（并且只有第一次尺寸（）
之后被调用），但O（1）否则？
If I''m not completely mistaken, the only reason why std::list::size()
may be (and usually is) a linear-time operation is because they want
std::list::splice() to be a constant-time operation, and if you execute
the latter, the size of the resulting lists cannot be known without
explicitly counting the sizes of the new lists.
I was thinking: What if size() was an O(n) operation only *after*
a splice() operation has been performed (and only the first time size()
is called after that), but O(1) otherwise?
这是实现std :: list的完全合法的方式。当然，这不是必需的b $ b，但如果你愿意，你可以这样做。再说一次，你一般都不能指望它是
。
-
后来，
杰瑞。
宇宙是自己想象的虚构。
This is a perfectly legitimate way of implementing std::list. It''s not
required, of course, but you can do it if you want to. Then again, you
can''t count on it in general.
--
Later,
Jerry.
The universe is a figment of its own imagination.
到*********** @ yahoo.co.uk 写道：
所有明智且在我看来都很有用，但有些人已经使用了不希望他们放慢$ b $的
b
All sensible and in my opinion useful, but there are people who''re
already using lists who wouldn''t want them to slow down
此解决方案只会加快速度。另一种方法是使用
当前的典型解决方案，这是一个O（n）size（）函数。
This solution would only speed it up. The alternative is to use
the current typical solution, which is an O(n) size() function.
或增加他们的数据成员大小
or grow their data member size
列表元素的大小根本不会改变。只有std :: list类的
大小会增长一个标志和一个大小
变量。几乎没有灾难性的（尤其是考虑到它需要多少加速大小（））。
The size of the list elements would not change at all. Only the
size of the std::list class would grow by one flag and one size
variable. Hardly catastrophical (especially taking into account
how much it speeds up size()).
您可以在包装类中轻松提供此功能围绕STL
You can easily provide this in a wrapper class around the STL
我可以吗？我将不得不重新实现大多数列表成员函数。
这不是一项简单的任务。
Can I? I would have to reimplement most of the list member functions.
Not a trivial task.
这篇关于一个快速std :: list :: size（）*和*一个快速std :: list :: splice（）的解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
