Подсчет появления слов в векторе и перечисление их в списке, C ++ - PullRequest
Новая
       9

Подсчет появления слов в векторе и перечисление их в списке, C ++

0 голосов
/ 07 апреля 2020

У меня есть вектор cpp, содержащий отдельные слова, и мне нужно подсчитать, сколько раз слово появляется, используя список. Я пытаюсь перебрать список, но без сравнения двух контейнеров STL, независимо от того, есть ли следующее слово в моем списке или нет. Если нет, я хочу добавить это слово в свой список с появлением 1. У меня есть структура, которая подсчитывает, сколько раз слово появилось в тексте. Следующий код возвращает список слов и цифр, но не каждое в моем векторе, и я не понимаю, почему. 

struct counter{
    string word;
    int sum = 1;
    counter(){};
    counter(string word): word(word){};
};

list<counter> list_count(vector<string> &text){
    list<counter> word_count;
    list<counter>::iterator it = word_count.begin();
    for(string t:text){
        if(it != word_count.end()){
            it -> sum++;
        } else {
            word_count.push_back(counter(t));
        }
        ++it;
    }
    return word_count;
}

Заранее спасибо.

Ответы [ 3 ]

0 голосов
/ 07 апреля 2020 
list<counter> list_count(const vector<string>& text) {
    list<counter> word_count;
    for (const string& t : text) {
        auto it = std::find_if(word_count.begin(), word_count.end(), 
            [&](const counter& c){ return c.word == t; });
        if (it != word_count.end()) {
            it -> sum++;
        } else {
            word_count.push_back(counter(t));
        }
    }
    return word_count;
}

Не проверенный код.

0 голосов
/ 07 апреля 2020

Вы пытаетесь использовать неэффективный подход. Стандартный список шаблонов классов не имеет произвольного доступа к его элементам. Каждый новый элемент добавляется в конец списка. Чтобы найти, присутствует ли элемент в списке, его элементы просматриваются последовательно.

Было бы гораздо эффективнее использовать стандартный контейнер std::map. Более того, в этом контейнере будут упорядочены слова.

Например, вы можете объявить 

std::map<std::string, size_t> counters;

Тем не менее, если вы хотите использовать список, функция может выглядеть так, как показано в демонстрационной программе. ниже. 

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

struct counter
{
    std::string word;
    size_t n = 0;
    counter() = default;
    counter( const std::string &word ): word( word ), n( 1 ){}
};

std::list<counter> list_count( const std::vector<std::string> &text )
{
    std::list<counter> word_count;

    for ( const auto &s : text )
    {
        auto it = std::find_if( std::begin( word_count ), std::end( word_count ),
                                [&s]( const auto &c ) { return c.word == s; } );

        if ( it == std::end( word_count ) )
        {
            word_count.push_back( s );
        }
        else
        {
            ++it->n;
        }
    }

    return word_count;
}

int main() 
{
    std::vector<std::string> v { "first", "second", "first" };

    auto word_count = list_count( v );

    for ( const auto &c : word_count )
    {
        std::cout << c.word << ": " << c.n << '\n';
    }

    return 0;
}

Его вывод 

first: 2
second: 1

Обратите внимание, что определение счетчика структуры является избыточным. Вместо этого вы можете использовать стандартный класс std :: pair. Вот вам. 

#include <iostream>
#include <string>
#include <utility>
#include <list>
#include <vector>
#include <iterator>
#include <algorithm>

std::list<std::pair<std::string, size_t>> list_count( const std::vector<std::string> &text )
{
    std::list<std::pair<std::string, size_t>> word_count;

    for ( const auto &s : text )
    {
        auto it = std::find_if( std::begin( word_count ), std::end( word_count ),
                                [&s]( const auto &p ) { return p.first == s; } );

        if ( it == std::end( word_count ) )
        {
            word_count.emplace_back( s, 1 );
        }
        else
        {
            ++it->second;
        }
    }

    return word_count;
}

int main() 
{
    std::vector<std::string> v { "first", "second", "first" };

    auto word_count = list_count( v );

    for ( const auto &p : word_count )
    {
        std::cout << p.first << ": " << p.second << '\n';
    }

    return 0;
}

Если использовать std::map, то функция будет выглядеть очень просто. 

#include <iostream>
#include <string>
#include <vector>
#include <map>

std::map<std::string, size_t> list_count( const std::vector<std::string> &text )
{
    std::map<std::string, size_t> word_count;

    for ( const auto &s : text )
    {
        ++word_count[s];
    }

    return word_count;
}

int main() 
{
    std::vector<std::string> v { "first", "second", "first" };

    auto word_count = list_count( v );

    for ( const auto &p : word_count )
    {
        std::cout << p.first << ": " << p.second << '\n';
    }

    return 0;
}

Использование списка будет эффективным только в том случае, когда вектор строк отсортировано.

Вот демонстрационная программа. 

#include <iostream>
#include <string>
#include <list>
#include <vector>

struct counter
{
    std::string word;
    size_t n = 0;
    counter() = default;
    counter( const std::string &word ): word( word ), n( 1 ){}
};

std::list<counter> list_count( const std::vector<std::string> &text )
{
    std::list<counter> word_count;

    for ( const auto &s : text )
    {
        if ( word_count.empty() || word_count.back().word != s )
        {
            word_count.push_back( s );          
        }
        else
        {
            ++word_count.back().n;
        }
    }

    return word_count;
}

int main() 
{
    std::vector<std::string> v { "A", "B", "B", "C", "C", "C", "D", "D", "E" };

    auto word_count = list_count( v );

    for ( const auto &c : word_count )
    {
        std::cout << c.word << ": " << c.n << '\n';
    }

    return 0;
}

Ее вывод 

A: 1
B: 2
C: 3
D: 2
E: 1
0 голосов
/ 07 апреля 2020

Вы вообще не ищете std::list. На каждой итерации l oop через std::vector вам нужно искать весь std::list спереди назад, например: 

#include <string>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;

struct counter {
    string word;
    int sum = 1;
    counter(const string &word): word(word) {}
};

list<counter> list_count(const vector<string> &text) {
    list<counter> word_count;
    for(const string &t: text) {
        // perform an actual search here!
        list<counter>::iterator it = find_if(
            word_count.begin(), word_count.end(),
            [&](counter &c){ return (c.word == t); }
        );
        if (it != word_count.end()) {
            it->sum++;
        } else {
            word_count.emplace_back(t);
        }
    }
    return word_count;
}

Live Demo

При этом std::list - плохое решение для подсчета элементов. Лучшее решение - вместо этого использовать std::(unordered_)map (если только вам не нужно сохранить порядок найденных слов, что ни один из них не сделает), например: 

#include <string>
#include <map>
#include <vector>

using namespace std;

map<string, int> list_count(const vector<string> &text) {
    map<string, int> word_count;
    for(const string &t: text) {
        word_count[t]++;
    }
    return word_count;
}

Live Demo (с использованием std::map)

Live Demo (с использованием std::unordered_map)

...