CODEWITHSUNDEEP
c++unordered-map
Asher Leask
Asher Leask

Reputation: 39

Remove single node from unordered_map

The program should print 'Yes' if all words contained in note appear in magazine (case-sensitive), otherwise print 'No'. Each word in magazine can only be used once, that is, if the note has the same word twice the magazine must also contain that word at least twice.

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>

using namespace std;

void checkMagazine(vector<string> magazine, vector<string> note) {

    // Inserts magazine vector into an unordered_map for quick access
    unordered_map<string, int> umap;
    for (auto& x : magazine)
        umap[x] = 1;    

    // For each word in note search the unordered_map for that word
    for (auto& word : note) {
        if (umap.find(word) == umap.end()) { // Word not in magazine
            cout << "No" << endl;
            return;
        }
        else    // Remove single instance of that word
            umap.erase(word);
    }

    cout << "Yes" << endl;
    return;
}


int main()
{
    vector<string> magazine = { "Help", "me", "please", "please" };
    vector<string> note = { "Help", "please", "please" };

    checkMagazine(magazine, note);

    return 0;
}

The else condition needs to remove that single node from umap (or only a single instance of that particular word) but to the best of my knowledge the only modifier that can do this is 'extract' but I cannot use C++17.

Is there a way I can work around this, or is this type of method not going to work with an unordered_map? Would a linked list be more appropriate? I'm new to data structures so any help would be appreciated.

Upvotes: 0

Views: 213

Answers (1)

Xgh05t
Xgh05t

Reputation: 240

Something of this nature. I wrote it without much thought and without checking, so take it with a grain of salt (probably is correct). The idea is to use count of number of times a word appears in a magazine and substract it whenever you find it in the note.

    unordered_map<string, int> mp;
    for(const auto& s: magazine) mp[s]++;
    for(const auto& s: note) {
        auto it = mp.find(s);
        if(it == mp.end() || it->second <= 0) { cout << "No"; return; }
        it->second--; // if(!--it->second) mp.erase(it);  
        if(!it->second) mp.erase(it); 
    }
    cout << "Yes";

Upvotes: 3

Related Questions