标签: deque

参考HerbSutter的文章Gotw 54,他解释说

1. 正确的"收缩适合"矢量或deque和

2. 完全清除矢量或双端队列的正确方法

我们可以使用container.resize() 和container.clear()执行上述任务,还是我错过了什么？

我如何insert()将一堆物品deque放在线性时间的中间？

(我插入的项目无法通过STL样式的迭代器访问.)

使用此Java代码:

    // create the items list
    List<Item> items = new ArrayList<Item>();
    // ... (add some elements into the list so that it is not empty)

    // iterating ArrayList<Item> from right to left we find the position
    // based on the `if` condition satisfied for an item property
    int pos = 0;
    for (int j = items.size() - 1; j >= 0; j--) {
        Item item = items.get(j);
        if (item.property <= 7) {
            pos = j + 1; break;
        }
    } …

我正在尝试动态实现“heapq”或“deque”（根据用户的输入）

class MyClass():

    def __init__(self,  choose = True ):
    self.Q = []
    self.add = self.genAdd(choose)
    self.get = self.genGet(choose)

    def genAdd(self, ch):
        if(ch == True):
            def f(Q, elem):
                return Q.append
        else:
            def f(Q):
                return heappush
        return f

'genGet' 也一样

执行在一侧 (x) 或另一侧（但不能同时进行）是正确的。我得到类似的东西

TypeError: f() takes exactly 1 argument (2 given)

尝试了多次继承，但得到了

TypeError: Error when calling the metaclass bases
metaclass conflict: the metaclass of a derived class must be a (non-strict) subclass of the metaclasses of all its bases

问题是 heapq 被调用 …

我想要一个根据输入索引u移动的函数.如果你是负面的,向右移动,否则向左移动.使用下面的代码得到的结果deque与输入相同.

deque<float> move(deque<float>p, int u)
{
    if(u==0 || p.size()==1)
        return p;

    else if(u<0)
    {
        for(int i=0; i<abs(p.size()); i++)
        {
            int temp = p.back();
            p.pop_back();
            p.push_front(temp);
        }       
    }

    else
    {
        for(int i=0; i<p.size(); i++)
        {
            int temp = p.front();
            p.pop_front();
            p.push_back(temp);
        }
    }

    return p;
  }

这段代码的另一个变体似乎在Python中运行良好,但在C++中却不行,这是:

deque<float> move1(deque<float>p, int u)
{
    deque<float> q;

    for(int i=0; i<p.size(); i++)
        q.push_back(p[(i-u) % p.size()]);

     return q;
 }

我在理解这个概念时遇到了一些困难。从这个线程here它指出

双端队列要求在前面或后面的任何插入都应保持对成员元素的任何引用有效。迭代器失效是可以的，但成员本身必须留在内存中的同一位置。

我对这个线程的印象是

指针实际上是一种迭代器。事实上，对于一些容器类型，对应的迭代器可以简单地实现为一个指针。

如果我们有一个指针和一个迭代器，它们都引用容器的相同元素，那么任何使一个无效的操作都会使另一个无效。

所以如果一个迭代器失效，那么引用也会失效。我的问题是这怎么可能。如果指向某个内存地址的迭代器无效，那么对该地址的引用如何有效？

更新：

我知道双端队列是由随机内存块实现的，这些内存块由独立的数据结构（例如动态数组）跟踪。但是，我很难理解迭代器如何无效但引用可能有效，因为迭代器本质上是数据结构内容的通用指针。这让我认为迭代器可能指向其他东西，而指针指向实际项目？考虑下面的向量图。

根据我在上图中对向量的理解，如果指针的内容发生变化，迭代器也会发生变化。deque 有什么不同。

我有一个类似的列表

a=[{'time':3},{'time':4},{'time':5}]

我想像这样以相反的顺序得到值的累积和

b=[{'exp':3,'cumsum':12},{'exp':4,'cumsum':9},{'exp':5,'cumsum':5}]

获得这个的最有效方法是什么？我已经阅读了其他答案,其中使用numpy给出了解决方案

a=[1,2,3]
b=numpy.cumsum(a)

但我也需要在字典中插入cumsum

背景

std::deque使用子数组来存储其元素.它有一个额外的簿记数据结构,以跟踪其子阵列.这样,与之相比std::vector,std::deque可以从后面更快地增长(O(1)与摊销的O(1)相比),并且在前面更快(O(1)与O(n)相比).这是因为std::deque可以在任一端添加子数组,只需要修改其簿记数据结构.

题

我不明白的是,为什么子阵列有自己的尺寸固定为解释在这里:

典型的实现使用一系列单独分配的固定大小的数组

没有固定大小的子阵列有很多优点.例如,由于子阵列的大小是固定的,因此中间的任何插入都必须是O(n)复杂度,其中n是到最近端的元素的数量.然而,如果子阵列可以自由生长,则在中间插入将是O(k),其中k是子阵列中元素的数量,其快得多,特别是如果std::deque具有许多子阵列.从中间删除也是一样的.

是因为std::deque想要保持其子阵列平衡吗？如果子阵列太大/太小,则可以通过启用子阵列进行拆分或合并来轻松减轻这种情况.复杂性将只是O(k),其中k是最大子阵列的大小.(或者最小的子阵列和它的较小邻居的组合大小)

是因为固定大小的子阵列使得随机迭代更快吗？例如,如果你想要第n个元素,你必须通过簿记数据结构并添加所有先前子阵列的大小,使得复杂度为O(k),其中k是簿记数据结构的大小.但这不是一个大问题,因为std::deque广告宣传是一个双向链表,无论如何都有更好的缓存.

编辑: std::deque只是链表实现和数组实现之间的中间人.我想我的问题已经失去了它的原始含义,只是暗示它应该表现得更像链接列表而不是矢量

好吧,我们知道这 RandomAccess是一个标记界面,文档说:

List实现使用的标记接口,表示它们支持快速(通常是恒定时间)随机访问.此接口的主要目的是允许通用算法更改其行为,以便在应用于随机或顺序访问列表时提供良好的性能.

因此,对我来说,ArrayList实现RandomAccess接口是完全合理的,因为内部元素存储在一个可以随机访问的数组中.但是,如果您将看到其内部实现ArrayDeque也将元素存储在一个数组中,但它没有实现RandomAccess,那么它是否有意或者它已经完成了一些我不知道的明确原因？

如何散列 deque 中的内置节点（这是一个双链表）并删除 O(1) 中间的节点？内置节点是否暴露？

例如，我想在 dict 中保存一个双端队列的节点，以便以后可以在恒定时间内删除该节点。

这是 LRU 中的一个用例，使用 deque，所以我不需要编写自己的双链表。

from collections import deque

class LRU:
  def __init__(self):
    self.nodes = deque()
    self.key2node = {}

  def insertThenDelete(self):
    # insert
    node = deque.Node('k', 'v') # imagine you can expose deque node here
    self.nodes.appendleft(node) 
    self.key2node = {'k': node} 

    # delete
    self.key2node['k'].deleteInDeque() # HERE shold remove the node in DLL!
    del self.key2node['k']

我知道你可以del mydeque[2]按索引删除。但我想key2node['k'].deleteInDeque()通过引用进行删除。