Вставка в отсортированный массив структур в C ++

Question

Я должен реализовать вектор с использованием массива в C ++, который используется для подсчета количества уникальных слов из входных данных.Он читает входные данные, а затем добавляет слова в структуру, которая содержит их счет и уникальное слово, а затем это добавляется в вектор.Я успешно осуществил вставку.Проблема в том, что я не могу заставить работать вставку / приращение уникального количества слов (элементы не добавляются в вектор).Вот мой код:

#include <stdio.h>
#include <iostream>
#include <unistd.h>
#include "MyVector.h"
using namespace std;

struct wordCount{
    string val;
    int count;
};

int main(int argc, char** argv) {
  enum { total, unique,individual } mode = total;
  for (int c; (c = getopt(argc, argv, "tui")) != EOF;) {
    switch(c) {
    case 't': mode = total; break;
    case 'u': mode = unique; break;
    case 'i': mode = individual; break;
    }
  }
  argc += optind;
  argv += optind;
  string word;
  Vector<wordCount> words;
  Vector<wordCount>::iterator it;
  int count = 0;
  while (cin >> word) {
    count++;
    if(mode == unique || mode == individual){
      for(it=words.begin();it != words.end();it++){
        if((it-1)->val <= word && it->val >= word){
            // Found word, increment its count
            if(it->val == word){
                it->count++;
                break;
            }
            // Otherwise insert the new unique word
            else{
              cout << "adding unique word" << endl;
              wordCount* wc;
              wc = new wordCount;
              wc->val = word;
              wc->count = 1;
              words.insert(it,*wc);
              break;
            }
        }
      }
    }
  }
  switch (mode) {
    case total: cout << "Total: " << count << endl; break;
    case unique: cout << "Unique: " << words.size() << endl; break;
    case individual:
        for(it=words.begin();it!=words.end();it++){
          cout << it->val << ": " << it->count << endl;}
        break;
  }
}

Answer 1

Трудно что-то сказать, не видя реализации Vector.Если мы предполагаем, что он соответствует стандартным соглашениям о контейнерах (и при этом не возникает ошибка при попытке сделать это): вы выполняете итерацию, начиная с it.begin(), but immediately access it-1 . That's undefined behavior for a standard container. (I don't know what it will do with your implementation of Vector`, но для этого потребуется некоторый хитрый кодэто работает.)

На более высоком уровне кажется несоответствие основным: вы сохраняете вектор отсортированным, но все еще используете линейный поиск.Если вы используете линейный поиск, нет смысла сохранять вектор отсортированным;просто используйте:

Vector<wordCount>::iterator it = words.begin();
while ( it != words.end() && *it != word ) {
    ++ it;
}
if ( it == words.end() ) {
    //  not found, append to end...
} else {
    //  found, do whatever is appropriate...
}

(хотя я, вероятно, добавлю конец, восстановите итератор для вновь вставленного элемента и обработайте его, как если бы он был найден).вы сохраняете вектор отсортированным, используйте бинарный поиск, а не линейный поиск.

В любом случае поместите поиск в отдельную функцию.(Если бы это была не домашняя работа, я бы сказал, что просто используйте std::vector и либо std::find_if, либо std::lower_bound.)

Кроме того, почему new во внутренней else?Более разумным подходом было бы предоставить конструктор для wordCount (который устанавливает счетчик в 0) и сделать что-то вроде:

if ( ! found ) {
    it = words.insert( wordCount( word ) );
}
++ it->count;

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

Vector<wordCount>::iterator it
    = std::find_if( words.begin(), words.end(), MatchWord( word );
if ( it == words.end() ) {
    it = words.insert( words.end(), wordCount( word ) );
}
++ it-count;

или

Vector<wordCount>::iterator it
    = std::lower_bound( words.begin(), words.end(), word, CompareWord() );
if ( it == words.end() || it->val != word ) {
    it = words.insert( wordCount( word ) );
++ it->count;

Возможно, вы должны стремиться к чему-то похожему, с отдельной функцией поиска, возвращая либо end,или позиция для вставки, когда значение не найдено.

Это четко разделяет различные проблемы и позволяет избежать чрезмерного вложения в ваш код.(Вам, вероятно, следует стараться избегать break в целом, и в случае множественных вложений if s это совершенно недопустимо - вы заметите, что один из отвечавших на них людей пропустил их, и из-за этого неправильно понял поток управления.)

Answer 2

Попробуйте использовать std :: map.

Counter::Map words;
Counter count(words);

std::for_each(
    std::istream_iterator<std::string>(myInStream /*std::cin*/), 
    std::istream_iterator<std::string>(),
    count);

std::copy(
    words.begin(),
    words.end(),
    std::ostream_iterator<Counter::Map::value_type>(myOutStream /*std::cout*/, "\n"));

Функтор Counter может выглядеть следующим образом

struct Counter
{
    typedef std::map<std::string, size_t> Map;
    Counter(Map& m) : words(&m) {}
    void operator()(const std::string& word)
    {
        Map::iterator it = words->lower_bound(word);
        if (it == words->end() || it->first != word)
            words->insert(it, std::make_pair(word, 1));
        else
            ++it->second; 
    }
    Map* words;
};

Использование std :: vector

struct CounterVector
{
    typedef std::vector<std::pair<std::string, size_t> > Vector;
    CounterVector(Vector& m) : words(&m) {}

    struct WordEqual
    {
        const std::string* s;
        WordEqual(const std::string& w) : s(&w) {}
        bool operator()(Vector::const_reference p) const {
            return *s == p.first;}
    };

    void operator()(const std::string& word)
    {
        Vector::iterator it = std::find_if(
            words->begin(), words->end(), WordEqual(word));
        if (it == words->end())
            words->push_back(std::make_pair(word,1));
        else
            ++it->second;
    }
    Vector* words;
};

Answer 3

Ну, почему бы вам не использовать map?Это именно то, для чего это, отображение от одного к другому.От string (слово) до int (количество случаев) в вашем случае.Или вы должны использовать вектор?