1

毫无疑问，你们中的一些人已经看过我最近的帖子，都是关于同一个程序的。我一直遇到问题。重申一下：还在学习，不是很高级，不太了解指针，没有上课，根本不懂OOP概念等。这段代码只是将两个排序的向量fray和sarray合并为一个排序的向量向量。至少，我希望它是这样做的。告诉我：

    //int num is to find the size of the original vector and
    //build up farray and sarray; not used in the merge process
    int num = original.size() 
    std::vector<int> final;

    std::vector<int>::iterator it = farray.begin();
    std::vector<int>::iterator iter = sarray.begin();

    //farray.size() == (0 thru (num / 2))
    //sarray.size() == ((num / 2) thru num)
    for (;it != farray.end() && iter != sarray.end();) {
        if (*it > *iter) {
            final.push_back(*it);
            it++;
        }    
        else
        {
            final.push_back(*iter);
            iter++;
        }

            if (it == farray.end()) {
                for (int i = 0; iter < sarray.end(); i++) {
                    final.push_back(*iter);
                }
            }

            if (iter == sarray.end()) {
                for (int i = 0; it < farray.end(); i++) {
                    final.push_back(*iter);
                }
            }
        }

我重写了我的合并排序函数的合并部分，以便......好吧，让它工作。我实际上对这段代码有几个问题：

  1. 如果 for 循环在下一次传递时可能会改变它们，那么将我的最后两个 if 语句与 std::vector::iterators it && iter 进行比较是一种好的形式吗？
  2. iter 的值是否会在此循环的最后一次通过时发生变化并搞砸我的代码？将我的最后一个 if 语句放在 *it 和 *iter 比较之前吗？
  3. end() 成员函数是否引用了调用它的最后一个值？似乎它可能会以某种方式延伸过去。

编辑：我明天会回复所有回复，所以如果你想听更多，请回来查看。已经过了午夜。晚安。

4

5 回答 5

3

1. 可以将来自同一容器的迭代器与 for 循环条件进行比较，但这仅在您在 for 循环语句的增量部分或 for 循环本身的主体中移动一个或其他迭代器时才有意义。在这个 for 循环中，您可以比较iter，sarray.end()但 for 循环永远不会改变iter。这意味着要么没有迭代，要么 for 循环永远不会终止。此外，您可能想要使用!=而不是<用于比较。==并!=为所有迭代器工作，<不是。

            for (int i = 0; iter != sarray.end(); i++) {
                final.push_back(*iter);
            }

从iter您希望循环开始的地方开始，您可能需要这样的东西：

            for (; iter != sarray.end(); ++iter) {
                final.push_back(*iter);
            }

由于您仍在学习（尽管我们不是所有人！），通过这样的算法工作可能具有指导意义，但您应该知道std::merge哪个可能会满足您的需求。

std::merge( farray.begin(), farray.end(), sarray.begin(), sarray.end(), std::back_inserter( final ) );

（你需要#include <iterator>和<algorithm>。）

2. 我没有看到在外部 for 循环中增加 iter 或它会使后面的 for 循环中的逻辑无效，即 1. 中的点。

3. end()指向容器末尾的一个，因此您可以将其用于循环终止检查，但您不应该尝试取消引用“ ==”到“ .end()”的迭代器。

于 2009-04-20T06:55:08.113 回答
3

我没有检查你的算法的实现，我只是参考你的三个问题：

  1. 迭代器很像指向容器值的指针。这就像在 for 循环中使用 size_t i 然后 ++i 一样。你会觉得比较 farray[i] 和 sarray[i] 有问题吗？可能不是，因此没关系。
  2. 我在这里看到您在代码中所做的是，您只是读取了 *it 和 *iter 的值，实际上并没有更改它们，因此它们不会更改。
  3. end() 指向一个无效的地方。它不指向最后一个值，而是指向“之后”。如果你愿意，它就像“NULL”，因此如果(iter == sarray.end()) 为真，如果你写 *iter，你会崩溃，因为你不能取消引用等于 end() 的迭代器。
于 2009-04-20T06:58:43.940 回答
1

一些一般性建议：您需要考虑变量名称。称您的迭代器为“it”和“iter”有时会让您感到困惑。事实上，如果你仔细观察，它已经有了。如果“farray”和“sarray”是有意义的名称，那么“fiter”和“siter”怎么样。

另外，考虑一下合并排序在做什么。最后两个块只是为了“排空”哪个迭代器还剩下一些东西。所以他们不需要在第一个循环中。

我可能会把它写成（伪代码）：

while not (list1.empty and list2.empty):
    if list1.empty:
        result.push(list2.pop)
    else if list2.empty:
        result.push(list1.pop)
    else if list1.top > list2.top:
        result.push(list2.pop)
    else:
        result.push(list1.pop)

或者在有点生锈的货物崇拜的 C++ 中：

std::vector<int>::iterator fiter = farray.begin();
std::vector<int>::iterator siter = sarray.begin();

while (fiter != farray.end() || siter != sarray.end()) {
    if (fiter == farray.end())      final.push_back(*siter++);
    else if (siter == sarray.end()) final.push_back(*fiter++);
    else if (*fiter > *siter)       final.push_back(*siter++);
    else                            final.push_back(*siter++);
}
于 2009-04-20T06:56:59.823 回答
0

你有几件事要考虑。

首先，如果要合并两个范围，最好使用std::merge函数，而不是自己滚动。

您的代码有点难以阅读，因为您使用不同的缩进样式以及花括号的位置。选择一种风格并坚持下去。

for 循环的第一部分似乎是合并的正确实现：

for (;it != farray.end() && iter != sarray.end();) {
    if (*it > *iter) {
        final.push_back(*it);
        it++;
    }    
    else
    {
        final.push_back(*iter);
        iter++;
    }

...这应该是完成工作所需的全部内容。

循环的第二部分有几个问题：

   for (;it != farray.end() && iter != sarray.end();) {
         :   :
            if (it == farray.end()) {
                for (int i = 0; iter < sarray.end(); i++) {
                    final.push_back(*iter);
                }
            }

            if (iter == sarray.end()) {
                for (int i = 0; it < farray.end(); i++) {
                    final.push_back(*iter);
                }
            }
        }

一方面，for() 条件的编写使得两者都it不能iter指向end()它们各自集合的 ，否则循环结束。所以itcan never point to sarray.end(), itercan never point to farray.end(), 任何if语句都不能触发。它们都是死的（无法访问的）代码。

但即使它们不是死代码，它们也有错误。for(...)当迭代器指向集合的末尾时，条件中的条件会中断循环，但是这个迭代器永远不会移动，所以你有一个无限循环。

同样，这两个for(...)s 都是不需要的死代码，因为迭代器永远不能指向向量的末尾。

于 2009-04-20T12:28:33.757 回答
0

一个简单的评论：为什么不使用while (condition)而不是for(; !condition; ).

后者的构造是非标准的，难以理解！

于 2009-04-20T12:47:28.110 回答