Здравствуйте, Шахтер, Вы писали:

Ш>Здравствуйте, Cyberax, Вы писали:

C>>Шахтер wrote:
>>> Упустил то, что невозможен двухуровневый break.
>>> Тут правда можно использовать break; -- continue;
C>>По-моему, исходный вариант с goto был понятнее

Ш>Дык о том и речь. Мне кажется, что данный пример демонстрирует вредность догм в программировании. Одна из таких догм -- не используй goto.
Ш>Обычно он не нужен. Но иногда его использование совершенно оправдано.

явно не этот случай
вариант Кодта вполне ничего.

Здравствуйте, Шахтер, Вы писали:

V>>мож что-где упустил, но общий аргумент должен быть ясен.. Ж)
Ш>Упустил то, что невозможен двухуровневый break.
а ну да, но не в этом суть.. Ж)

Здравствуйте, night beast, Вы писали:

NB>Здравствуйте, Шахтер, Вы писали:

Ш>>Здравствуйте, Cyberax, Вы писали:

C>>>Шахтер wrote:
>>>> Упустил то, что невозможен двухуровневый break.
>>>> Тут правда можно использовать break; -- continue;
C>>>По-моему, исходный вариант с goto был понятнее

Ш>>Дык о том и речь. Мне кажется, что данный пример демонстрирует вредность догм в программировании. Одна из таких догм -- не используй goto.
Ш>>Обычно он не нужен. Но иногда его использование совершенно оправдано.

NB>явно не этот случай
NB>вариант Кодта вполне ничего.

Он вводит лишние вычисления в код (либо лишние данные).

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Шахтер, Вы писали:

Ш>Здравствуйте, night beast, Вы писали:

NB>>Здравствуйте, Шахтер, Вы писали:

Ш>>>Дык о том и речь. Мне кажется, что данный пример демонстрирует вредность догм в программировании. Одна из таких догм -- не используй goto.
Ш>>>Обычно он не нужен. Но иногда его использование совершенно оправдано.

NB>>явно не этот случай
NB>>вариант Кодта вполне ничего.

Ш>Он вводит лишние вычисления в код (либо лишние данные).

O(n)
это всего лишь показывает, что красивый код не всегда самый быстрый, и наоборот.
ничего личного, но меня твой исходный текст не впечатлил.

Здравствуйте, night beast, Вы писали:

NB>это всего лишь показывает, что красивый код не всегда самый быстрый, и наоборот.

Для меня красота в программировании -- это функциональность и экономность.
Так же как и в жизни -- дама, заросшая жиром, некрасива.
Но это, конечно, дело вкуса.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Шахтер, Вы писали:

Ш>Для меня красота в программировании -- это функциональность и экономность.
А "
Ш>дама, заросшая жиром, некрасива
" -- это нефункционально или неэкономно?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Шахтер, Вы писали:

Ш>>Для меня красота в программировании -- это функциональность и экономность.
E>А "
Ш>>дама, заросшая жиром, некрасива
E>" -- это нефункционально или неэкономно?

И то, и другое.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Шахтер, Вы писали:

А>>Если подразумевается классическое слияние то одной строчки не хватает:

Ш>Нет, строится объединения множеств. Результирующая выходная последовательность строго монотонная.

Так, так, так... Если предположить не строго монотонные входные последовательности, то этот алгоритм будет для каждой "постоянной" подпоследовательности выбирать более длинную (из присутствующих в двух входных массивах). Является ли это существенно частью спецификации? Или все таки можно сразу завязываться на тот факт, что входные последовательности строго монотонны. Если да, то это несколько меняет дело...

Здравствуйте, Андрей Тарасевич, Вы писали:

А>>>Если подразумевается классическое слияние то одной строчки не хватает:

Ш>>Нет, строится объединения множеств. Результирующая выходная последовательность строго монотонная.

