c++ - 在 C++ 中插入到已排序的结构数组中

Question

我必须使用 C++ 中的数组实现一个 vector ，该数组用于计算输入中唯一单词的数量。它读取输入，然后将单词添加到包含其计数和唯一单词的结构中，然后将其添加到 vector 中。我已经成功地实现了插入。问题是我无法使插入/递增唯一字数起作用(元素未添加到 vector 中)。这是我的代码:

#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() 开始迭代，但立即访问 it-1。这是标准容器的未定义行为。 (我 不知道它会如何处理您的 Vector` 实现， 但需要一些棘手的代码才能使其工作。)

在更高的层面上，似乎存在一个基本的不一致:你是 保持 vector 排序，但仍然使用线性搜索。如果 你正在使用线性搜索，没有必要保留 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...
}

(尽管我可能会追加到结尾，将迭代器恢复到 新插入的元素，并将其视为已找到)。

或者，如果您要对 vector 进行排序，请使用二进制 搜索，而不是线性搜索。

无论哪种情况，都将搜索放在一个单独的函数中。 (如果这 不是家庭作业，我想说只是使用 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 中，它是 完全不能接受——你会注意到其中一个 其他回答的人错过了他们，并且误解了 因为它控制流程。)