» Главная
eXcode.ru » Статьи » С / С++
» Новости
» Опросы
» Файлы
» Журнал



Пользователей: 0
Гостей: 6





Алгоритмы библиотеки STL 3




Операции сортировки и отношения (Sorting and related operations)

     Все операции в этом разделе имеют две версии: одна берёт в качестве параметра функциональный объект типа Compare, а другая использует operator< .

     Compare - функциональный объект, который возвращает значение, обратимое в bool. Compare comp используется полностью для алгоритмов, принимающих отношение упорядочения. comp удовлетворяет стандартным аксиомам для полного упорядочения и не применяет никакую непостоянную функцию к разыменованному итератору. Для всех алгоритмов, которые берут Compare, имеется версия, которая использует operator< взамен. То есть comp(*i, *j) == true по умолчанию для *i < *j == true.

     Последовательность сортируется относительно компаратора comp, если для любого итератора i, указывающего на элемент в последовательности, и любого неотрицательного целого числе n такого, что i + n является допустимым итератором, указывающим на элемент той же самой последовательности, comp(*( i + n), *i) == false.

     В описаниях функций, которые имеют дело с упорядочивающими отношениями, мы часто используем представление равенства, чтобы описать такие понятия, как устойчивость. Равенство, к которому мы обращаемся, не обязательно operator==, а отношение равенства стимулируется полным упорядочением. То есть два элементa a и b считаются равными, если и только если !(a < b) && !(b < a).

Сортировка (Sort)

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare> 
void sort(RandomAccessIterator first, RandomAccessIterator last, 
    Compare соmр);

     sort сортирует элементы в диапазоне [first, last). Делается приблизительно NIogN (где N равняется last - first) сравнений в среднем. Если режим наихудшего случая важен, должны использоваться stable_sort или partial_sort.

template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare> 
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, 
    Compare comp);

     stable_sort сортирует элементы в диапазоне [first, last). Он устойчив, то есть относительный порядок равных элементов сохраняется. Делается максимум N(logN)2 (гдеN равняется last - first) сравнений; если доступна достаточная дополнительная память, тогда зто - NlogN.

template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
     RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
     RandomAccessIterator last, Compare comp);

     partial_sort помещает первые middle - first сортированных элементов из диапазона [first, last) в диапазон [first, middle). Остальная часть элементов в диапазоне [middle, last) помещена в неопределённом порядке. Берётся приблизительно (last - first) * log(middle - first) сравнений.

template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first, 
    InputIterator last, RandomAccessIterator result_first, 
    RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator, 
    class Compare> 
RandomAccessIterator partial_sort_copy(InputIterator first, 
    InputIterator last, RandomAccessIterator result_first, 
    RandomAccessIterator result_last, Compare comp);

     partial_sort_copy помещает первые min(last - first, result_last - result_first) сортированных элементов в диапазон [result_first, result_first + min(last - first, result_last - result_first)). Возвращается или result_last, или result_first +(last - first), какой меньше. Берётся приблизительно (last - first) * log(min(last - first, result_last - result_first)) сравнений.

N-й элемент (Nth element)

template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
     RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, 
    RandomAccessIterator last, Compare comp);

     После операции nth_element элемент в позиции, указанной nth, является элементом, который был бы в той позиции, если бы сортировался целый диапазон. Также для любого итератора i в диапазоне [first, nth) и любого итератора j в диапазоне [nth, last) считается, что !(*i > *j) или comp(*i, *j) == false. Операция линейна в среднем.

Двоичный поиск (Binary search)

     Все алгоритмы в этом разделе - версии двоичного поиска. Они работают с итераторами не произвольного доступа, уменьшая число сравнений, которое будет логарифмическим для всех типов итераторов. Они особенно подходят для итераторов произвольного доступа, так как эти алгоритмы делают логарифмическое число шагов в структуре данных. Для итераторов не произвольного доступа они выполняют линейное число шагов.

template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, 
    const T& value);

template <class ForwardIterator, class T, class Compare>  
ForwardIterator lower_bound(ForwardIterator first, 
    ForwardIterator last, const T& value, Compare comp);

     lower_bound находит первую позицию, в которую value может быть вставлено без нарушения упорядочения. lower_bound возвращает самый дальний итератор i в диапазоне [first, last) такой, что для любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: *j < value или comp(*j, value) == true. Делается максимум log(last - first) + 1 сравнений.

