Подсчитайте количество вхождений элементов с векторами

Question

В настоящее время я изучаю C++ (правильно), просматривая книгу Ускоренный C++ от Andrew Koenig и Barbara Moo самостоятельно и выполняя все упражнения в каждой главе.

Упражнение 3-3: Напишите программу, чтобы подсчитать, сколько раз каждое отдельное слово появляется на своем входе. Для меня это упражнение представлялось чрезвычайно сложным, особенно учитывая: 1. Примеры и другие упражнения в этой главе были относительно простыми и 2. Вам разрешено использовать только векторы, поэтому ничего не продвинулось. (или, может быть, это просто я неправильно оцениваю сложность)

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

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

using std::cin; 
using std::setprecision; 
using std::cout; 
using std::string; 
using std::endl; 
using std::streamsize; 
using std::sort; 
using std::vector; 

int main() 
{ 

// Ask for string input 

cout << "Please write some text, followed by end-of-file: " << endl; 

vector<string> word_input; 
string word; 

// input words into string vector word_input 

    typedef vector<string>::size_type vecsize; 


    while (cin >> word) 
    { 
     word_input.push_back(word);     
    } 

// sort the vector in alphabetical order to be able to separate distinct words 

    sort(word_input.begin(),word_input.end()); 

// create two vectors: one where each (string) element is a unique word, and one 
// that stores the index at which a new distinc word appears 

    vector<string> unique_words; 
    vector<int> break_index; 


    for (int i=0; i != word_input.size()-1; ++i) 
    { 
     if(word_input[i+1] != word_input[i]) 
      { 
       unique_words.push_back(word_input[i]); 
       break_index.push_back(i); 
      } 

    } 

// add the last word in the series to the unique word string vector 

    unique_words.push_back(word_input[word_input.size()-1]); 

// create a vector that counts how many times each unique word occurs, preallocate 
// with 1's with as many times a new word occurs in the series (plus 1 to count the first word) 

    vector<int> word_count(1,break_index[0]+1); 

// if a new word occurs, count how many times the previous word occured by subtracting the number of words so far 

    for(int i=0; i != break_index.size()-1;++i) 
     { 
      word_count.push_back(break_index[i+1] - break_index[i]); 
     } 

// add the number of times the last word in the series occurs: total size of text - 1 (index starts at 0) - index at which the last word starts 

    word_count.push_back(word_input.size()-1-break_index[break_index.size()-1]); 


    // number of (distinct) words and their frequency output 

    cout << "The number of words in this text is: " << word_input.size() << endl; 

    cout << "Number of distinct words is: " << unique_words.size() << endl; 

     // The frequency of each word in the text 

     for(int i=0; i != unique_words.size(); ++i) 
      cout << unique_words[i] << " occurs " << word_count[i] << " time(s)" << endl; 



return 0; 
} 

Есть ли лучший способ сделать это с помощью векторов? Может ли код быть более эффективным, комбинируя любые петли?

Answer 1

Если вы предполагаете, что кто-то использует ваш код для обработки всего произведения Шекспира, вы будете тратить много места, сохраняя КАЖДОЕ слово. Если вместо этого вы сохраните структуру «слова» и «отсчет слова», вам нужно будет только один раз сохранить слово «один», даже если оно встречается 100000 раз в тексте, который подает ваша программа. То есть, если вам даже нужно знать, что это слово произошло более одного раза - если вам нужно всего лишь список уникальных слов, все, что вам нужно, это посмотреть, уже ли вы сохранили слово. [Сохранение их в отсортированном порядке позволит использовать binary_search, чтобы найти их, что помогло бы во время выполнения, если вы действительно используете 800K (не уникальные) слова Шекспира по вашему коду]

Answer 2

Решение, которое сработало для меня (когда я работал над этой проблемой) было использование трех векторов: input_vector, output_vector и count_vector. Прочтите ввод пользователя с помощью while с использованием std::cin до ввода символа пробега: используйте input_vector.push_back(input_word) для заполнения input_vector словами. Используйте std::sort от <algorithm>, чтобы отсортировать векторное изображение и создать output_vector (с одним значением, по первому из слов в input_vector) и count_vector (с одним значением, 1).

Затем для каждого элемента в input_vector (начиная со второго, а не первого) проверьте, совпадает ли текущий элемент с последним элементом. Если это так, добавьте 1 к текущему элементу в count_vector. В противном случае добавьте текущее слово в input_vector в output_vector с использованием push_back() и увеличьте размер count_vector на один элемент (значение которого равно 1).