Собственно идеологический вопрос.

Зачем изначально было делать std::sort на RandomAccessIterator?

Во первых всегда можно разделить имплементации для рандом и бидирекшен.
Во вторых обычно используемый introsort отлично работает с обьеими видами итераторов.

И наоборот std::lower_bound эффективно работать может только с RandomAccessIterator но принимает Forward.


Это меня одного озадачивает ?

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

M>Собственно идеологический вопрос.
...
M>Это меня одного озадачивает ?

согласен, не симметрично. можно запилить запрос в https://groups.google.com/a/isocpp.org/forum/?fromgroups#!forum/lib-proposals (главное сыроежку туда не пускать).
может быть сочли редко-используемым, может было мало времени и просмотрели(stl вообще предложили на очень позднем этапе стандартизации), может ещё что.

примечательно что на MSVC10 std::stable_sort работает с std::list

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

P>согласен, не симметрично. можно запилить запрос в https://groups.google.com/a/isocpp.org/forum/?fromgroups#!forum/lib-proposals (главное сыроежку туда не пускать).

точнее походу сюда https://groups.google.com/a/isocpp.org/forum/?fromgroups#!forum/std-proposals

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

P>>согласен, не симметрично. можно запилить запрос в https://groups.google.com/a/isocpp.org/forum/?fromgroups#!forum/lib-proposals (главное сыроежку туда не пускать).
P>точнее походу сюда https://groups.google.com/a/isocpp.org/forum/?fromgroups#!forum/std-proposals

кстати, может они планирует сделать это в контексте концепций. То есть не будут тратить время на формальный proposal пока нет концепций. Так как с ними определение будет по-другому выглядеть.

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

M>Собственно идеологический вопрос.

M>Зачем изначально было делать std::sort на RandomAccessIterator?

M>Во первых всегда можно разделить имплементации для рандом и бидирекшен.
M>Во вторых обычно используемый introsort отлично работает с обьеими видами итераторов.
ORLY? И как выбирать pivor element, используя median three, если нет RandomAccess?

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

sdf>ORLY? И как выбирать pivor element, используя median three, если нет RandomAccess?

Например так же как и для RandomAccess. Асимптотику это не изменит.

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

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

sdf>>ORLY? И как выбирать pivor element, используя median three, если нет RandomAccess?

M>Например так же как и для RandomAccess. Асимптотику это не изменит.
ORLY?

Так же, как RandomAccess и без изменения асимптотики, его выбирать нельзя, т.к. для RandomAccess поиск серединного элемента занимает O(1), а для bidirectional чтобы получить средний элемент вам нужно будеть сделать O(длины участка/2) вызовов ++

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

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

sdf>Так же, как RandomAccess и без изменения асимптотики, его выбирать нельзя, т.к. для RandomAccess поиск серединного элемента занимает O(1), а для bidirectional чтобы получить средний элемент вам нужно будеть сделать O(длины участка/2) вызовов ++

Хотя, верно, все равно потом делается прохол по всему участку. Будет медленнее. но асмтотика останется той же. Вопрос закрыт.

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

M>Собственно идеологический вопрос.

M>Зачем изначально было делать std::sort на RandomAccessIterator?

M>Во первых всегда можно разделить имплементации для рандом и бидирекшен.
Вроде бы основная проблема была в том, что разделить имплементацию для рандом и бидерекшен во время включения в стандарт STL, было нетривиально.

Концептов в С++ нет до сих пор, а SFINAE тогде вроде еще не было.

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

M>>Зачем изначально было делать std::sort на RandomAccessIterator?
M>>Во первых всегда можно разделить имплементации для рандом и бидирекшен.
sdf>Вроде бы основная проблема была в том, что разделить имплементацию для рандом и бидерекшен во время включения в стандарт STL, было нетривиально.
sdf>Концептов в С++ нет до сих пор, а SFINAE тогде вроде еще не было.

ну в lower_bound же разделили.

"tag dispatching" : http://www.boost.org/community/generic_programming.html

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

sdf>Вроде бы основная проблема была в том, что разделить имплементацию для рандом и бидерекшен во время включения в стандарт STL, было нетривиально.

Дык и обобщенную можно собрать без накладных расходов.

Piko:

P>кстати, может они планирует сделать это в контексте концепций.

Насколько я помню, первый стандарт с Concepts планировали выпустить примерно в 2022 году. Тем, кому хочется иметь дело с этой фичей, осталось подождать совсем чуть-чуть

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

P>>кстати, может они планирует сделать это в контексте концепций.
M>Насколько я помню, первый стандарт с Concepts планировали выпустить примерно в 2022 году. Тем, кому хочется иметь дело с этой фичей, осталось подождать совсем чуть-чуть