template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, 
    ForwardIterator last, const T& value);

template <class ForwardIterator, class T, class Compare>
ForwardIterator  upper_bound(ForwardIterator first, 
    ForwardIterator last, const T& value, Compare comp);

     upper_bound находит самую дальнюю позицию, в которую value может быть вставлено без нарушения упорядочения. upper_bound возвращает самый дальний итератор i в диапазоне [first, last) такой, что для любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: !(value < *j) или comp(value, *j) == false. Делается максимум log(last - first) + 1 сравнений.

template <class ForwardIterator, class T>
ForwardIterator equal_range(ForwardIterator first, 
    ForwardIterator last, const T& value);

template <class ForwardIterator, class T, class Compare>  
ForwardIterator equal_range(ForwardIterator first, 
    ForwardIterator last, const T& value, 
    Compare comp);

     equal_range находит самый большой поддиапазон [i, j) такой, что значение может быть вставлено по любому итератору k в нём. k удовлетворяет соответствующим условиям: !(*k < value) && !(value < *k) или comp(*k, value) == false && comp(value, *k) == false. Делается максимум 2 * log(last - first) + 1 сравнений.

template <class ForwardIterator, class T>
ForwardIterator binary_search(ForwardIterator first, 
    ForwardIterator last, const T& value);

template <class ForwardIterator, class T, class Compare>
ForwardIterator binary_search(ForwardIterator first, 
    ForwardIterator last, const T& value, 
    Compare comp);

     binary_search возвращает истину, если в диапазоне [first, last) имеется итератор i, который удовлетворяет соответствующим условиям: !(*i < value) && !(value < *i) или comp(*i, value) == false && comp(value, *i) == false. Делается максимум log(last - first) + 2 сравнений.

Объединение (Merge)

template <class InputIterator1, class Input Iterator2, 
    class OutputIterator>
OutputIterator merge(InputIterator1 first1, 
    InputIterator1 last1, InputIterator2 first2, 
    InputIterator2 last2, OutputIterator result);

template <class InputIterator1, class InputIterator2, 
    class OutputIterator, class Compare> 
OutputIterator merge(InputIterator1 first1, 
    InputIterator1 last1, InputIterator2 first2, 
    InputIterator2 last2, OutputIterator result, 
    Compare comp);

     merge объединяет два сортированных диапазона [first1, last1) и [first2, last2) в диапазон [result, result + (last1 - first1) + (last2 - first2)). Объединение устойчиво, то есть для равных элементов в двух диапазонах элементы из первого диапазона всегда предшествуют элементам из второго. merge возвращает result + (last1 - first1) + (last2 - first2). Выполняется максимально (last1 - first1) + (last2 - first2) - 1 сравнений. Результат merge не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first, 
    BidirectionalIterator middle, 
    BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first, 
    BidirectionalIterator middle, 
    BidirectionalIterator last, 
    Compare comp);

     inplace_merge объединяет два сортированных последовательных диапазона [first, middle) и [middle, last), помещая результат объединения в диапазон [first, last). Объединение устойчиво, то есть для равных элементов в двух диапазонах элементы из первого диапазона всегда предшествуют элементам из второго. Когда доступно достаточно дополнительной памяти, выполняется максимально (last - first) - 1 сравнений. Если никакая дополнительная память не доступна, может использоваться алгоритм со сложностью O(NlogN).

Операции над множеством для сортированных структур (Set operations on sorted structures)

     Этот раздел определяет все основные операции над множеством для сортированных структур. Они даже работают с множествами с дубликатами, содержащими множественные копии равных элементов. Семантика операций над множеством обобщена на множества с дубликатами стандартным способом, определяя объединение, содержащее максимальное число местонахождений каждого элемента, пересечение, содержащее минимум, и так далее.

template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1, 
    InputIterator2 first2, InputIterator2 last2);

template <class InputIterator1, class InputIterator2, 
    class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1, 
    InputIterator2 first2, InputIterator2 last2, 
    Compare comp);

     includes возвращает true, если каждый элемент в диапазоне [first2, last2) содержится в диапазоне [first1, last1). Иначе возвращается false. Выполняется максимально ((last1 - first1) + (last2 - first2)) * 2 - 1 сравнений.

template <class InputIterator1, class InputIterator2, 
    class OutputIterator>
