标签: deque

对于列表，我们可以获得元素的索引list_name.index(3)

如何获取双端队列中项目的索引。

例如： d_list = deque([1, 2, 3, 4])获取元素 3 的索引的最佳方法是什么。

编辑：我正在使用Python 2.7.6

我在为双端队列 (Deque) 的大小分配限制时遇到问题。似乎我的队列永远不会满，并且每当我为其添加或提供值时就会调整大小。我的简单代码只接受一个字符串值，用空格“”分割它，循环所有内容并将其添加到队列中。

evaluate("A B C D E F");

public static int evaluate(final String input){
    final Deque<String> stack = new ArrayDeque<>(3);
    final String[] tokens = input.split(" ");


    for (String token:tokens){
        System.out.println(stack.offer(token));
    }

    System.out.println(stack.size());
 }

返回：

 true
 true
 true
 true
 true
 true
 6

我预计队列将已满，因为我没有从中删除或读取任何值。我在这里缺少什么吗？或者我只是错误地使用了队列？谢谢！

Consumer我有一个由类和类组成的线程程序Producer。目前，我在实现中使用 Fifo queue.Queue，生产者put获取队列末尾的数据，消费者get获取队列末尾的数据。

但是，我想添加一个功能，如果有必要，可以Consumer通过将其放回前面来put支持（可能稍微修改过的）项目（以便返回的下一个项目是刚刚添加的项目，就像在堆栈中一样）。getQueueget

我知道这对于 s 是可能的，但我在这里deque读到它们仅对于和是线程安全的。出于上述目的，我还需要使用.append()popleft()appendleft()

是否存在具有 a 特性的线程安全数据结构deque？如果没有，我可以deque通过在使用时放入自己的锁来使线程安全吗appendleft？

collections.deque 我一直在此处和此处阅读有关 CPython 的线程安全性的内容。我知道.append()和.popleft()操作在线程之间可以很好地配合，就像.appendleft()和一样.pop()。

.popleft()我的问题是：和之间同样适用吗.clear()？或者如果失败的话，在.popleft()和之间.pop()？我的情况是，我有一个消费者线程，称之为 A，不断地.popleft()从 a 获取项目deque d，还有一个生产者线程 B，将.append()它们放在右侧。在某些时候，我希望线程 B 能够说“取消所有待处理项目”。如果我这样做

d.clear()

由于与线程 A 的操作冲突，它是否可能导致未定义的行为.popleft()？如果我说：

while d:
    try: d.pop()
    except: break

反而？

我正在尝试为算法交易实现市场模拟，我在 github 上找到了这段代码https://github.com/DrAshBooth/PyLOB。问题是，当我在小窗口（例如 2 天）运行代码时，一切都很好，并且得到了预期的结果。但是当我将窗口增加到 20 天或更长时，我收到“RuntimeError: deque mutated during iteration”。我检查了我的代码，但从未发现任何可能在运行期间改变双端队列的内容。以下是产生错误的代码部分：

    self.tape = deque(maxlen=None)
    .
    .
    .
    def avg_volume_traded(self):
       if self.tape != None and len(self.tape) > 0:
          num = 0
          total_volume = 0
          for entry in self.tape:
             total_volume = entry['qty'] + total_volume
             num += 1
          if num != 0 and total_volume != None:
             return total_volume, num
       else:
          return None, None

这是实际的错误消息：

    Exception in thread Thread-10986:
    Traceback (most recent call last):
      File "/home/hamid/anaconda3/lib/python3.6/threading.py", line 916, in _bootstrap_inner
        self.run()
      File …

我需要将元素流保存在大小有限的列表中。流中可能有重复的元素，但我需要保留唯一的元素。此外，当列表的大小超过指定限制时，我需要删除最旧的元素并添加新元素。

我已经尝试过set并且list. 问题set是它没有大小限制，如果我想删除最旧的元素，我不知道如何检索它，因为集合是无序的；然而，它解决了唯一性问题。

另一方面，list保持项目的顺序，但每当我想插入新元素时，我都需要检查可能的重复项，这可能会花费大量时间。也list不受尺寸限制set。

我的第三个选择可能是，collections.deque但我不知道它是否保留订单。有什么办法可以保持物品的collections.deque独特性吗？

这些是我的代码示例list：

ids = list()
for item in stream:
    if item not in ids:
        ids.append(item)
    if len(ids) >= len_limit:
        del ids[0]

