Combining a vector of pairs that has a similar string value C-CodePudding

I have a vector of pairs that contains strings as titles and int as values. I wanted to add all of the values that have a similar title. I was wondering if std::accumulate has a way of exploring this, or if std::map can be used too.

So I have a vector of pairs: 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} }; that should reduce to {{"a",70},{"b",5},{"c",4},{"d",25},{"f",11}} where similar strings have their values added.

This is what I have so far, but my iterator j skips when there is a succeeding similar title.

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);
        }
    }
}

Hoping for some englightment. Thank you!

CodePudding user response：

This is normal: you delete an element in the middle of the vector, and you don't modify j to stay at the same position (it will be incremented on next iteration of the loop). So add j--; after your erase and it should work properly.

But it's VERY inefficient to delete an element in the middle of a vector. Usually, on a vector, you do operations from end to start so you always remove last elements instead of middle ones. Your way would suits better to a std::list, which is optimized for random insertions/deletions - at the expense of random access, which is a O(n) operation.

But your algorithm's complexity is O(n²)... Using a temporary map to store data will reduce it to O(n.log2(n)) [including map's access complexity for writing], which is way better, then you can push all the data into the original vector and then truncate it where needed.

Example by @TedLyngmo (see his demo):

#include <algorithm> // std::move
#include <iostream>
#include <map>       // std::map
#include <string>
#include <utility>   // std::pair
#include <vector>

int main() {
    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}};
    
    { // 
        std::map<std::string, int> res;
        for(auto&[str, val] : list) res[str]  = val;

        list.resize(res.size());
        std::move(res.begin(), res.end(), list.begin());
    }

    for(auto&[str, val] : list) {
        std::cout << str << ',' << val << '\n';
    }
}

CodePudding user response：

To resolve your code, you can just decrease the value of j after erasing an element from the vector.

For example,

for(int i = 0; i < vec.size(); i  )
{
    for(int j = i   1; j < vec.size(); j  )
    {
        if (vec[i].first == vec[j].first)
        {
            vec[i].second  = vec[j].second;
            vec.erase(vec.begin()   j);
            j--;
        }
    }
}

Using STL map

Assuming will be given the pairs of vector, you can iterate the vector just once and store values in a map. No erasing will be required in here.

int main()
{
    map<string,int> mp;
    vector<pair<string,int>> vec;
    vec.push_back({"a", 10});
    vec.push_back({"b", 20});
    vec.push_back({"c", 30});
    vec.push_back({"a", 100});
    vec.push_back({"a", 500});
    vec.push_back({"d", 40});
    vec.push_back({"a", 20});
    vec.push_back({"b", 200});
    vec.push_back({"c", 30});

    for(auto curr : vec)
    {
        mp[curr.first]  = curr.second;
    }

    for(auto curr : mp)
    {
        cout << curr.first << " " << curr.second << endl;
    }
}

Output

CodePudding user response：

A solution using 2 for loops (time complexity, O(N^2).
(I would still prefer an std::map)

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

//upside: does not mutate the original vector  
//downside: too much redundant info
std::vector<int> foo(const std::vector<std::string>& vec_of_strings, const std::vector<int>& vec_of_integers) {
    std::vector<int> vec_of_sums;
    for (auto string : vec_of_strings) {
        auto sum = 0;
        for (auto it = std::find(vec_of_strings.begin(), vec_of_strings.end(), string); it != vec_of_strings.end(); it = std::find(it, vec_of_strings.end(), string)) {
            sum  = vec_of_integers.at(std::distance(vec_of_strings.begin(), it  ));
        }
        vec_of_sums.push_back(sum);
    }
    return vec_of_sums;
}

//upside: does not mutate the original vector  
//upside: no redundancy
std::vector<int> bar(const std::vector<std::string>& vec_of_strings, const std::vector<int>& vec_of_integers) {

    auto findAll = [=](const auto str) {
        std::vector<int> positions;
        for (int i = 0; i < vec_of_strings.size(); i  ) {
            if (vec_of_strings.at(i) == str) {
                positions.push_back(i);
            }
        }
        return positions;
    };

    std::vector<std::string> titles_done;

    std::vector<int> vec_of_sums;
    for (auto string : vec_of_strings) {
        if (std::find(titles_done.begin(), titles_done.end(), string) != titles_done.end()) {
            continue;
        }
        titles_done.push_back(string);
        std::vector<int> find_indices = findAll(string);
        auto sum = 0;
        for (auto index : find_indices) {
            sum  = vec_of_integers.at(index);
        }
        vec_of_sums.push_back(sum);
    }
    return vec_of_sums;

}

int main() {
    std::vector<std::string> vec_of_strings = { "A", "B", "A", "B", "C", "B", "D" };
    std::vector<int> vec_of_integers = { 1,2,1,2,3,2,4 };
    auto vec_of_sums = bar(vec_of_strings, vec_of_integers);
    std::copy(vec_of_sums.begin(), vec_of_sums.end(), std::ostream_iterator<int>(std::cout, " "));
    return 0;
}