Это хорошая форма для сравнения с изменением значений в цикле в C ++?

Question

Нет сомнений в том, что некоторые из вас видели мое недавнее сообщение, касающееся одной и той же программы. Я продолжаю сталкиваться с проблемами с этим. Повторим еще раз: все еще учимся, не очень продвинуты, плохо разбираемся в указателях, не занимаемся в классе, вообще не понимаем концепции ООП и т. Д. Этот код просто объединяет два отсортированных вектора, farray и 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. Это хорошая форма для сравнения с std :: vector :: iterators it && iter для моих последних двух операторов if, если цикл for может изменить их при следующем проходе?
2. Изменится ли значение iter и его значения на последнем проходе этого цикла и испортит мой код? Поместит ли мои последние операторы if сравнение с * it и * iter?
3. Ссылочная функция end () ссылается на последнее значение того, что ее вызывает? Кажется, что это может как-то простираться мимо него.

РЕДАКТИРОВАТЬ: Я отвечу на все ответы завтра, так что проверьте, если вы хотите услышать больше. Уже полночь. Спокойной ночи.

Answer 1

Я не проверял реализацию вашего алгоритма, я просто сошлюсь на три ваших вопроса:

1. Итераторы очень похожи на указатели на значения контейнера. Это похоже на использование size_t i и затем ++ i в цикле for. Вы считаете, что сравнивать farray [i] с sarray [i] проблематично? вероятно нет, поэтому все в порядке.
2. Я вижу, что вы делаете здесь в своем коде, что вы просто читаете значения * it и * iter, на самом деле вы их не меняете, поэтому они не изменятся.
3. Конец () указывает на недопустимое место. Он указывает не на последнее значение, а на «после». Это похоже на «NULL», если вы захотите, поэтому если (iter == sarray.end ()) имеет значение true, вы упадете, если напишите * iter, потому что вы не можете разыменовать итератор, который равен end ().

Answer 2

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. Я не вижу увеличения iter или его во внешнем цикле for, делающего недействительной логику в последующем цикле for, в точке 1. в сторону.

3. end() указывает на один конец конца контейнера, так что вы можете использовать его для проверки завершения цикла, но вы не должны пытаться разыменовать итератор с "==" до ".end()".

Answer 3

Несколько общих советов: вам нужно подумать об именах переменных. Называние ваших итераторов '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++);
}

Answer 4

Один простой комментарий: почему бы не использовать while (condition) вместо for(; !condition; ).

Последняя конструкция нестандартна и трудна для понимания!

Answer 5

У вас есть несколько вещей, чтобы подумать здесь.

Во-первых, если вы объединяете два диапазона, вам было бы гораздо лучше использовать функцию 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() их соответствующей коллекции, иначе цикл заканчивается. Так что it никогда не может указывать на sarray.end(), iter никогда не может указывать на farray.end(), и ни одно из операторов if не может срабатывать. Они оба являются мертвым (недоступным) кодом.

Но даже если они не были мертвым кодом, у них есть ошибки. Условие в for(...) прерывает цикл, когда итератор указывает на конец коллекции, но этот итератор никогда не перемещается, поэтому у вас есть бесконечный цикл.

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