OutputIterator set_union(InputIterator1 first1, 
    InputIterator1 last1, InputIterator2 first2, 
    InputIterator2 last2, OutputIterator result);

template <class InputIterator1, class InputIterator2, 
    class OutputIterator, class Compare>
OutputIterator set_union(InputIterator1 first1, 
    InputIterator1 last1, InputIterator2 first2, 
    InputIterator2 last2, OutputIterator result, 
    Compare comp);

     set_union создаёт сортированное объединение элементов из двух диапазонов. Он возвращает конец созданного диапазона. set_union устойчив, то есть, если элемент присутствует в обоих диапазонах, он копируется из первого диапазона. Выполняется максимально ((last1 - first1) + (last2 - first2)) * 2 - 1 сравнений. Результат set_union не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

template <class InputIterator1, class InputIterator2, 
    class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, 
    InputIterator1 last1, InputIterator2 first2, 
    InputIterator2 last2, OutputIterator result);

template <class InputIterator1, class InputIterator2, 
    class OutputIterator, class Compare>
OutputIterator set_intersection(InputIterator1 first1, 
    InputIterator1 last1, InputIterator2 first2, 
    InputIterator2 last2, OutputIterator result, 
    Compare comp);

     set_intersection создаёт сортированное пересечение элементов из двух диапазонов. Он возвращает конец созданного диапазона. Гарантируется, что set_intersection устойчив, то есть, если элемент присутствует в обоих диапазонах, он копируется из первого диапазона. Выполняется максимально ((last1 - first1) + (last2 - first2)) * 2 - 1 сравнений. Результат set_union не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

template <class InputIterator1, class InputIterator2, 
    class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, 
    InputIterator1 last1, InputIterator2 first2, 
    InputIterator2 last2, OutputIterator  result);

template <class InputIterator1, class InputIterator2, 
    class OutputIterator, class Compare>
OutputIterator set_difference(InputIterator1 first1, 
    InputIterator1 last1, InputIterator2 first2, 
    InputIterator2 last2, OutputIterator result, 
    Compare comp);

     set_difference создаёт сортированную разность элементов из двух диапазонов. Он возвращает конец созданного диапазона. Выполняется максимально ((last1 - first1) + (last2 - first2)) * 2 - 1 сравнений. Результат set_difference не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

template <class InputIterator1, class InputIterator2, 
    class OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 first1, 
    InputIterator1 last1, InputIterator2 first2, 
    InputIterator2 last2, OutputIterator result);

template <class InputIterator1, class InputIterator2, 
    class OutputIterator, class Compare>
OutputIterator set_symmetric_difference(InputIterator1 first1, 
    InputIterator1 last1, InputIterator2 first2, 
    InputIterator2 last2, OutputIterator result, 
    Compare comp);

     set_symmetric_difference создаёт сортированную симметричную разность элементов из двух диапазонов. Он возвращает конец созданного диапазона. Выполняется максимально ((last1 - first1) + (last2 - first2)) * 2 - 1 сравнений. Результат set_symmetric_difference не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

Операции над пирамидами (Heap operations)

     Пирамида - специфическая организация элементов в диапазоне между двумя итераторами произвольного доступа [a, b). Два её ключевые свойства: (1) *a - самый большой элемент в диапазоне, (2) *a может быть удалён с помощью pop_heap или новый элемент добавлен с помощью push_heap за O(logN) время. Эти свойства делают пирамиды полезными для приоритетных очередей. make_heap преобразовывает диапазон в пирамиду, a sort_heap превращает пирамиду в сортированную последовательность.

template <class RandomAccessIterator>
void push_heap(RandomAccessIterator first, 
    RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, 
    RandomAccessIterator last, Compare comp);

     push_heap полагает, что диапазон [first, last - 1) является соответствующей пирамидой, и надлежащим образом помещает значение с позиции last - 1 в результирующую пирамиду [first, last). Выполняется максимально log(last - first) сравнений.

template <class RandomAccessIterator> 
void pop_heap(RandomAccessIterator first, 
    RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, 
    RandomAccessIterator last, 
    Compare comp);

     pop_heap полагает, что диапазон [first, last) является соответствующей пирамидой, затем обменивает значения в позициях first и last - 1 и превращает [first, last - 1) в пирамиду. Выполняется максимально 2 * log(last - first) сравнений.

