C++索引到索引映射

我有一个ID（整数）的列表。他们是在一个非常有效的方式来分类，使我的应用程序可以轻松地处理它们，例如C++索引到索引映射

（这种是在我的应用非常重要）。

现在我面临的问题是不得不访问另一个向量中的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：我正在寻找一些简单的东西，可以很容易地从一个文件读入，也可以很容易地被序列化为一个文件。这就是为什么我以前一直在使用这种蛮力方法。

来源

2013-04-18 tmighty

你可以考虑使用一个std ::向量或std ::地图'的std ::地图'？ – 2013-04-18 05:31:20

如果您当前的m_content数组超出了会导致您的直接错误的堆栈大小，我不会感到惊讶。无论这种方法似乎关闭。你想解决什么问题？ – 2013-04-18 05:34:03

我想保留一个列表，告诉我某个ID位于矢量上的哪个位置。 – tmighty 2013-04-18 05:37:55

如果你想从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其中有一个worse-实现强制查找O（log n）的速度。这比O（1）稍微慢一点，你会从巨大的数组中获得，但是它更好地利用了空间，并且除非存储真正庞大的数字或做了大量的查找工作。

编辑：

在回应一些评论我想指出的是，距离O移动（1）至O（log n）的可以使你的应用程序的速度显著差异是非常重要的更不用说将固定的内存块转移到基于树的结构所带来的实际速度问题。不过，我认为首先要表达你想说的（int-to-int）映射并避免过早优化的陷阱是很重要的。

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

来源

2013-04-18 05:44:11

2个向量中的值是相同的，但它们是混合的，例如vector1：43,98,11和vector2：98,11,43 – tmighty 2013-04-18 05:46:35

谢谢您的解释。但是因为我有这么多的数据（400.000 * 2个ID对于RAM来说可能真的太多了），我是否应该使用文件映射从文件中获取数据，然后使用memcopy来检索值？我的代码非常庞大，为了简单地尝试，我需要几个小时，这就是为什么我想提前询问我的方法是否合乎逻辑。 – tmighty 2013-04-18 05:54:47

800,000个id对于对数运算而言相对较小。把它放到透视日志（800000）〜= 5.903，这在大型计算的规模上很小。复制那么多的数据会比执行一些地图查找要慢得多。尽管所有这些取决于你的应用程序如何放在一起。 – 2013-04-18 05:57:16

可能是由于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-18 05:40:40

到底动态分配和固定分配有什么区别，都变成了相同的大小？例如，如果我在向量中真的有400.000个id，则动态分配或立即分配并不重要，是吗？ – tmighty 2013-04-18 05:52:02

@tmighty，固定分配分配在堆栈上，堆栈的大小有限，但动态分配的限制仅限于可用RAM。如果你想使用像这样的巨大数组，你可以通过使用像std :: vector这样的标准容器来避免stackoverflow的问题，或者你可以在关键字new的堆上定义你的数组 – 2013-04-18 05:55:30

你能告诉我怎样才能从那里访问vector外？我的“int * Content（）;”已过时。我想你错了。它不应该是“std :: vector m_content（）;” ？ – tmighty 2013-04-18 06:39:34

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

不过是由其他成员提出的建议用量，使用

来源

2013-04-18 05:49:11 weima

C++索引到索引映射

回答

相关问题