VPF::std::sort vs std::list::sort - Форум программистов

korian

Дата 10.9.2008, 12:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 651
Регистрация: 8.3.2008
Где: Украина, Харьков

Репутация: 3
Всего: 17

что лучше использовать исходя из стандарта C++ std::sort() или std::list::sort(). С точки зрения логики, эфективнее должен работать std::list::sort. Но после того как я начал изучать boost, я понял, что логика C++ может быть совсем другой. Разные варианты частичной сепциализации шаблонов и перегрузка функций приводит к таким вариантам, которые сразу не поймешь.
Возможен вариант, что std::sort() в конечном итоге сводиться к тому же std::list::sort(), если в функцию переданы итераторы std::list::iterator. Так ли это?
Если std::sort сводиться к std::list::sort, то поидее лучше будет использовать std::sort, на случай если будет необходимо поменять тип контейнера на std::vector, например, у которого нету встроенной функции sort.
Интересно кто что думает по этому поводу и что говорит стандарт.

vinter

Дата 10.9.2008, 12:33 (ссылка)

(голосов:2)

Загрузка ...

Explorer

Профиль
Группа: Завсегдатай
Сообщений: 2735
Регистрация: 1.4.2006
Где: Н.Новгород

Репутация: 13
Всего: 56

если у контейнера есть ф-ия аналог, всегда нужно использовать ее.

Цитата(korian @ 10.9.2008, 13:20

)

std::sort()

разве будет работать с list? там по моему нужны random iterator

Цитата(korian @ 10.9.2008, 13:20

)

Если std::sort сводиться к std::list::sort, то поидее лучше будет использовать std::sort, на случай если будет необходимо поменять тип контейнера на std::vector, например, у которого нету встроенной функции sort.

нет, не надо гнаться за совместимостью контейнеров, ничего хорошего из этого не выйдет. По этому поводу хорошо написано у Майерса "Эффективное использование STL"
Вывод: используй list::sort

--------------------

Мой блог

korian

Дата 10.9.2008, 15:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 651
Регистрация: 8.3.2008
Где: Украина, Харьков

Репутация: 3
Всего: 17

Цитата(vinter @ 10.9.2008, 11:33

)

разве будет работать с list? там по моему нужны random iterator

понял. оказывается все на много проще smile

действительно std::sort работает только с RandomAccessIterator.
спасибо.

Cycle

Дата 12.9.2008, 11:43 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 59
Регистрация: 1.12.2007

Репутация: 3
Всего: 3

А кто мне объяснит, как binary_search работает на ForwardIterator ?

Mayk

Дата 12.9.2008, 11:50 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134

Цитата(Cycle @ 12.9.2008, 15:43

)

А кто мне объяснит, как binary_search работает на ForwardIterator ?

Можешь сам посмотреть в исходниках. в mingw341

Код


  /**
   *  @brief Determines whether an element exists in a range.
   *  @param  first   An iterator.
   *  @param  last    Another iterator.
   *  @param  val     The search term.
   *  @return  True if @a val (or its equivelent) is in [@a first,@a last ].
   *  @ingroup binarysearch
   *
   *  Note that this does not actually return an iterator to @a val.  For
   *  that, use std::find or a container's specialized find member functions.
  */
  template<typename _ForwardIterator, typename _Tp>
    bool
    binary_search(_ForwardIterator __first, _ForwardIterator __last,
                  const _Tp& __val)
    {
      // concept requirements
      // See comments on lower_bound.
      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
      __glibcxx_function_requires(_SameTypeConcept<_Tp,
        typename iterator_traits<_ForwardIterator>::value_type>)
      __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
      __glibcxx_requires_partitioned(__first, __last, __val);

      _ForwardIterator __i = std::lower_bound(__first, __last, __val);
      return __i != __last && !(__val < *__i);
    }

  /*
   *  @brief Finds the first position in which @a val could be inserted
   *         without changing the ordering.
   *  @param  first   An iterator.
   *  @param  last    Another iterator.
   *  @param  val     The search term.
   *  @return  An iterator pointing to the first element "not less than" @a val,
   *           or end() if every element is less than @a val.
   *  @ingroup binarysearch
  */
  template<typename _ForwardIterator, typename _Tp>
    _ForwardIterator
    lower_bound(_ForwardIterator __first, _ForwardIterator __last,
        const _Tp& __val)
    {
      typedef typename iterator_traits<_ForwardIterator>::value_type
    _ValueType;
      typedef typename iterator_traits<_ForwardIterator>::difference_type
    _DistanceType;

      // concept requirements
      // Note that these are slightly stricter than those of the 4-argument
      // version, defined next.  The difference is in the strictness of the
      // comparison operations... so for looser checking, define your own
      // comparison function, as was intended.
      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
      __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
      __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
      __glibcxx_requires_partitioned(__first, __last, __val);

      _DistanceType __len = std::distance(__first, __last);
      _DistanceType __half;
      _ForwardIterator __middle;

      while (__len > 0)
    {
      __half = __len >> 1;
      __middle = __first;
      std::advance(__middle, __half);
      if (*__middle < __val)
        {
          __first = __middle;
          ++__first;
          __len = __len - __half - 1;
        }
      else
        __len = __half;
    }
      return __first;
    }

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

vinter

Дата 12.9.2008, 14:55 (ссылка)

(нет голосов)

Загрузка ...

Explorer

Профиль
Группа: Завсегдатай
Сообщений: 2735
Регистрация: 1.4.2006
Где: Н.Новгород

Репутация: 13
Всего: 56

Цитата(Mayk @ 12.9.2008, 12:50

)

_ForwardIterator __i = std::lower_bound(__first, __last, __val);

вот уроды

--------------------

Мой блог

chipset

Дата 14.9.2008, 22:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 4071
Регистрация: 11.1.2003
Где: Seattle, US

Репутация: 27
Всего: 165

А разве "что быстрее" не зависит от конкретной реализации STL?

--------------------

Цитата(Jimi Hendrix)

Well, I stand up next to a mountain
And I chop it down with the edge of my hand

vinter

Дата 14.9.2008, 23:00 (ссылка)

(нет голосов)

Загрузка ...

Explorer

Профиль
Группа: Завсегдатай
Сообщений: 2735
Регистрация: 1.4.2006
Где: Н.Новгород

Репутация: 13
Всего: 56

chipset, зависит smile

--------------------

Мой блог

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »