组合具有相似字符串值的对向量 C++

Question

我有一个向量对，其中包含字符串作为标题和 int 作为值。我想添加具有相似标题的所有值。我想知道是否std::accumulate有办法探索这个，或者是否std::map也可以使用。

所以我有一个成对的向量： std::vector<std::pair<std::string, int>> list { {"a",10},{"a",20},{"a",30},{"b",5},{"c",4},{"d",10},{"a",10},{"f",11},{"d",15},{"a",20} };它应该减少到{{"a",70},{"b",5},{"c",4},{"d",25},{"f",11}}相似字符串添加其值的位置。

这是我到目前为止所拥有的，但是j当有后续的类似标题时，我的迭代器会跳过。

for (std::size_t i = 0; i < list.size(); ++i) {
    for (std::size_t j = i + 1; j < list.size(); ++j) {
        if (list[i].first == list[j].first) {
            list[i].second += list[j].second;
            list.erase(list.begin() + j);
        }
    }
}

希望有所启发。谢谢你！

Answer 1

这是正常的：您删除了向量中间的一个元素，并且不修改j以保持在同一位置（它将在循环的下一次迭代中递增）。所以j--;在你之后添加erase它应该可以正常工作。

\n

但是删除向量中间的元素是非常低效的。通常，在向量上，您从头到尾执行操作，因此您总是删除最后一个元素而不是中间的元素。您的方法更适合 a std::list，它针对随机插入/删除进行了优化 - 以随机访问为代价，这是一个 O(n) 操作。

\n

但是你的算法的复杂度是O(n\xc2\xb2)...使用临时map来存储数据会将其降低到O(n.log2(n)) [包括map的写入访问复杂度] ，这样更好，然后您可以将所有数据推入原始向量，然后在需要的地方截断它。

\n

@TedLyngmo 的示例（参见他的演示）：

\n

#include <algorithm> // std::move\n#include <iostream>\n#include <map>       // std::map\n#include <string>\n#include <utility>   // std::pair\n#include <vector>\n\nint main() {\n    std::vector<std::pair<std::string, int>> list{\n        {"a", 10}, {"a", 20}, {"a", 30}, {"b", 5},  {"c", 4},\n        {"d", 10}, {"a", 10}, {"f", 11}, {"d", 15}, {"a", 20}};\n    \n    { // \n        std::map<std::string, int> res;\n        for(auto&[str, val] : list) res[str] += val;\n\n        list.resize(res.size());\n        std::move(res.begin(), res.end(), list.begin());\n    }\n\n    for(auto&[str, val] : list) {\n        std::cout << str << \',\' << val << \'\\n\';\n    }\n}\n

\n