标签: deque

我有一个std :: deque,我想在指定的索引处插入一个元素(我知道std :: list会更好).deque :: insert()函数使用迭代器指定要插入的位置.给定一个索引,如何获得指向该位置的迭代器,以便我可以将该迭代器传递给insert()？

例如:

void insertThing ( deque<Thing> & things, Thing thing, size_t index )
{
   deque<Thing>::iterator it = /* what do I do here? */
   things.insert ( it, thing );
}

我确信这是一个非常基本的问题,我为此道歉.自从我使用STL已经有很长一段时间了,我在std :: deque的成员列表中看不到任何显然符合我想要的东西.谢谢.

我正在运行许多线程并在队列中收集结果.我想将其转储到数组或列表中,以便我可以进行索引并检索这些结果.队列中的每个元素都是维度为n的数组.我想访问这些数组.请你告诉我,我怎么办？

 def dump_queue(model_queue):
 queue_list = []
 for i in iter(model_queue.get,'STOP'):
         queue_list.append(i)
  return queue_list




aux_model=train_svm(np.array(trainExample),np.array(trainLabel))
model_queue.put(aux_model.coef_)

因此,数组是学习的模型参数svm.model_queue在线程之间共享.我想访问每个模型参数向量而不是模型参数的每个条目.

我正在寻找Java解决方案,但任何一般的答案也没关系.

Vector/ArrayList是O(1)用于追加和检索,但O(n)用于前置.

LinkedList(在Java中实现为双链接列表)是O(1)用于追加和前置,但是O(n)用于检索.

Deque(ArrayDeque)对于上面的所有内容都是O(1)但不能在任意索引处检索元素.

在我看来,满足上述要求的数据结构内部有2个可增长列表(一个用于前置,一个用于追加),还存储一个偏移量以确定在检索期间获取元素的位置.

我用a std::deque来存储相当多的对象.如果我删除了一堆这些对象,在我看来它的内存使用量并没有减少,与std :: vector类似.

有没有办法减少它？我知道在矢量中你必须使用'交换技巧',我认为它也适用于此,但我宁愿避免使用它,因为它需要复制容器中剩下的所有元素(因此需要你有足够的内存来存储每个对象两次).我并不熟悉deque的实现,但我对它的理解是,有可能在没有大量副本的情况下实现这样的事情(而使用矢量显然不是这样).

我正在使用VC++(Dinkumware)STL,如果这有任何区别的话.

刚才,我正在读Josuttis的STL书.

据我所知 - c ++ vector是一个可以重新分配的c-array.所以,据我所知,为什么在push_back()之后所有迭代器和引用都会变得无效.

但我的问题是关于std :: deque.据我所知,它是大块的数组(c-array的c-array).因此push_front()在开头插入元素,如果没有空格,则deque分配新块,并将元素放在已分配块的末尾.

在中间插入()后,所有引用和迭代器都变得无效,我理解为什么 - 所有元素都被移动.但我真的误解了这句话"...在push_back()和push_front()之后所有引用都保持有效,但迭代器没有"(同样的短语可以在@ standard:23.2.2.3找到)

这是什么意思？!如果引用有效,则deque无法重新分配(==移动)其元素.那么为什么迭代器变得无效呢？为什么我不能在非移动元素插入后使用它们？或者这句话意味着,我不能确定迭代器相等于begin()或end()和溢出？

另外,我想提一下,在erase()之后,所有迭代器和引用都保持有效(除了擦除的:-)).

PS:请不要以"标准"形式回答:"它不能被使用,因为标准是这样说的".我想明白为什么,会发生什么.

我正在使用重用标识符以编程方式创建单元格.

注意 - 我没有使用故事板来创建单元格

每当单元出列时,单元格为零,因此需要使用alloc重新创建单元,这很昂贵.

编辑(增加了1个问题并更正了代码)

题

