Re[15]: Разработка на чистом C - C/C++

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

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

EP>>>Конкретный пример — бинарный поиск:
EP>>>

EP>>>template<typename I, typename P>
P>>....
P>>....
EP>>>

P>>Так это же совсем другое дело, здесь шаблоны как раз к месту применены.

EP>Здесь разговор не о том что шаблоны или макросы где-то применяют не к месту, а о том что
EP>

EP>если нужно понять как что-то работает, то смотреть лучше в C реализации, нежели в C++

EP>Вот я и прошу показать на простом примере как на C всё становится понятнее.
Я уже приводил ссылку на операции с полгонами.
Вот другой пример попроще: наибольший общий делитель

unsigned gcd(unsigned a, unsigned b) {
  unsigned c;
  while (a) {
     c = a; 
     a = b % a;
     b = c;
  }
  return b;
}

и http://www.boost.org/doc/libs/master/boost/math/common_factor_rt.hpp

template <typename Integer>
inline Integer gcd(Integer const &a, Integer const &b)
{
    return detail::optimal_gcd_select(static_cast<Integer>(gcd_traits<Integer>::abs(a)), static_cast<Integer>(gcd_traits<Integer>::abs(b)));
}
....

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

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

EP>>>Отсутствие компилятора это один из немногих случаев где оправданно использование C, по очевидным причинам.
_>>Есть еще причина. Т.к. C менее универсальный нежели С++ авторы вынужденые реализовывать конкретику, а не абстракции.
_>>Такая деятельность дисциплинирует, требует большей ответственности и усердия от ремеслеников, занимающихся подобным трудом.

EP>То есть программисты тратят свои ресурсы на "усердие" и прочую борьбу с языком.

_>>И если нужно понять как что-то работает, то смотреть лучше в C реализации, нежели в C++.
_>>Что бы далеко не ходить можно посмотреть реализацию базовых операций с полигонами GPC и boost

EP>Конкретный пример — бинарный поиск:
EP>

EP>template<typename I, typename P>
EP>I partition_point_m(I first, I last, P p)
EP>{
EP>    while(first != last)
EP>    {
EP>        I middle = first + (last - first)/2;
EP>        if( p(*middle) )
EP>            last = middle;
EP>        else
EP>            first = middle + 1;
EP>    }
EP>    return first;
EP>}
EP>

EP>Покажи аналог на C — вот и сравним где понятнее как "что-то работает"

Разве это бинарный поиск. Это сферический конь в вакууме.
Вот реальный бинарный поиск
на C++ http://llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm (искать по binary_search и __lower_bound)
на C http://lxr.free-electrons.com/source/lib/bsearch.c
Разница, видна?

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

EP>>Конкретный пример — бинарный поиск:
EP>>

EP>>template<typename I, typename P>
EP>>I partition_point_m(I first, I last, P p)
EP>>

EP>>Покажи аналог на C — вот и сравним где понятнее как "что-то работает"

_>Разве это бинарный поиск. Это сферический конь в вакууме.

Самый что ни на есть реальный.

_>Вот реальный бинарный поиск

Вообще-то вот

_>на C++ http://llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm (искать по binary_search и __lower_bound)

Там же и partition_point

_>на C http://lxr.free-electrons.com/source/lib/bsearch.c
_>Разница, видна?

Конечно видна, версия C замусорена размером элемента, звёздами пустоты, при этом работает только для плоских массивов, да ещё и медленнее (runtime sizeof, косвенный вызов предиката). Версия же C++ работает для всего начиная с Forward Interator — например для односвязных списков (логарифмическое количество сравнений).

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

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

S>>Или даже вот в таком.

P>На С это будет так

Трудно себе представить, чтобы под современной ОС на современном компутере, не в ядре, strdup() вернул бы не NULL, и программа при этом бы сумела обработать ошибку и выжить. Гораздо вероятмее, что strdup() найдет место в адресном пространстве (а не реальную память), и вернет какой-то адрес, а вот при попытке обратиться по этому адресу выяснится, что памяти-то и нет, и программа получит SIGFAULT.

Поэтому я бы, для очистки совести, обернул бы strdup() и подобные функции в нечто, что вместо возврата NULL аварийно завершается с разумной диагностикой, и сильно упростил бы этот код.

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

EP>>Конкретный пример — бинарный поиск:
EP>>