АТ>Так, так, так... Если предположить не строго монотонные входные последовательности, то этот алгоритм будет для каждой "постоянной" подпоследовательности выбирать более длинную (из присутствующих в двух входных массивах). Является ли это существенно частью спецификации? Или все таки можно сразу завязываться на тот факт, что входные последовательности строго монотонны. Если да, то это несколько меняет дело...

При наличии такой гарантии можно предложить следующий вариант (предполагая, что значения 'CmpLess', 'CmpEqual' и 'CmpGreater' сравнимы через операторы сравнения и дают именно такой порядок, а также что итераторы удволетворяют требованиям 'std::swap')

std::pair<int> cmp(CmpEqual, CmpLess);

while (a)
  for (std::swap(a, b), std::swap(cmp.first, cmp.second); a && Cmp(*a, *b) <= cmp.first; ++a)
    fun(*a);

for (; b; ++b)
  fun(*b);

Требование 'std::swap' можно, разумеется, обойти через указатели.

Можно также сделать так

do
{
  for (; a && (!b || Cmp(*a, *b) <= CmpEqual); ++a)
    fun(*a);

  for (; b && (!a || Cmp(*a, *b) > CmpEqual); ++b)
    fun(*b);

} while (a)

Хотя это просто не особо осмысленная попытка избавиться от отдельного обработчика "хвоста".

Ну и Настоящий Хакер, разумеется, воспользуется чем-то вроде Duff's device для избежания лишней проверки в вырожденном случае

switch (!a)
{
  do
  {
    case false:
      for (; a && (!b || Cmp(*a, *b) <= CmpEqual); ++a)
        fun(*a);

    case true:
      for (; b && (!a || Cmp(*a, *b) > CmpEqual); ++b)
        fun(*b);

  } while (a);
}

Бред, но не каждый же день подвернется возможность использовать Duff's device

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>Здравствуйте, Шахтер, Вы писали:

А>>>Если подразумевается классическое слияние то одной строчки не хватает:

Ш>>Нет, строится объединения множеств. Результирующая выходная последовательность строго монотонная.

АТ>Так, так, так... Если предположить не строго монотонные входные последовательности, то этот алгоритм будет для каждой "постоянной" подпоследовательности выбирать более длинную (из присутствующих в двух входных массивах). Является ли это существенно частью спецификации? Или все таки можно сразу завязываться на тот факт, что входные последовательности строго монотонны. Если да, то это несколько меняет дело...

Да, входные последовательности строго монотонны.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>Можно также сделать так

АТ>

АТ>do
АТ>{
АТ>  for (; a && (!b || Cmp(*a, *b) <= CmpEqual); ++a)
АТ>    fun(*a);

АТ>  for (; b && (!a || Cmp(*a, *b) > CmpEqual); ++b)
АТ>    fun(*b);

АТ>} while (a)
АТ>

В условиях цикла присутствуют !b и !a, которые являются инвариантами цикла.
Есть ещё один недостаток -- в начале цикл может быть холостым. После чего последует повторное сравнение.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Шахтер, Вы писали:

Ш>Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>>Можно также сделать так

АТ>>

АТ>>do
АТ>>{
АТ>>  for (; a && (!b || Cmp(*a, *b) <= CmpEqual); ++a)
АТ>>    fun(*a);

АТ>>  for (; b && (!a || Cmp(*a, *b) > CmpEqual); ++b)
АТ>>    fun(*b);

АТ>>} while (a)
АТ>>

Ш>В условиях цикла присутствуют !b и !a, которые являются инвариантами цикла.

Ну так я же сам прокомментировал это вариант, как просто попытку достичь самоцели: растворить обработку хвостов в основном цикле. В качестве "разумного" варианта предлагался только первый — со 'swap'.

Ш>Есть ещё один недостаток -- в начале цикл может быть холостым. После чего последует повторное сравнение.

Не совсем понимаю, о чем идет речь в этом случае.

Здравствуйте, Шахтер, Вы писали:

Ш>Что-то много всякой фигнёй в последнее время страдаем (особенно философской).

