C++按字母顺序对结构 vector 进行排序

Question

我有一个任务要完成。我需要创建一个程序来读取输入文件，将每个单词以及该单词被读取的次数(因此是结构)存储到一个 vector 中。这些值然后需要按字母顺序打印出来。

我想出了一些我认为正确的方法:

struct WordInfo {
string text;
int count; 
} uwords, temp;

string word;
int count = 0; //ignore this. For a different part of the task
vector<WordInfo> uwords;

while (cin >> word) {
    bool flag = false;
    count += 1;
    for (int i = 0; i < uwords.size(); i++) {
        if (uwords[i].text == word) {
            flag = true;
            uwords[i].count += 1;
        }
    }
    if (flag == false) {
        if (count == 1) { //stores first word into vector
            uwords.push_back(WordInfo());
            uwords[0].count = 1;
            uwords[0].text = word;
        } else {
            for (int i = 0; i < uwords.size(); i++) {
                if (word < uwords[i].text) {
                    uwords.push_back(WordInfo());
                    WordInfo temp = {word, 1};
                    uwords.insert(uwords.begin() + i, temp);
                }
            }
        }
    }
}

现在我遇到的问题是，当我运行程序时，它似乎陷入了无限循环，我不明白为什么。虽然我已经做了足够多的测试以意识到它可能在最后一个 if 语句中，但我修复它的尝试并不好。任何帮助表示赞赏。干杯。

编辑:我忘了说，我们必须使用 vector 类，我们可以使用的东西有限，排序不是一个选项:(

Answer 1

            if (word < uwords[i].text) {
                uwords.push_back(WordInfo());
                WordInfo temp = {word, 1};
                uwords.insert(uwords.begin() + i, temp);
            }

好好看看这段代码:

首先，它实际上会在您的列表中插入 2 个单词；一次是使用 push_back 的“空”，一次是使用 insert。只要当前单词小于 i 位置的单词，它就会执行此操作。

一旦插入，就会有 2 个新元素要经过；一个实际上在 i 的当前位置，所以在下一次迭代中，我们将再次比较同一个词 - 所以你的循环卡住了，因为索引 i 每次增加 1迭代，但是 i 的增加只会越过刚刚插入的元素!

为了快速解决，您想 (1) 搜索前一个单词比当前单词“小”但下一个单词大的位置。有点像

if (uwords[i-1].text < word && word < uwords[i].text) {

(2) 并且您想摆脱 push_back 调用。

此外，(3) 您可以在 if 条件为真后中断循环 - 您已经插入 then，无需进一步迭代。 (4) 通过一些条件调整，count == 1 实际上可以合并到循环中。修改后的代码部分(将替换您的整个 if (code == false) block - 警告，尚未测试):

if (!flag) {
    for (int i = 0; i <= uwords.size(); ++i) {
        if ((i == 0 || uwords[i-1].text < word) &&
            (i == uwords.size() || word < uwords[i].text)) {
            WordInfo temp = {word, 1};
            uwords.insert(uwords.begin() + i, temp);
            break;
        }
    }
}