EP>>template<typename I, typename P>
EP>>I partition_point_m(I first, I last, P p)
EP>>{
EP>>    while(first != last)
EP>>    {
EP>>        I middle = first + (last - first)/2;
EP>>        if( p(*middle) )
EP>>            last = middle;
EP>>        else
EP>>            first = middle + 1;
EP>>    }
EP>>    return first;
EP>>}
EP>>

.section .text
    .globl faq1
    .type faq1, @function

/* // параметры вызова функции func(fist, last, p)
    movq $first, %rdi
    movq $last, %rsi
    movq $p, %rdx */

faq1:
    xorb %r11b, %r11b
loop1:
    movq %rsi, %r10
    subq %rdi, %r10
    shr  $2, %r10
    addq %rdi,%r10
    call *%rdx
    cmpb %r11b, %al
    jne el1
if1:
    movq %r10, %rsi
    jmp fi1
el1:
    movq %r10, %rdi
fi1:
    cmpq %rdi, %rsi
    jne loop1
    movq %rdi, %rax
    retq

не намного больше чем в с/c++
но выполняться будет намного быстрее
ни один компилятор не оптимизирует
чаще всего компиляторы с аргументами работают через стек

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

T>не намного больше чем в с/c++

В C++ работает для произвольных последовательностей, начиная от Forward Sequence, для любых типов элементов и т.п.

T>но выполняться будет намного быстрее

Это с call *%rdx внутри ?

T>ни один компилятор не оптимизирует

ШТА?

T>чаще всего компиляторы с аргументами работают через стек

Зависит от calling convention, на x64 часто через регистры (пока их хватает), НО — это не имеет никакого отношения к делу, ибо вызов partition_point на C++ будет заинлайнен, то есть вообще не будет никакого call.

template<typename I, typename P>
I partition_point_m(I first, I last, P p)
{
    while(first != last)
    {
        I middle = first + (last - first)/2;
        if( p(*middle) )
            last = middle;
        else
            first = middle + 1;
    }
    return first;
}

int *concrete_test(int *first, int *last)
{
    return partition_point_m(first, last, [](int x){ return x <= 42; });
}

clang++ -std=c++11 -O3 -Wall -pedantic main.cpp -S && cat main.s

    .text
    .file    "main.cpp"
    .globl    _Z13concrete_testPiS_
    .align    16, 0x90
    .type    _Z13concrete_testPiS_,@function
_Z13concrete_testPiS_:                  # @_Z13concrete_testPiS_
    .cfi_startproc
# BB#0:
    cmpq    %rsi, %rdi
    je    .LBB0_1
# BB#2:
    movabsq    $9223372036854775806, %rax # imm = 0x7FFFFFFFFFFFFFFE
    .align    16, 0x90
.LBB0_3:                                # %.lr.ph.i
                                        # =>This Inner Loop Header: Depth=1
    movq    %rsi, %rcx
    subq    %rdi, %rcx
    movq    %rcx, %rdx
    sarq    $2, %rdx
    shrq    $63, %rcx
    addq    %rdx, %rcx
    andq    %rax, %rcx
    leaq    (%rdi,%rcx,2), %rdx
    cmpl    $43, (%rdi,%rcx,2)
    leaq    4(%rdi,%rcx,2), %rcx
    cmovlq    %rdx, %rsi
    cmovgeq    %rcx, %rdi
    cmpq    %rsi, %rdi
    jne    .LBB0_3
# BB#4:                                 # %"_Z17partition_point_mIPiZ13concrete_testS0_S0_E3$_0ET_S2_S2_T0_.exit"
    movq    %rsi, %rax
    retq
.LBB0_1:
    movq    %rdi, %rsi
    movq    %rsi, %rax
    retq
.Lfunc_end0:
    .size    _Z13concrete_testPiS_, .Lfunc_end0-_Z13concrete_testPiS_
    .cfi_endproc

    .ident    "clang version 3.8.0 (tags/RELEASE_380/final 263969)"
    .section    ".note.GNU-stack","",@progbits

LIVE DEMO

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

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

T>>не намного больше чем в с/c++

EP>В C++ работает для произвольных последовательностей, начиная от Forward Sequence, для любых типов элементов и т.п.

T>>но выполняться будет намного быстрее

EP>Это с call *%rdx внутри ?

T>>ни один компилятор не оптимизирует

EP>ШТА?

T>>чаще всего компиляторы с аргументами работают через стек

