size_type size() const {
size_type __result = 0;
distance(begin(), end(), __result);
return __result;
}
在sgi stl的实现版本中看到关于size member的实现。
这里的distance是一个全局函数。
对于random_access iterator 而言是两个迭代器相减,具有O(1)的复杂度,而对于其他类型的迭代器则是++first到last的形式,具有O(n)的复杂度。
Why islist<>::size()linear time?
Thesize()member function, forlistandslist, takes time proportional to the number of elements in the list. This was a deliberate
tradeoff. The only way to get a constant-timesize()for linked lists would be to maintain an extra member variable containing the list's size. This would require taking extra time to update that variable (it would makesplice()a linear
time operation, for example), and it would also make the list larger. Many list algorithms don't require that extra word (algorithms that do require it might do better with vectors than with lists), and, when it is necessary to maintain an explicit size count,
it's something that users can do themselves.
This choice is permitted by the C++ standard. The standard says thatsize()"should" be constant time, and "should" does not mean the same thing as "shall". This is the officially recommended
ISO wording for saying that an implementation is supposed to do something unless there is a good reason not to.
One implication of linear timesize(): you should never write
if (L.size() == 0) ...
Instead, you should write
if (L.empty()) ...
在VC下面是保存了一个size_t的静态变量来保存list中的size,但是这样做就需要在插入删除的操作中进行这个变量的维护,在例如splice的操作中复杂度将达到O(n)。这样对于list中插入和删除都是const complexity的特性就不符合了。
分享到:
相关推荐
Computational.Complexity.A.Modern.Approach
The C++ Standard Library A Tutorial and Reference (2nd Edition)+cppstdlib-code.zip C++标准库(第二版)英文版.pdf 非扫描版+源代码 Prefaceto the SecondEdition xxiii Acknowledgments for the Second...
18 C++ Network Programming, Volume 1: Mastering Complexity with ACE and Patterns 19 C++ Network Programming, Volume 2: Systematic Reuse with ACE and Frameworks 7. 杂项 20 Thinking in C++, Volume 1: ...
18 C++ Network Programming, Volume 1: Mastering Complexity with ACE and Patterns 19 C++ Network Programming, Volume 2: Systematic Reuse with ACE and Frameworks 7. 杂项 20 Thinking in C++, Volume 1: ...
18 C++ Network Programming, Volume 1: Mastering Complexity with ACE and Patterns 19 C++ Network Programming, Volume 2: Systematic Reuse with ACE and Frameworks 7. 杂项 20 Thinking in C++, Volume 1: ...
18 C++ Network Programming, Volume 1: Mastering Complexity with ACE and Patterns 19 C++ Network Programming, Volume 2: Systematic Reuse with ACE and Frameworks 7. 杂项 20 Thinking in C++, Volume 1: ...
18 C++ Network Programming, Volume 1: Mastering Complexity with ACE and Patterns 19 C++ Network Programming, Volume 2: Systematic Reuse with ACE and Frameworks 7. 杂项 20 Thinking in C++, Volume 1: ...
18 C++ Network Programming, Volume 1: Mastering Complexity with ACE and Patterns 19 C++ Network Programming, Volume 2: Systematic Reuse with ACE and Frameworks 7. 杂项 20 Thinking in C++, Volume 1: ...
2 Introduction to C++ and the Standard Library 7 2.1 History of the C++ Standards . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 Common Questions about the C++11 Standard . . . . . . ...
A Low Complexity Algorithm for Generating Turbo.pdf
Training times can be very long depending on the complexity of the environment. [This repo](https://github.com/matthiasplappert/keras-rl-weights) provides some weights that were obtained by running ...
关于计算复杂性理论的教科书草案。 涵盖基本的复杂性类,具体计算模型的下限和一些高级主题。
He shows you how to tame C++'s complexity, cut through its vast array of paradigms, take back control over your code--and get far better results. If you're a long-time C++ developer, this book will ...
1. ON THE COMPLEXITY OFFULLERENES AND NANOTUBES 1 ′ ˇ ′ MilanRandic, Xiaofeng Guo,DejanPlavsicand Alexandru T.Balaban 1. Introduction . . .......................... 1 2. On the ...
python库。 资源全名:complexity-0.1.2.tar.gz
Addison.Wesley.Adaptive.Project.Framework.Managing.Complexity.in.the.Face.of.Uncertainty.Jan.2010.rar
Programming.Scala_Tackle.Multi-Core.Complexity.on.the.Java.Virtual.Machine[2009][EN][PDF] Programming Scala: Tackle Multi-Core Complexity on the Java Virtual Machine by Venkat Subramaniam Scala is ...
TMathEngine allows to evaluate mathematical expressions of any complexity. It supports addition, subtraction, multiplication, division, parenthesis, and logical operations. Example: Command: (134....
A Conceptual Perspective
Domain.Driven.Design.Tackling.Complexity.In.The.Heart.Of.Software领域驱动设计