• 为什么这个出列总是返回零？我该如何纠正？
• 只有在与storyboard/nib文件一起使用时才会出列队列吗？

码

- (UITableViewCell *)tableView:(UITableView *)tableView cellForRowAtIndexPath:(NSIndexPath *)indexPath
{

    static NSString *CellIdentifier = @"Cell";

    UITableViewCell *cell = [self.tableView dequeueReusableCellWithIdentifier:CellIdentifier];

    if(!cell) //Every time cell is nil, dequeue not working 
    {
        cell = [[UITableViewCell alloc] initWithStyle:UITableViewCellStyleDefault reuseIdentifier:CellIdentifier];

    }

    return cell;
}

我有一个队列(来自Queue模块),我希望获得索引访问权限.(即,能够在队列中询问第4项,而不将其从队列中删除.)

我看到一个队列在内部使用了一个deque,而deque已经建立了索引访问.问题是,如何在没有(1)弄乱队列的情况下使用双端队列,(2)破坏线程安全性.

我知道,当插入位于前端或末端时,deque比vector更有效,如果我们必须进行指针算法,则vector更好.但是当我们必须在中间执行插入时要使用哪一个.为什么.？

我有一个问题,我正在努力,我需要使用某种二维数组.数组是固定宽度(四列),但我需要动态创建额外的行.

为此,我一直在使用向量的向量,我一直在使用一些包含这个的嵌套循环:

array.push_back(vector<float>(4));
array[n][0] = a;
array[n][1] = b;
array[n][2] = c;
array[n][3] = d;
n++

添加行及其内容.问题是我似乎因为我试图创建的元素数量而耗尽内存,所以我减少了我使用的数量.但后来我开始阅读deque,并认为它可以让我使用更多的内存,因为它不必是连续的.在这个循环中,我将所有提到的"vector"改为"deque",以及所有声明.但后来看来我再次耗尽内存,这次即使行数减少也是如此.

我查看了我的代码使用了多少内存,当我使用deque时,内存稳定上升到2GB以上,程序很快关闭,即使使用较少的行数.当内存耗尽时,我不确定它在这个循环中的确切位置.

当我使用向量时,即使循环退出,内存使用(对于相同的行数)仍然低于1GB.然后继续进行类似的循环,添加更多行,仍然只达到约1.4GB.

所以我的问题是.对于deque来说,使用两倍以上的向量内存是正常的,还是我在思考我可以在声明/初始化和上面的代码中用"deque"替换单词"vector"时做出错误的假设？

提前致谢.

我正在使用:MS Visual C++ 2010(32位)Windows 7(64位)

标准说：

双端队列是支持随机访问迭代器（27.2.7）的序列容器。此外，它支持在开头或结尾的恒定时间插入和擦除操作；在中间插入和擦除需要线性时间。

然而，它也在同一个条款中说：

本条款中的所有复杂性要求仅根据对所包含对象的操作数量进行说明。[ 示例： type 的复制构造函数vector<vector<int>>具有线性复杂性，即使复制每个包含的复杂性vector<int>本身也是线性的。— 结束示例 ]

不这是否意味着在插入的，刚开始说，deque<int>被允许采取线性时间，只要不超过固定数量的执行更多操作上的int那些已经在双端队列和新的Sint对象插入?

例如，假设我们使用“大小为 K 个向量的向量”来实现双端队列。似乎我们在开头每插入 K 次，就必须在开头添加一个新的大小为 K 的向量，因此必须移动所有其他大小为 K 的向量。这意味着开始时插入的时间复杂度分摊为 O(N/K)，其中 N 是元素总数，但 K 是常数，所以这只是 O(N)。但这似乎是标准允许的，因为移动大小为 K 的向量不会移动其任何元素，并且“复杂性要求”“仅根据对所包含int对象的操作数量进行说明” 。

标准真的允许这样做吗？或者我们应该将其解释为具有更严格的要求，即对所包含对象的恒定操作次数加上恒定的额外时间？