Categories

See More
Popular Forum

MBA (4887) B.Tech (1769) Engineering (1486) Class 12 (1030) Study Abroad (1004) Computer Science and Engineering (988) Business Management Studies (865) BBA (846) Diploma (746) CAT (651) B.Com (648) B.Sc (643) JEE Mains (618) Mechanical Engineering (574) Exam (525) India (462) Career (452) All Time Q&A (439) Mass Communication (427) BCA (417) Science (384) Computers & IT (Non-Engg) (383) Medicine & Health Sciences (381) Hotel Management (373) Civil Engineering (353) MCA (349) Tuteehub Top Questions (348) Distance (340) Colleges in India (334)
See More

Merge entries in map if value equals key

General Tech Bugs & Fixes
Max. 2000 characters
Replies

usr_profile.png
Lucky Negi

User

( 7 months ago )

 

I have a std::map with the following values:

2 31
4 36
5 29
6 24
24 49
25 83
29 63
36 42
42 79

Now I want to "merge" values if a key exists for a value. So the desired output (data structure is irrelevant) would be:

2 31
4 36 42 79
5 29 63
6 24 49
25 83

I have tried iterating through the map and using std::find for every value. But I am having problems with vector sizes greater than 3 and it seems to be very slow for large maps. Here is a small example not giving exactly the desired output:

int main(int argc, char** argv)
{   
    std::map<int, int> my_map = { {2, 31}, {4, 36}, {5, 29}, {6, 24}, {24, 49}, {25, 83}, {29, 63}, {36, 42}, {42, 79} };

    std::vector<int> temp_vec;
    std::vector<std::vector<int>> destination_vec;

    for (auto it = my_map.begin(); it != my_map.end(); ++it) {

        std::map<int, int>::iterator map_iterator = my_map.find(it->second);
        if (map_iterator == my_map.end()) {
            temp_vec.push_back(it->first);
            temp_vec.push_back(it->second);
        }
        else {
            temp_vec.push_back(it->first);
            temp_vec.push_back(it->second);
            temp_vec.push_back(map_iterator->second);
            // I stopped here because I could try another if loop here or a while loop for the whole process but it seems very inefficient
        }
        destination_vec.push_back(temp_vec);
        temp_vec.clear();
    }
} 

usr_profile.png
Charles Kyobe

User

( 7 months ago )

std::map<int, std::vector<int>> foo(std::map<int, int> m)
{
    std::map<int, std::vector<int>> res;

    while (!m.empty())
    {
        auto it = m.begin();
        const auto key = it->first;
        auto& v = res[key];

        while (it != m.end()) {
            auto value = it->second;
            v.push_back(value);
            m.erase(it);
            it = m.find(value);
        }
    }
    return res;
}

what's your interest


forum_ban8_5d8c5fd7cf6f7.gif