相关疑难解决方法(0)

显然;-)标准容器提供某种形式的保证.

什么类型的保证以及不同类型的容器之间究竟有什么区别？

从工作的SGI页(约STL)我想出了这一点:

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  Sequence                    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 …

我有一个排序数组,我在其中使用二进制搜索(std::upper_bound)O(logn)及时找到小于特定值的项目数.
现在我想在保持排序的同时插入和删除此数组.我希望整体的复杂性O(logn).

我知道,使用二叉搜索树或者std::multiset我可以做的插入,删除和UPPER_BOUND的O(logn),但我不能够做得到的距离/指数(std::distance是O(n)用于集)在对数时间.

那么有没有办法实现我想做的事情？