EP>Зависит от calling convention, на x64 часто через регистры (пока их хватает), НО — это не имеет никакого отношения к делу, ибо вызов partition_point на C++ будет заинлайнен, то есть вообще не будет никакого call.
EP>

EP>template<typename I, typename P>
EP>I partition_point_m(I first, I last, P p)
EP>{
EP>    while(first != last)
EP>    {
EP>        I middle = first + (last - first)/2;
EP>        if( p(*middle) )
EP>            last = middle;
EP>        else
EP>            first = middle + 1;
EP>    }
EP>    return first;
EP>}

EP>int *concrete_test(int *first, int *last)
EP>{
EP>    return partition_point_m(first, last, [](int x){ return x <= 42; });
EP>}
EP>

EP>clang++ -std=c++11 -O3 -Wall -pedantic main.cpp -S && cat main.s
EP>

EP>    .text
EP>    .file    "main.cpp"
EP>    .globl    _Z13concrete_testPiS_
EP>    .align    16, 0x90
EP>    .type    _Z13concrete_testPiS_,@function
EP>_Z13concrete_testPiS_:                  # @_Z13concrete_testPiS_
EP>    .cfi_startproc
EP># BB#0:
EP>    cmpq    %rsi, %rdi
EP>    je    .LBB0_1
EP># BB#2:
EP>    movabsq    $9223372036854775806, %rax # imm = 0x7FFFFFFFFFFFFFFE
EP>    .align    16, 0x90
EP>.LBB0_3:                                # %.lr.ph.i
EP>                                        # =>This Inner Loop Header: Depth=1
EP>    movq    %rsi, %rcx
EP>    subq    %rdi, %rcx
EP>    movq    %rcx, %rdx
EP>    sarq    $2, %rdx
EP>    shrq    $63, %rcx
EP>    addq    %rdx, %rcx
EP>    andq    %rax, %rcx
EP>    leaq    (%rdi,%rcx,2), %rdx
EP>    cmpl    $43, (%rdi,%rcx,2)
EP>    leaq    4(%rdi,%rcx,2), %rcx
EP>    cmovlq    %rdx, %rsi
EP>    cmovgeq    %rcx, %rdi
EP>    cmpq    %rsi, %rdi
EP>    jne    .LBB0_3
EP># BB#4:                                 # %"_Z17partition_point_mIPiZ13concrete_testS0_S0_E3$_0ET_S2_S2_T0_.exit"
EP>    movq    %rsi, %rax
EP>    retq
EP>.LBB0_1:
EP>    movq    %rdi, %rsi
EP>    movq    %rsi, %rax
EP>    retq
EP>.Lfunc_end0:
EP>    .size    _Z13concrete_testPiS_, .Lfunc_end0-_Z13concrete_testPiS_
EP>    .cfi_endproc

EP>    .ident    "clang version 3.8.0 (tags/RELEASE_380/final 263969)"
EP>    .section    ".note.GNU-stack","",@progbits
EP>

EP>

LIVE DEMO

в исходной задаче не было функции. Но с учетом тела функции сравни

.section .text
    .globl faq1
    .type faq1, @function

/* // параметры вызова функции func(fist, last, p)
    movq $first, %rdi
    movq $last, %rsi
    movq $p, %rdx */

faq1:
    xorb %r11b, %r11b
loop1:
    movq %rsi, %r10
    subq %rdi, %r10
    shr  $1, %r10
    addq %rdi,%r10
    cmpl $43, (%r10)  /* add */
    jl el1
if1:
    movq %r10, %rsi
    jmp fi1
el1:
    movq %r10, %rdi
fi1:
    cmpq %rdi, %rsi
    jne loop1
    movq %rdi, %rax
    retq

обрати внимание на цикл и количество обращений к памяти

Здравствуйте, Evgeny.Panasyuk, Вы писали:
или вот так с учетом cmovgeq cmovqlq

.section .text
    .globl faq1
    .type faq1, @function

faq1:
    movq %rsi, %r10
    subq %rdi, %r10
    shr  $1, %r10
    addq %rdi,%r10
    cmpl $43, (%r10)  /* add */
    cmovgeq %r10, %rsi
    cmovlq %r10, %rdi
    cmpq %rdi, %rsi
    jne faq1
    movq %rdi, %rax
    retq

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

T>в исходной задаче не было функции. Но с учетом тела функции сравни