和set：

ids = set()
for item in stream:
    ids.add(item)
    if len(ids) >= len_limit:
        ids.remove(list(ids)[0])

我想实现一个VecDeque具有最大大小限制的。我有两个策略，但我都无法完成。

第一种方法：组合继承。

我创建了一个新结构：

pub struct LimVecDeque<T> {                                                                                                    
     deque: VecDeque<T>,                                                 
     limit: usize,                                                       
}

并创建一个新的推送函数：

impl<T> LimVecDeque<T> {
  ...

  pub fn push (&self, elem: T) {
    self.deque.push_back(elem);
    if self.limit < self.deque.len() {
      self.deque.pop_front();
    }
  }

  ...
}

这是可行的，但是随着我的程序的成长，我需要向我的LimVecDeque结构添加功能。其中大部分是原件的副本VecDeque：

pub fn len(&self) -> usize {
  self.deque.len()
}

我还有更多问题需要导出VecDeque::iter()。我在类型和迭代器方面遇到了问题（我还不太擅长迭代器）。这种方法迫使我将每个函数克隆/导出VecDeque到LimVecDeque. 大量的工作！

第二种方法：创建一个新特征并实施VecDeque：

trait Limited {
  type Elem;

  pub fn push_bounded(&self, limit: usize, elem: Elem);
}

然后再实现 的特征VecDeque。 …

我正在以流方式处理字节输入，如下所示：

pub struct CharQueue<R: Read> {
    reader: R,
    deque: VecDeque<u8>,
    buf: [u8;1024],
}

self.deque.reserve_exact(bytes_read);
for i in 0..bytes_read {
    self.deque.push_back(self.buf[i]);
}

在分析中，它似乎VecDeque::cap()是运行时的主要贡献者。这是令人惊讶的，因为它除了返回一个变量（我猜还有分支）之外几乎什么都不做：

fn cap(&self) -> usize {
    if mem::size_of::<T>() == 0 {
        // For zero sized types, we are always at maximum capacity
        MAXIMUM_ZST_CAPACITY
    } else {
        self.buf.capacity()
    }
}

所以它一定被调用了很多次（如果它在 inside 被调用push_back()，事后看来这很有意义）。

我想知道是否有一种方法可以将整个缓冲区一次性复制到队列中，因此容量只需检查并增加一次。.reserve_exact()跳过中间分配，但不跳过检查和增量。.append()是这样的，但我必须先消耗缓冲区才能将其转换为另一个 VecDeque，但我不想这样做，因为我想重新使用它。我真正想要的是这样的东西push_back_slice()，只需要一个切片，增加队列长度/执行任何所需的分配一次，然后将切片的每个元素直接复制到可用空间中，而不改变或消耗它。

有没有办法做到这一点？

给定一个数组 n 个元素 (n <= 10^5) 计算范围的数量 [L; R] (L <= R) 最大值与最小值之差为偶数。

例如，n = 5
a[] = {4, 5, 2, 6, 3}
答案是 11：[1;1], [1;4], [1;5], [2;2], [2;4]、[2;5]、[3;3]、[3;4]、[3;5]、[4;4]、[5;5] 时间限制为 1 秒

如果 n <= 1000，O(n^2) 的 natvie 算法就可以了。我认为我们可以通过使用堆栈或双端队列来改进这种方法。但这太难了。

有什么有效的办法吗？

std::deque 是否是连续的内存容器？

Scott Meyers 的著名著作《Effective STL》如下所述

连续内存容器（也称为基于数组的容器）将其元素存储在一个或多个（动态分配的）内存块中，每个块保存多个容器元素。如果插入新元素或删除现有元素，同一内存块中的其他元素必须向上或向下移动，以便为新元素腾出空间或填充以前被擦除元素占用的空间。这种移动会影响性能（参见第 5 条和第 14 条）和异常安全（我们很快就会看到）。标准的连续内存容器是向量、字符串和双端队列。非标准绳索也是连续内存容器。

但你可以在 cppreference.com 找到相反的解释

与 std::vector 不同，双端队列的元素不是连续存储的：典型的实现使用一系列单独分配的固定大小数组，并进行额外的簿记，这意味着与向量相比，对双端队列的索引访问必须执行两次指针取消引用索引访问仅执行一项。

哪一个是真的？