Inserting into a sorted array of structs in C++

I have to implement a vector using an array in C++ that is used to count the number of unique words from the input. It reads the input and then adds to the words to a struct which contains its count and the unique word and then this is added to the vector. I have successfully implemented insert. The problem is that I can't get the inserting/ incrementing unique word count to work (elements aren't added to the vector). Here is my code:

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

It's hard to say anything without seeing your implementation of Vector. If we assume it adheres to the standard container conventions (and doesn't have an error in trying to do so): you iterate starting with 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 ofVector`, but it would take some tricky code to make it work.)

At a higher level, there seems a basic inconsistency: you're keeping the vector sorted, but still using linear search. If you're using linear search, there's no point in keeping the vector sorted; just use:

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...
}

(although I'd probably append to end, recover the iterator to the newly inserted element, and treat it as if it were found).

Alternatively, if you're keeping the vector sorted, use a binary search, not a linear search.

In either case, put the search in a separate function. (If this wasn't homework, I'd say just use std::vector and either std::find_if or std::lower_bound.)

Also, why the new in the innermost else? A more reasonable approach would be to provide a constructor for wordCount (which sets the count to 0), and do something like:

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

The definition of found will depend on whether you're using binary search or not. In terms of the standard, this would be either:

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;

or

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;

You should probably strive for something similar, with a separate lookup function, returning either end, or the position for the insertion when the value isn't found.

This keeps the various concerns clearly separated, and avoids the excessive nesting in your code. (You should probably try to avoid break in general, and in multiply nested ifs, it is completely inacceptable—you'll notice that one of the other people answering missed them, and misunderstood the control flow because of it.)

Well, why don't you use a map? That's exactly what it's for, mapping from one thing to another. From a string (the word) to an int (the number of occurences) in your case. Or do you have to use a vector?

Try to use a 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"));

The Counter functor could look like this

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

Using a 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;
};