Удалить один узел из unordered_map - PullRequest
Новая
       9

Удалить один узел из unordered_map

0 голосов
/ 29 января 2020

Программа должна вывести «Да», если все слова, содержащиеся в примечании, появляются в журнале (с учетом регистра), в противном случае вывести «Нет». Каждое слово в журнале может использоваться только один раз, то есть, если примечание содержит одно и то же слово дважды, журнал также должен содержать это слово как минимум дважды. 

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

Условие else необходимо удалить этот единственный узел из umap (или только одного экземпляра этого конкретного слова), но, насколько мне известно, единственный модификатор, который может сделать это, - «извлечь», но Я не могу использовать C ++ 17 .

Есть ли способ, которым я могу обойти это, или этот метод не будет работать с unordered_map? Будет ли связанный список более подходящим? Я новичок в структурах данных, поэтому любая помощь будет оценена.

Ответы [ 2 ]

3 голосов
/ 29 января 2020

Что-то в этом роде. Я написал это без долгих размышлений и без проверки, поэтому возьмите его с крошкой соли (вероятно, правильно). Идея состоит в том, чтобы использовать количество раз, когда слово появляется в журнале, и вычитать его всякий раз, когда вы найдете его в заметке. 

    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";
0 голосов
/ 29 января 2020

Несколько иной способ - использовать хэш-карту для подсчета всех слов в журнале, а затем для обратного отсчета. Затем используйте std::all_of, чтобы проверить, что число больше или равно 0 для каждого слова. 

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

    // Increment count for each word in magazine
    unordered_map<string, int> umap;
    for (auto& x : magazine)
        umap[x]++;

    // Decrement count for each word in note
    for (auto& word : note) {
        umap[word]--;
    }

    bool result = std::all_of(umap.cbegin(), umap.cend(),
        [](const std::pair<const std::string, int>& item) { return item.second >= 0; });

    if (!result)
        std::cout << "No";
    else
        std::cout << "Yes";
}

Это позволяет избежать ненужного удаления элементов в контейнере.

...