Ты предлагаешь вручную выписывать бинарный поиск на ассемблере под каждую комбинацию предикатов, типов элементов, не говоря уже о типах последовательностей?

T>обрати внимание на цикл и количество обращений к памяти

По одному обращению на итерацию, и там и там в cmp. А ты сколько насчитал?
И кстати, у тебя нет проверки на входные first==last.

И судя по всему тебя не O3 интересует, а что-то типа Os:

#include <algorithm>

int *concrete_test(int *first, int *last)
{
    return std::partition_point(first, last, [](int x){ return x > 42; });
}

g++ -std=c++11 -Os -DNDEBUG -Wall -pedantic main.cpp -S && cat main.s

    .file    "main.cpp"
    .text
    .globl    _Z13concrete_testPiS_
    .type    _Z13concrete_testPiS_, @function
_Z13concrete_testPiS_:
.LFB799:
    .cfi_startproc
    subq    %rdi, %rsi
    movq    %rdi, %rax
    sarq    $2, %rsi
.L3:
    testq    %rsi, %rsi
    jle    .L2
    movq    %rsi, %rdx
    sarq    %rdx
    leaq    (%rax,%rdx,4), %rcx
    cmpl    $42, (%rcx)
    jg    .L7
    movq    %rdx, %rsi
    jmp    .L3
.L7:
    subq    %rdx, %rsi
    leaq    4(%rcx), %rax
    decq    %rsi
    jmp    .L3
.L2:
    ret
    .cfi_endproc
.LFE799:
    .size    _Z13concrete_testPiS_, .-_Z13concrete_testPiS_
    .ident    "GCC: (GNU) 6.1.0"
    .section    .note.GNU-stack,"",@progbits

LIVE DEMO

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

T>или вот так с учетом cmovgeq cmovqlq
T>

T>.section .text
T>    .globl faq1
T>    .type faq1, @function

T>faq1:
T>    movq %rsi, %r10
T>    subq %rdi, %r10
T>    shr  $1, %r10
T>    addq %rdi,%r10
T>    cmpl $43, (%r10)  /* add */
T>    cmovgeq %r10, %rsi
T>    cmovlq %r10, %rdi
T>    cmpq %rdi, %rsi
T>    jne faq1
T>    movq %rdi, %rax
T>    retq
T>

Корабли лавировали, лавировали, да не вылавировали — вариант цикла нарушен — диапазон [first..last) должен уменьшаться как минимум на один элемент на каждой итерации, иначе зацикливание.

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

не лишайте красноглазиков насиженных мест

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

_>Вот другой пример попроще: наибольший общий делитель
_>

_>unsigned gcd(unsigned a, unsigned b) {
_>  unsigned c;
_>  while (a) {
_>     c = a; 
_>     a = b % a;
_>     b = c;
_>  }
_>  return b;
_>}
_>

_>и http://www.boost.org/doc/libs/master/boost/math/common_factor_rt.hpp
_>

_>template <typename Integer>
_>inline Integer gcd(Integer const &a, Integer const &b)
_>{
_>    return detail::optimal_gcd_select(static_cast<Integer>(gcd_traits<Integer>::abs(a)), static_cast<Integer>(gcd_traits<Integer>::abs(b)));
_>}
_>....
_>

А теперь предположим, что вместо unsigned вдруг понадобился какой-нибудь bigint. И все, на Си приходится руками переписывать "a = b % a" в "bigint_mod(&a, &b, &a)". А с шаблонным решением достаточно определить свои traits и ВСЕ алгоритмы, их использующие автоматически начинают поддерживать ваш тип.

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

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

T>>или вот так с учетом cmovgeq cmovqlq
T>>

T>>.section .text
T>>    .globl faq1
T>>    .type faq1, @function

T>>faq1:
T>>    movq %rsi, %r10
T>>    subq %rdi, %r10
T>>    shr  $1, %r10
T>>    addq %rdi,%r10
T>>    cmpl $43, (%r10)  /* add */
T>>    cmovgeq %r10, %rsi
T>>    cmovlq %r10, %rdi
T>>    cmpq %rdi, %rsi
T>>    jne faq1
T>>    movq %rdi, %rax
T>>    retq
T>>

EP>Корабли лавировали, лавировали, да не вылавировали — вариант цикла нарушен — диапазон [first..last) должен уменьшаться как минимум на один элемент на каждой итерации, иначе зацикливание.

