假设我们已经阅读了这些值:
3
1241
124515
5322353
341
43262267234
1241
1241
3213131
我有一个像这样的数组(上面的元素):
a[0]=1241
a[1]=124515
a[2]=43262267234
a[3]=3
...
问题是数组中元素的顺序不是恒定的(我必须在程序中的其他地方更改它)。
我怎么知道一个元素出现在读取文档中的哪个位置。
请注意，我不能这样做:
vector <int> a[1000000000000];
a[number].push_back(all_positions);
因为a将太大(存在内存限制)。 (假设我只有3000个元素，但是它们的值是从0到2 ^ 32)
因此，在上面的示例中，我想知道所有位置1241都在显示，而无需再次遍历所有读取的元素。
换句话说，如何将数字“1241”与位置“1,6,7”相关联，以便可以在O(1)中访问它们(其中1实际上是元素出现的位置数)
如果没有O(1)，我想知道什么是最佳的...
我不知道自己是否清楚。如果没有，请说出来，我会更新我的问题:)
最佳答案
您需要使用某种动态数组，例如 vector (std::vector)或其他类似的容器(std::list，可能取决于您的需求)。
这样的数据结构比C样式的数组更安全，更易于使用，因为它们负责内存管理。
如果还需要在O(1)中查找元素，则应考虑使用一些将索引与项目关联以及项目与索引关联的结构。我不认为STL提供任何东西，但是boost应该有类似的东西。
如果O(log n)是您可以负担的费用，请考虑std::map