c++ - 如何有效地存储等价物(来自连接组件标记算法)？

Question

我想存储来自 Connected-component labeling algorithm 的等价项.它基本上是制作一种从一个值(一个标签的 ID)到多个值(来自与前者等效的标签的 ID)的映射。

我已经做过这样的事情，但效果不是很好:

std::map<unsigned short, std::list<unsigned int>> equivalences;
for(int i = 0; i < MAX_NUMBER_OF_LABELS; ++i )
{
    std::list<unsigned int> temp;
    temp.push_back(i);
    // note that a label is equivalent to itself
    equivalences.insert( std::pair< int, std::list<unsigned int>>(i, temp) );
}

然后我通过以下方式添加适当的等价物:

equivalences.at( i ).push_back( equivalent_labels_int );

此方法的主要缺点是我必须预先声明 map 的大小(它必须足够大)，然后对于较大的大小(例如 9999)，初始化时间约为2.5秒。

谁有更好的主意？

Answer 1

在 C++(或大多数语言，就此而言)中，您不需要预先调整 map 的大小。 map 可以通过向其中添加新元素来动态增长，因此如果您找到一个新键，您可以随时将其添加到 map 中。例如:

equivalences[i].push_back(equivalent_labels_int);

这是有效的，因为 map 的方括号运算符 (operator[]) 会自动向 map 添加一个新的键/值对> 使用给定的键和默认值(如果不存在的话)。

此外，我建议不要使用 list 作为存储连接的 blob 序列的容器。 list 当您不需要随机访问并且经常删除序列中间的元素时很好，我认为您实际上并没有在这里做。相反，我会建议使用 vector 或 deque，因为这些结构的空间效率更高并且具有更好的局部性。

最后，根据您的特殊需要，您可能希望完全切换数据结构。如果您的算法通过从某个起点运行深度优先搜索然后存储它遇到的所有结果来工作，那么您现在拥有的方法可能非常好。但是，如果您的算法通过查找相似的点对然后将它们包含的 Blob 合并在一起来工作，您可能会对 disjoint-set forest data structure 感兴趣，实现简单但性能极佳。也就是说，使用这种结构会使您失去检查哪些点连接到给定点的能力，但效率的提升非常显着。

希望这对您有所帮助!