ну прям обижаешь
middle(%r10)=first[%rdi]+(last[%rsi]-fist[%rdi])/2[shr]
в квадртаных скобках соотвествие переменному

movq %rsi, %r10
subq %rdi, %r10
shr  $1, %r10
addq %rdi,%r10

можно еще убрать 2 оператора из цикла
за счет команды lzcnt предварительный расчет количества итераций
но добавятся 3 до цикла
и еще в формуле(алгоритме) заложена ошибка
middle при некоторых обстоятельствах никогда не достигнет last
middle — last = 0 или 1
надо учитывать epsilon
http://math.semestr.ru/optim/dichotomy.php
либо last делать заглушкой

тут я чуток ошибся
ранее епсилон учитывается в конструкции first = middle + 1;
я как то пропустил

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

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

_>>Вот другой пример попроще: наибольший общий делитель
_>>

_>>unsigned gcd(unsigned a, unsigned b) {
_>>  unsigned c;
_>>  while (a) {
_>>     c = a; 
_>>     a = b % a;
_>>     b = c;
_>>  }
_>>  return b;
_>>}
_>>

_>>и http://www.boost.org/doc/libs/master/boost/math/common_factor_rt.hpp
_>>

_>>template <typename Integer>
_>>inline Integer gcd(Integer const &a, Integer const &b)
_>>{
_>>    return detail::optimal_gcd_select(static_cast<Integer>(gcd_traits<Integer>::abs(a)), static_cast<Integer>(gcd_traits<Integer>::abs(b)));
_>>}
_>>....
_>>

_>>unsigned gcd(unsigned a, unsigned b) {
_>>  unsigned c;
_>>  while (a) {
_>>     c = a; 
_>>     a = b % a;
_>>     b = c;
_>>  }
_>>  return b;
_>>}
_>>

_>>и http://www.boost.org/doc/libs/master/boost/math/common_factor_rt.hpp
_>>

_>>template <typename Integer>
_>>inline Integer gcd(Integer const &a, Integer const &b)
_>>{
_>>    return detail::optimal_gcd_select(static_cast<Integer>(gcd_traits<Integer>::abs(a)), static_cast<Integer>(gcd_traits<Integer>::abs(b)));
_>>}
_>>....
_>>

B>А теперь предположим, что вместо unsigned вдруг понадобился какой-нибудь bigint. И все, на Си приходится руками переписывать "a = b % a" в "bigint_mod(&a, &b, &a)". А с шаблонным решением достаточно определить свои traits и ВСЕ алгоритмы, их использующие автоматически начинают поддерживать ваш тип.

Вот где будет копипаста — в траитсах. Вместо преписи 4х строк надо 100500 строк вспомогательных сущностей.
С++ способствует излишним обобщения. А если я туда комплексные числа суну, а если полиномы — не порядок надо предусмотреть.
Поэтому в C++ любой алгоритм пытаются сделать универсальным.
Хотя если взглянуть правде в глаза то бывает что для решения задачи даже точного алгоритма нет и используют приближенные решения и всякие эвристика. Тут лафа для обобщений.

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

_>Вот где будет копипаста — в траитсах. Вместо преписи 4х строк надо 100500 строк вспомогательных сущностей.
_>С++ способствует излишним обобщения. А если я туда комплексные числа суну, а если полиномы — не порядок надо предусмотреть.
_>Поэтому в C++ любой алгоритм пытаются сделать универсальным.
_>Хотя если взглянуть правде в глаза то бывает что для решения задачи даже точного алгоритма нет и используют приближенные решения и всякие эвристика. Тут лафа для обобщений.

все можно реализовать на любом языке особенно на низком уровне.
Вопрос удобства, времени на код, желания.
Но не стоит для микроконтроллера с памятью в 1к писать программы на c++/c
также системные вещи не стоить писать на c++, не контролируемого кода много будет.
Когда запускается прога, ее исполнение никогда не начинается с main.
Сначала разные иниты, потом статические классы(конструкторы)
а ф функции main в конечном счете можно написать только exit(0), а вся программа будет в конструкторах
Каждый язык имеет сильные и слабые стороны.
Дождемся искусственного интеллекта, может тогда будет интересная форма составления алгоритма.

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

EP>>Корабли лавировали, лавировали, да не вылавировали — вариант цикла нарушен — диапазон [first..last) должен уменьшаться как минимум на один элемент на каждой итерации, иначе зацикливание.
T>

