标准容器的复杂性保证是什么？ [英] What are the complexity guarantees of the standard containers?

问题描述

显然，标准容器提供了某种形式的保证。

什么类型的保证和什么是不同类型的容器之间的区别？ p>

使用 SGI页面（约 STL ）我想出了这个：

 容器类型：
 ================ 
容器：
向前容器
反向容器
随机访问容器
序列
前插入序列
后插入序列
关联容器
简单关联容器
对关联容器
已排序关联容器
多关联容器
 
映射到标准容器的容器类型
 ============================= ================ 
 
 std :: vector：Sequence Back Sequence Forward / Reverse / Random Container 
 std :: deque：Sequence Front /返回序列前进/后退/随机容器
 std :: list：序列前/后序列前进/后退容器
 std :: set：Sorted / Simple / Unique关联容器向前容器
 std： ：map：Sorted / Pair / Unique Associative Container Forward Container 
 std :: multiset：Sorted / Simple / Multiple Associative Container Forward Container 
 std :: multimap：Sorted / Pair / Multiple Associative Container Forward Container 
 
 
集装箱保证：
 ===================== 
 
 Simp 
或
 For Rev Rand前面后面Assoc排序多个
 Cont：Cont：Cont Cont：Sequ：Sequ：Sequ：Cont：Cont：Cont：
复制Const：O $ b Fill Const：O（n）
 begin（）O（1）
 end（）O（1）
 rbegin （1）
 front（）O（1）
 push_front（）O（1）
 pop_front（）O（1）
 push_back b pop_back（）O（1）
 Insert（）O（ln（n））
插入：fill O（n）
插入： + n）
 size（）O（n）
 swap（）O（1）
清除键O（ln（n））
擦除元素O $ b擦除范围O（ln（n）+ S）
 count（）O（log（n）+ k）
 find （ln（n））
下边界/上边界O（ln（n））
等式O（n）
等式O（n）
元素访问O 
  

解决方案

从这里开始：复杂性规范。然后阅读该网站上的所有容器类型，并查看所述的复杂性要求。

希望这有助于！

Apparently ;-) the standard containers provide some form of guarantees.

What type of guarantees and what exactly are the differences between the different types of container?

Working from the SGI page (about STL) I have come up with this:

Container Types:
================
Container:
    Forward Container
        Reverse Container
            Random Access Container
    Sequence
        Front Insert Sequence
        Back  Insert Sequence
    Associative Container
        Simple   Associative Container
        Pair     Associative Container
        Sorted   Associative Container
        Multiple Associative Container

Container Types mapped to Standard Containers
=============================================

std::vector:    Sequence    Back        Sequence                    Forward/Reverse/Random Container
std::deque:     Sequence    Front/Back  Sequence                    Forward/Reverse/Random Container
std::list:      Sequence    Front/Back  Seuqence                    Forward/Reverse Container
std::set:       Sorted/Simple/Unique    Associative Container       Forward Container
std::map:       Sorted/Pair/Unique      Associative Container       Forward Container
std::multiset:  Sorted/Simple/Multiple  Associative Container       Forward Container
std::multimap:  Sorted/Pair/Multiple    Associative Container       Forward Container


Container Guarantees:
=====================

                                                                                  Simp
                                                                                  or
                          For   Rev  Rand        Front  Back  Assoc        Sort   Mult
                    Cont: Cont: Cont Cont: Sequ: Sequ:  Sequ: Cont:        Cont:  Cont:
Copy    Const:      O(n)
Fill    Const:                             O(n)
begin()             O(1)
end()               O(1)
rbegin()                        O(1)
rend()                          O(1)
front()                                    O(1)
push_front()                                     O(1)
pop_front()                                      O(1)
push_back()                                             O(1)
pop_back()                                              O(1)
Insert()                                                                          O(ln(n))
Insert: fill                               O(n)
Insert: range                              O(n)                                   O(kln(n)+n)
size()              O(n)
swap()              O(1)
erase key                                                     O(ln(n))
erase element                                                 O(1)
erase range                                                   O(ln(n)+S)
count()                                                       O(log(n)+k)
find()                                                        O(ln(n))
equal range                                                   O(ln(n))
Lower Bound/Upper Bound                                                    O(ln(n))
Equality                  O(n)
InEquality                O(n)
Element Access                       O(1)

解决方案

Start here: STL Complexity Specifications. Then read through all the container types on that site, and look at the complexity requirements stated.

Hope this helps!

这篇关于标准容器的复杂性保证是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！