寻找预分配向量C++的非空索引
提问于 2014-06-25 22:04:14
有什么简单的方法可以找到预分配向量的非空项的索引吗？
一种方法是简单地循环通过向量。但是，如果分配给向量的内存很大，并且非空条目的数量非常少，则速度非常慢。
下面是示例代码。因为我有索引5,9,9,15的条目，现在的任务是从大小为20的向量x中识别indices 5、9、15。请提出一些简单的方法，甚至更好的数据结构来做这将是有帮助的。
#include "stdafx.h"
#include <string>
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
vector <map<int,int>> x(20);
x[5].insert({ 4,10002 });
x[9].insert({2,20});
x[9].insert({ 3, 60 });
x[15].insert({ 11, 60 });
return 0;
}
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-06-25 23:32:36
首先，对于零项，您的意思是空条目(没有元素的map )。
我认为不可能删除迭代成本，但可以将其移到程序的其他点(初始化、元素插入、.)从要识别这些索引的点开始。
例如，您可以将两个容器封装在一个类中:您提议的向量，以及一个带有向量中的空条目索引的set<size_t>。两者都不应该在类之外直接访问(private)。您必须用范围向量中的所有索引初始化集合(这里的迭代)。新元素的插入应该通过类接口来从集合中删除该索引。删除新元素(包括从任何条目的映射中删除元素，以检测其何时为空)。要标识空条目索引，那么，集合中有所有这些索引。
如您所见，这种方法将迭代成本从要标识空条目索引的位置移到初始化，将复杂性(和成本)添加到其他任何地方。
根据您的需要，要使用的容器可能是不同的，或者这种方法可能根本没用。
更新:如果问题是寻找空条目索引，那么上面的方法是正确的。要解决问题中的问题(标识非空的条目索引)，方法是：
- 使用
set<size_t>存储非空索引， - 与初始化时的设置无关。
- 插入新元素时，请在集合中插入该索引。
- 当从向量中的任何映射中移除元素时，请检查映射是否变为空，以便在这种情况下删除索引
- 集合将包含非空项的索引。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/24423423
复制相关文章
node_modules / rxjs / internal / types.d.ts中的错误（81,44）：错误TS1005：';' 预期。 node_modules / rxjs / int...
腾讯云开发者