T>ну прям обижаешь
T>middle(%r10)=first[%rdi]+(last[%rsi]-fist[%rdi])/2[shr]
T>в квадртаных скобках соотвествие переменному

Ошибка не вычислении middle, а в выборе следующего диапазона.
У тебя выбирается либо [first..middle), либо [middle..last) — во втором случае ошибка. middle может равняться first с предыдущей операции, например если всего один элемент в диапазоне, и если продолжать в [middle..last) — то получается зацикливание. Более того, значение *middle уже проверенно предикатом, и его проверять вообще не нужно.

T>и еще в формуле(алгоритме) заложена ошибка
T>middle при некоторых обстоятельствах никогда не достигнет last
T>middle — last = 0 или 1
T>надо учитывать epsilon
T>http://math.semestr.ru/optim/dichotomy.php
T>либо last делать заглушкой

Это у тебя в алгоритме ошибка — об этом я и сказал когда говорил про лавировку и вариант цикла. И никакой epsilon не нужен. Сравни с тем вариантом который я привёл ранее.

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

T>Но не стоит для микроконтроллера с памятью в 1к писать программы на c++/c

Я пишу периодически. Вот, например, неплохая либа https://github.com/KonstantinChizhov/Mcucpp

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

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

T>>Но не стоит для микроконтроллера с памятью в 1к писать программы на c++/c

Ops>Я пишу периодически. Вот, например, неплохая либа https://github.com/KonstantinChizhov/Mcucpp

какое-нибудь устройство делал со своей прошивкой ?

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

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

EP>>>Конкретный пример — бинарный поиск:
EP>>>

EP>>>template<typename I, typename P>
EP>>>I partition_point_m(I first, I last, P p)
EP>>>

EP>>>Покажи аналог на C — вот и сравним где понятнее как "что-то работает"

_>>Разве это бинарный поиск. Это сферический конь в вакууме.

EP>Самый что ни на есть реальный.

_>>Вот реальный бинарный поиск

EP>Вообще-то вот

_>>на C++ http://llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm (искать по binary_search и __lower_bound)

EP>Там же и partition_point

_>>на C http://lxr.free-electrons.com/source/lib/bsearch.c
_>>Разница, видна?

EP>Конечно видна, версия C замусорена размером элемента, звёздами пустоты, при этом работает только для плоских массивов, да ещё и медленнее (runtime sizeof, косвенный вызов предиката). Версия же C++ работает для всего начиная с Forward Interator — например для односвязных списков (логарифмическое количество сравнений).

Вот я с вас поражаюсь. Это разговор слепого с глухонемым. Вы как сектант: "Верую и всё и никакие доводы не собъют меня с пути истенного! Только C++ и пророк его Бьярн Страустрап" Я разве против. Да гибко, Да универсально, Да во многих случаях 99.9% нафиг не надо, да компилятор мегабайтами треша лопатит, да копипаста всёравно никуда не девается, да сбоирает проект по 7 часов и хорошо...
Из за излишнего обобщения, которое возникает само собой в шаблонах, вам приходится рассматривать ситуации которые вам нафиг не нужны в реальном проекте.

Бинарный поиск и разбиение на две части это разные алгоритмы.

// partition_point

template<class _ForwardIterator, class _Predicate>
_ForwardIterator
partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
{
    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
    difference_type __len = _VSTD::distance(__first, __last);
    while (__len != 0)
    {
        difference_type __l2 = __len / 2;
        _ForwardIterator __m = __first;
        _VSTD::advance(__m, __l2);
        if (__pred(*__m))
        {
            __first = ++__m;
            __len -= __l2 + 1;
        }
        else
            __len = __l2;
    }
    return __first;
}

// stable_partition

Тут никакого мусора только нужное

И сам файл очень удобен для чтения никуда не надо лазить и никаких лишних сущностей или черезмерных обобщений.

	От:	kov_serg
	Дата:	06.11.16 21:07
	Оценка:

	От:	kov_serg
	Дата:	06.11.16 21:26
	Оценка:	-1

	От:	Evgeny.Panasyuk
	Дата:	06.11.16 22:55
	Оценка:	+1

От:	Pzz	https://github.com/alexpevzner
Дата:	06.11.16 23:09
Оценка:

	От:	tranzit
	Дата:	07.11.16 00:44
	Оценка: