优化C++代码(使用UnorderedMap和向量)

Question

我正在尝试优化C++代码的某些部分，这需要很长的时间(下面的代码部分对于X数据量大约需要19秒，并且在相同数据量的基础上，我试图在不到5秒的时间内完成整个过程--基于我已有的一些基准)。我有一个函数"add“，我已经在这里编写和复制了代码。我将尽可能多地解释我认为理解代码所需的内容。如果我漏掉了什么，请告诉我。

下面的函数add对X个数据项的数量调用X次。

void HashTable::add(PointObject vector)   // PointObject is a user-defined object
{
    int combinedHash = hash(vector);   // the function "hash" takes less than 1 second for X amount of data

   // hashTableMap is an unordered_map<int, std::vector<PointObject>>

   if (hashTableMap.count(combinedHash) == 0)
   {
        // if the hashmap does not contain the combinedHash key, then 
        //  add the key and a new vector
        std::vector<PointObject> pointVectorList;
        pointVectorList.push_back(vector);
        hashTableMap.insert(std::make_pair(combinedHash, pointVectorList));
   }
   else
   {
        // otherwise find the key and the corresponding vector of PointObjects and add the current PointObject to the existing vector
        auto it = hashTableMap.find(combinedHash);
        if (it != hashTableMap.end())
        {
            std::vector<PointObject> pointVectorList = it->second;
            pointVectorList.push_back(vector);
            it->second = pointVectorList;
        }
   }
}

Answer 1

你做了很多没用的手术..。如果我理解正确，一个简化的表格可以简单地：

void HashTable::add(const PointObject& vector) {
   hashTableMap[hash(vector)].push_back(vector);    
}

这起作用是因为

• 当使用operator[]访问一个映射时，如果它还没有出现在映射中，它将创建一个默认值。
• 值(一个std::vector)是通过引用返回的，因此您可以直接将传入点返回到它。如果该键已经在映射中，则该std::vector将是一个新插入的，或者是先前存在的。

还请注意，根据PointObject的大小和其他因素，按值传递vector可能比通过const PointObject&传递更有效。然而，这是一种微观优化，需要明智地进行分析。

Answer 2

与其调用hashTableMap.count(combinedHash)和hashTableMap.find(combinedHash)，不如插入新元素并检查insert()返回的内容：

在版本(1)和(2)中，函数返回一个对对象，该对象的第一个元素是一个迭代器，指向容器中新插入的元素或键为等效的的元素，并返回一个bool值，该值指示元素是否已成功插入。

此外，不要按值传递对象，在不必传递对象的地方。最好通过指针或引用传递。这是：

std::vector<PointObject> pointVectorList = it->second;

效率低下，因为它会创建一个不必要的向量副本。

Answer 3

如果没有if，尝试在哈希表上插入一个空条目：

auto ret = hashTableMap.insert(
   std::make_pair(combinedHash, std::vector<PointObject>());

或者添加一个新的空白条目，或者检索已经存在的条目。在您的示例中，您不需要检查是哪种情况，只需接受返回的迭代器并添加新元素：

auto &pointVectorList = *ret.first;
pointVectorList.push_back(vector);