Фигня поскипана.

Решение — заменить финиш а, финиш Бэ на функции и не париться, лучшего решения нет. Учим матчасть.

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>Ну так я же сам прокомментировал это вариант, как просто попытку достичь самоцели: растворить обработку хвостов в основном цикле. В качестве "разумного" варианта предлагался только первый — со 'swap'.

А, тогда понятно.

Ш>>Есть ещё один недостаток -- в начале цикл может быть холостым. После чего последует повторное сравнение.

АТ>Не совсем понимаю, о чем идет речь в этом случае.

О том, что если в первом цикле мы вычислили Cmp(*a,*b) и получили >0, то мы этот цикл закончим и плавно войдем во второй, где снова вычислим это же выражение и получим тот же результат (фактически уже известный). Избыточное телодвижение. То же самое будет при переходе снизу вверх.
Если это была бы одиночная избыточность, это было бы ещё ничего, но постоянные повторения в цикле -- слишком жирно.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Шахтер, Вы писали:

template <class Range> 
template <class Collector>
typename ResultAttributes<typename Collector::FunctorType>::ResultType 
UnionGenType<Range>::operator () (Collector collector) const
{
    Range a=a_,b=b_;

    typedef typename Collector::FunctorType FunctorType;

    FunctorType fun(collector);

    //////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////
    struct s_finish_a
    {
        finish_a(Range &_a, FunctorType &_fun)
            :a(_a)
            ,fun(_fun)
        {
        }

        void build()
        {
            for(; +a ;++a) fun(*a);
        }

        typename ResultAttributes<typename Collector::FunctorType>::ResultType get_result()
        {
             build();

             return ResultAttributes<FunctorType>::GetResult(fun);
        }

        Range &a;
        FunctorType &fun;
    };

    //////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////
    struct s_finish_b
        : public s_finish_a
    {
        finish_a(Range &_a,Range &_b, FunctorType &_fun)
            :finish_a(_a,_fun)
            ,b(_b)
        {
        }

        typename ResultAttributes<typename Collector::FunctorType>::ResultType get_result()
        {
            build();

            for(; +b ;++b) fun(*b);

            return ResultAttributes<FunctorType>::GetResult(fun)
        }

        Range &b;
    };

    s_finish_a finish_a(a,fun);
    s_finish_b finish_b(a,b,fun);

    //////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////

    if( !a ) return finish_b.get_result();
    if( !b ) return finish_a.get_result();

    for(;;)
        switch( Cmp(*a,*b) )
    {
        case CmpLess :
            {
                fun(*a);
                ++a;

                if( !a ) return finish_b.get_result();
            }
            break;

        case CmpGreater :
            {
                fun(*b);
                ++b;

                if( !b ) return finish_a.get_result();
            }
            break;

        case CmpEqual :
            {
                fun(*a);
                ++a;
                ++b;

                if( !a ) return finish_b.get_result();
                if( !b ) return finish_a.get_result();
            }  
    }  

    return finish_b.get_result();
}

Здравствуйте, Шахтер, Вы писали:

Ш>Здравствуйте, Cyberax, Вы писали:

C>>Шахтер wrote:
>>> Упустил то, что невозможен двухуровневый break.
>>> Тут правда можно использовать break; -- continue;
C>>По-моему, исходный вариант с goto был понятнее

Ш>Дык о том и речь. Мне кажется, что данный пример демонстрирует вредность догм в программировании. Одна из таких догм -- не используй goto.
Ш>Обычно он не нужен. Но иногда его использование совершенно оправдано.
Не буду вдаваться в тонкости, но чем вас не устраивает такой код на пседоязыке:

while ((!A)&&(!B)) {
  if (A < B) {
    C = A;
    nextC; nextA;
  }
  else {
    C = B;
    nextC; nextB;
  }
}
while (!A) {
  C = A;
  nextC; nextA;
}
while (!B) {
  C = B;
  nextC; nextB;
}

По-моему очень даже внятный код!