C++ 索引到索引映射

Question

我有一个 ID(整数)列表。 它们以一种非常有效的方式排序，因此我的应用程序可以轻松处理它们，例如

9382
297832
92
83723
173934

(这种排序在我的申请中非常重要)。

现在我面临着必须访问另一个 vector 中 ID 的某些值的问题。

例如，ID 9382 的某些值位于 someVectorB[30] 上。

我一直在用

const int UNITS_MAX_SIZE = 400000;

class clsUnitsUnitIDToArrayIndex : public CBaseStructure
{
private:
    int m_content[UNITS_MAX_SIZE];
    long m_size;
protected:
    void ProcessTxtLine(string line);
public:
    clsUnitsUnitIDToArrayIndex();
    int *Content();
    long Size();
};

但现在我将 UNITS_MAX_SIZE 提高到 400.000，出现页面堆栈错误，这告诉我我做错了什么。我认为整个方法并不是很好。

如果“位置”不同，我想在不同的 vector 中定位一个 ID，我应该使用什么？

ps:我正在寻找可以轻松地从文件中读入并且也可以轻松地序列化为文件的简单内容。这就是我之前一直使用这种蛮力方法的原因。

Answer 1

如果您想要从 int 到 int 的映射并且您的索引号不连续，您应该考虑 std::map。在这种情况下，您可以这样定义它:

std::map<int, int> m_idLocations;

映射表示两种类型之间的映射。第一种类型是“键”，用于查找第二种类型，称为“值”。对于每个 id 查找，您可以将其插入:

m_idLocations[id] = position;
// or
m_idLocations.insert(std::pair<int,int>(id, position));

您可以使用以下语法查找它们:

m_idLocations[id];

通常，STL 中的 std::map 是使用 red-black trees 实现的它的查找速度较差，为 O(log n)。这比 O(1) 稍微慢一点，你将从巨大的数组中获得，但它是对空间的更好利用，你不太可能注意到实践中的差异，除非你存储真正大量的数字或进行大量查找。

编辑:

在回应一些评论时，我认为重要的是要指出从 O(1) 到 O(log n) 可以显着提高应用程序的速度，更不用说从 O(1) 到 O(log n) 的实际速度问题将内存块固定为基于树的结构。但是，我认为重要的是首先表示您要说的内容(int-to-int)映射并避免过早优化的陷阱。

在您表达了概念之后，您应该使用分析器 来确定是否存在速度问题以及速度问题出在哪里。如果您发现 map 导致问题，那么您应该考虑用您认为会更快的东西替换您的 map 。 确保测试优化是否有帮助，并且不要忘记包含关于您所代表的内容以及需要更改的原因的重要评论。