а когда следующий?
по мне так то лучше дольше и надёжней.
по поводу концепций — я больше всего жду аксиомы.

Забавное наблюдение. Наколеночная qsort обогнала MSVC2010 реализацию std::list<>.sort на случайных данных , раза в 2ва

template<class IterT>
void qSort(IterT begIt, IterT endIt)
{
    int dist = std::distance(begIt, endIt);
    if(dist <= 1 )
        return;

      IterT low  = begIt;
      IterT high = endIt; --high;

      IterT i = low;
      IterT j = high;
      IterT x = low; std::advance(x, (dist+1)/2);

      int i_idx = 0;
      int j_idx = dist - 1;
      int x_idx = i_idx + (dist+1)/2;


      do {
          while(*i < *x){ ++i; ++i_idx;}
          while(*j > *x){ --j; --j_idx;}

          if(i_idx <= j_idx)
          {
              std::iter_swap(i,j);

              if(i_idx == x_idx)
              {
                  x_idx = j_idx;
                  x = j;
              }else  if(j_idx == x_idx)
              {
                  x_idx = i_idx;
                  x = i;
              }


              {++i; ++i_idx;}
              {--j; --j_idx;}
          }
      } while(i_idx <= j_idx);
 
      if(0 < j_idx)
      {
          qSort(low, ++j);
      }
      if(i_idx < (dist-1))
      {
          qSort(i, ++high);
      }
  }

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

M>Забавное наблюдение. Наколеночная qsort обогнала MSVC2010 реализацию std::list<>.sort на случайных данных , раза в 2ва

1. попробуй отсортировать последовательность {N, N-1, N-2, N-3, N-4 ...}

2. ISO, list sort:
"Effects: Sorts the list according to the operator< or the comp function object. This operation shall be
stable: the relative order of the equivalent elements is preserved. If an exception is thrown the order
of the elements in *this is unspecified. Does not affect the validity of iterators and references.
23 Complexity: Approximately N logN comparisons, where N is distance(begin(), end())."

Стабильность + Сложность(даже не сложность, а количество сравнений). А что у тебя?

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

P>1. попробуй отсортировать последовательность {N, N-1, N-2, N-3, N-4 ...}

Зачем мне ?


P>Стабильность + Сложность(даже не сложность, а количество сравнений). А что у тебя?

Написал же, "наколеночный qsort"

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

P>>1. попробуй отсортировать последовательность {N, N-1, N-2, N-3, N-4 ...}
M>Зачем мне ?

ну ты же говоришь, что типа у тебя быстрее в два раза.
Сравни на этих данных

P>>Стабильность + Сложность(даже не сложность, а количество сравнений). А что у тебя?
M>Написал же, "наколеночный qsort"

ты хинт не понял. во-первых qsort не стабильна http://en.wikipedia.org/wiki/Stable_sort#Stability, во вторых у неё сложность может быть и O(N^2) http://en.wikipedia.org/wiki/Quicksort

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

P>ну ты же говоришь, что типа у тебя быстрее в два раза.
P>Сравни на этих данных

Я написал же, что на случайных данных, внимательно читай.

P>ты хинт не понял. во-первых qsort не стабильна http://en.wikipedia.org/wiki/Stable_sort#Stability, во вторых у неё сложность может быть и O(N^2) http://en.wikipedia.org/wiki/Quicksort

Хинт я не понял.

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

P>>ну ты же говоришь, что типа у тебя быстрее в два раза.
P>>Сравни на этих данных
M>Я написал же, что на случайных данных, внимательно читай.

я прочитал

ты сделай проверку, не ленись.
http://ideone.com/g3tZD
добавь сравнение времени, и отпиши, что быстрее

P>>ты хинт не понял. во-первых qsort не стабильна http://en.wikipedia.org/wiki/Stable_sort#Stability, во вторых у неё сложность может быть и O(N^2) http://en.wikipedia.org/wiki/Quicksort
M>Хинт я не понял.

list.sort обладает свойством стабильности + его сложность всегда O(NlogN).
В твоём же варианте стабильности нет. И сложность может взрываться в самый неподходящий момент, на самом не подходящем N, до O(N^2).

Ну ещё хинт.
Сравни std::sort и std::stable_sort.

В чём вообще смысл? Что ты хотел показать своим сравнением? То что qsort может обгонять стабильную сортировку с O(NlogN) сложностью? Ну и?

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

Поскипано.

P>В чём вообще смысл?

"Забавное наблюдение"