0

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

9382
297832
92
83723
173934

（这种类型在我的应用程序中非常重要）。

现在我面临着必须访问另一个向量中某个 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，我得到了页面堆栈错误，这告诉我我做错了什么。我认为整个方法并不是很好。

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

ps：我正在寻找一些简单的东西，可以很容易地从文件中读取，也可以很容易地序列化到文件中。这就是为什么我之前一直在使用这种蛮力方法。

4

3 回答 3

3

如果您想要从 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];

通常std::map，stl 中的 a 是使用红黑树实现的，红黑树的查找速度较差，为 O(log n)。这比 O(1) 稍慢，您将从巨大的数组中获得，但它是对空间的更好利用，除非您存储真正大量的数字，否则您不太可能注意到实践中的差异或进行大量查找。

编辑：

在回应一些评论时，我认为重要的是要指出从 O(1) 到 O(log n) 可以对应用程序的速度产生显着影响，更不用说从移动到固定块的实际速度问题了内存到基于树的结构。但是，我认为最初表示您要说的内容（int 到 int）映射并避免过早优化的陷阱很重要。

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

于 2013-04-18T05:44:11.447 回答
1

由于 int m_content[UNITS_MAX_SIZE]，您可能会遇到 stackoverflow 错误。数组分配在堆栈上，400000 对堆栈来说是一个相当大的数字。您可以改用 std::vector ，它是动态分配的，您可以返回向量成员的引用以避免复制操作：

std::vector<int> m_content(UNITS_MAX_SIZE);

const std::vector<int> &clsUnitsUnitIDToArrayIndex::Content() const
{
   return m_content;
}
于 2013-04-18T05:40:40.217 回答
1

如果没有其他工作，您可以在构造函数中动态分配数组。这将在堆上移动大数组并避免您的页面堆栈错误。您还应该记住在销毁您的资源时释放资源clsUnitsUnitIDToArrayIndex

但推荐的用法是其他成员建议的，使用 std::vector 或 std::map

于 2013-04-18T05:49:11.293 回答