template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, 
    RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, 
    RandomAccessIterator last, 
    Compare comp);

     make_heap создает пирамиду из диапазона [first, last). Выполняется максимально 3 * (last - first) сравнений.

template <class RandomAccessIterator> 
void sort_heap(RandomAccessIterator first, 
    RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, 
    RandomAccessIterator last, Compare comp);

     sort_heap сортирует элементы в пирамиде [first, last). Выполняется максимально NlogN сравнений, где N равно last - first. sort_heap не устойчив.

Минимум и максимум (Minimum and maximum)

template <class T> 
const T& min(const T& a, const T& b);

template <class T, class Compare> 
const T& min(const T& a, const T& b, Compare comp);

template <class T> 
const T& max(const T& a, const T& b);

template <class T, class Compare> 
const T& max(const T& a, const T& b, Compare comp);

     min возвращает меньшее, а max большее. min и max возвращают первый параметр, когда их параметры равны.

template <class ForwardIterator> 
ForwardIterator max_element(ForwardIterator first, 
    ForwardIterator last);

template <class ForwardIterator, class Compare>
ForwardIterator max_element(ForwardIterator first, 
    ForwardIterator last, Compare comp);

     max_element возвращает первый такой итератор i в диапазоне [first, last), что для любого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*i < *j) или comp(*i, *j) == false. Выполняется точно max((last - first) - 1, 0) соответствующих сравнений.

template <class ForwardIterator> 
ForwardIterator min_element(ForwardIterator first, 
    ForwardIterator last);

template <class ForwardIterator, class Compare>
ForwardIterator min_element(ForwardIterator first, 
    ForwardIterator last, Compare comp);

     min_element возвращает первый такой итератор i в диапазоне [first, last), что для любого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*j < *i) или comp(*j, *i) == false. Выполняется точно max((last - first) - 1, 0) соответствующих сравнений.

Лексикографическое сравнение (Lexicographical comparison)

template <class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2);

template <class InputIterator1, class InputIterator2, class Compare> 
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
    InputIterator2 first2, InputIterator2 last2, Compare comp);

     lexicographical_compare возвращает true, если последовательность элементов, определённых диапазоном [first1, last1), лексикографически меньше, чем последовательность элементов, определённых диапазоном [first2, last2). Иначе он возвращает ложь. Выполняется максимально 2 * min((last1 - first1), (last2 - first2)) сравнений.

Генераторы перестановок (Permutation generators)

template <class BidirectionalIterator> 
bool next_permutation(BidirectionalIterator first, 
    BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first, 
    BidirectionalIterator last, Compare comp);

     next_permutation берёт последовательность, определённую диапазоном [first, last), и трансформирует её в следующую перестановку. Следующая перестановка находится, полагая, что множество всех перестановок лексикографически сортировано относительно operator< или comp. Если такая перестановка существует, возвращается true. Иначе он трансформирует последовательность в самую маленькую перестановку, то есть сортированную по возрастанию, и возвращает false. Максимально выполняется (last - first)/2 перестановок.

template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, 
    BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first, 
    BidirectionalIterator last, Compare comp);

     prev_permutation берёт последовательность, определённую диапазоном [first, last), и трансформирует её в предыдущую перестановку. Предыдущая перестановка находится, полагая, что множество всех перестановок лексикографически сортировано относительно operator< или comp. Если такая перестановка существует, возвращается true. Иначе он трансформирует последовательность в самую большую перестановку, то есть сортированную по убыванию, и возвращает false. Максимально выполняется (last - first)/2 перестановок.

К началу статьи





Добавил: LedWormДата публикации: 2006-03-14 10:10:41
Рейтинг статьи:3.00 [Голосов 5]Кол-во просмотров: 10269

Комментарии читателей

Всего комментариев: 0
Ваше имя: *
Текст записи: *
Имя:

Пароль:



Регистрация

Каким браузером вы пользуйтесь?
MS Internet Explorer
22% (66)
Mozilla
3% (8)
Mozilla Firefox
26% (77)
Opera
43% (130)
Konqueror
1% (3)
Netscape
0% (0)
Lynx
0% (0)
Galeon
0% (0)
Другим
5% (15)

Проголосовало: 299
Обнаружен узел www.microsoft.com.
Ожидается ответ...
Обезврежен узел www.microsoft.com
Рейтинг: 2.9/10 (7)
Посмотреть все анекдоты