Эти алгоритмы всегда выполняют не менее3n/2-2сравнений, что в любом случае является нижней границей по количеству сравнений (Кормен, Лейзерсон, Ривест: «Введение в алгоритмы», раздел 9.1, Упражнение 9.1-). Алгоритмы по существу сравнивают элементы в парах, выполняя 1 сравнение для первых двух элементов, затем 3 сравнения для каждой оставшейся пары элементов (один для заказа элементов и один для обновления каждого минимума и максимума). Когда число элементов нечетное, последний необходимо сравнить с текущим минимумом, а также с текущим максимумом. Кроме того, дляminmax, в случаях, когда равенство двух участников в паре может произойти, и обновление хранит второе, мы сохраняем первое, чтобы проверить в конце, если обновление должно было сохранить первое (в случае равенства). Трудно предсказать, будет ли выполнено последнее сравнение или нет, следовательно, самое большее в обоих случаях.

Эти алгоритмы всегда выполняют не менее3n/2-2сравнений, что в любом случае является нижней границей по количеству сравнений. Метод такой же, как в примечании.выше, и, как и выше, когда число элементов нечетное, последний необходимо сравнить с текущим минимумом, а также с текущим максимумом. Мы можем избежать последнего сравнения, если первое успешно, следовательно,самое большеевместоточнов странном случае.

Обоснование:

Этот проект был первоначально предложен и одобрен в официальном обзоре. Поскольку потребность в Boost.tuple стала очевидной (из-за ограниченийstd::pair), стало также раздражающим требовать другую библиотеку дляminmax_element, которая в ней не нуждается. Следовательно, разделение на два файла заголовка.Передний итераторявляется модельюПередний итератор.

• Передний итераторявляется модельюПередний итератор.
• Бинарный Предикатявляется модельюБинарный Предикат.
• Форвардиотератортип значения конвертируется вдвоичный прогнозпервый тип аргумента и второй тип аргумента.

• Все вариантыmin_elementиmax_elementвыполняют точно(n-1)сравнения,
• minmax_element,first_min_first_max_elementиlast_min_last_max_elementпроводят самое большее3(n/2)-1сравнения, еслиnчетно и ненулево, и самое большее3(n/2)+1, еслиnнечетно,
• first_min_last_max_element, иlast_min_first_max_elementвыполняют точно3n/2-2сравнения, если n равно и не равно нулю, и самое большее3(n/2), еслиnнечетно,

int main()
{
  using namespace std;
  boost::tuple<int const&, int const&> result1 = boost::minmax(1, 0);
  assert( result1.get<0>() == 0 );
  assert( result1.get<1>() == 1 );
  list<int> L;
  generate_n(front_inserter(L), 1000, rand);
  typedef list<int>::const_iterator iterator;
  pair< iterator, iterator > result2 = boost::minmax_element(L.begin(), L.end());
  cout << "The smallest element is " << *(result2.first) << endl;
  cout << "The largest element is  " << *(result2.second) << endl;
  assert( result2.first  == std::min_element(L.begin(), L.end());
  assert( result2.second == std::max_element(L.begin(), L.end());
}

[2] These algorithms always perform at least 3n/2-2 comparisons, which is a lower bound on the number of comparisons in any case (Cormen, Leiserson, Rivest: "Introduction to Algorithms", section 9.1, Exercise 9.1-). The algorithms essentially compare the elements in pairs, performing 1 comparison for the first two elements, then 3 comparisons for each remaining pair of elements (one to order the elements and one for updating each the minimum and and the maximum). When the number of elements is odd, the last one needs to be compared to the current minimum and also to the current maximum. In addition, for minmax, in cases where equality of the two members in the pair could occur, and the update stores the second, we save the first to check at the end if the update should have stored the first (in case of equality). It's hard to predict if the last comparison is performed or not, hence the at most in both cases.

[3] These algorithms always perform at least 3n/2-2 comparisons, which is a lower bound on the number of comparisons in any case. The method is the same as in note [2] above, and like above, when the number of elements is odd, the last one needs to be compared to the current minimum and also to the current maximum. We can avoid the latter comparison if the former is successful, hence the at most instead of exactly in the odd case.

Rationale:

Я знаю о проблемах с std::min и std::max, и все дебаты, которые продолжаются (пожалуйста, проконсультируйтесь).Статья Александрескуи ссылки на нее. Но я не рассматриваю цель этой библиотеки как исправление чего-то, что является частью стандарта C++. Я смиренно думаю, что это выходит за рамки этой библиотеки. Скорее, я следую стандарту, просто предоставляя еще одну функцию той же семьи. Если кто-то еще хочет исправить std::min, их исправление, вероятно, будет применяться для повышения::minmax.

Why no min/max_element_if?

В первой версии библиотеки я предложил_ifверсии всех алгоритмов (ну, не всех, потому что это было бы слишком много). Однако для этого просто нет причин, и все версии, которые у меня были, были так же быстро реализованы с использованием отличногоБиблиотека. А именно, призыв кmin_element_if (первый, последний, пред)будет так же хорошо реализован:<

     // equivalent to min_element_if(first, last, pred)
     min_element(boost::make_filter_iterator(first, last, pred),
                 boost::make_filter_iterator(last, last, pred));

Discussion: about std::max_element

Это обоснование несколько исторично, но объясняет, почему все эти функцииfirst/last_min/max_element.

Стандарт C++ требует, чтобыstd::min_elementиstd::max_elementвозвращали первый экземпляр наименьших и крупнейших элементов (в отличие, скажем, от последнего). Этот произвольный выбор имеет некоторую последовательность: В случае v типа vector, например, верно, чтоstd::min_element(v.begin(),v.end(),std::less()) == std::max_element(v.begin(),v.end(),std:: greater()).

Конечно, в этом нет ничего плохого: это просто вопрос выбора. Еще один способ определить min_element и max_element - определить их как первый и последний элементы, если диапазон был стабильно отсортирован. (Сортстабильныйнеобходим для разграничения итераторов, имеющих одинаковое значение.) В этом случае мин должен вернуть первую инстанцию, а макс - последнюю. Затем обе функции связаныreverse_iterator(std::first_min_element(v.begin(),v.end(),std::less())) == std::last_max_element(v.rbegin(),v.rend(),std:: greater()). Это определение тонко отличается от предыдущего.

Проблема определения возникает, когда человек пытается спроектировать элемент minmax_element, используя процедуру, предложенную в (Cormen, Leiserson, Rivest: «Введение в алгоритмы», раздел 9.1). Ондолжениметь возможность вывести алгоритм, используя только3n/2сравнения, если[первый, последний]имеетnэлементов, но если попытаться написать функцию, называемуюfirst_min_first_max_element(), которая возвращает обаstd::min_elementиstd::max_elementв паре, тривиальная реализация не работает. Проблема, довольно тонко, заключается в равных элементах: Мне пришлось некоторое время думать, чтобы найти способ выполнить только три сравнения на пару и вернуть первые мин и первые макс элементы. Долгое время казалось, что любая попытка сделать это потребует четырех сравнений на пару в худшем случае. Эта реализация достигает трех.

Невозможно (или даже желательно) изменить значениеmax_element, но все же полезно предоставить функцию под названиемminmax_element, которая возвращает паруmin_elementиmax_element. Хотя достаточно легко назватьmin_elementиmax_element, это выполняет2(n-1)сравнения и требуетдвухпроходов над входом. Напротив,minmax_elementбудет выполнять меньшее количество сравнений и выполнятьодиночныйпроход над входом. Экономия может быть значительной, когда тип итератора не является исходным указателем или даже просто моделью концепции InputIterator (хотя в этом случае интерфейс должен быть изменен, поскольку тип возврата не может быть скопирован, поэтому можно, например, вернуть значение).

Чтобы извлечь выгоду из всех вариантов алгоритма, я предлагаю ввести какfirst_min_elementиlast_min_element, так и их аналогиfirst_max_elementиlast_max_element. Затем я также предлагаю все варианты алгоритмов:first_min_last_max_elementиlast_min_first_max_element, которые выполняют только самое большее3n/2сравнения, и только один проход на входе. Фактически, можно доказать, что для вычисления minmax требуется по меньшей мере3(n/2)-2сравнения в любом случае проблемы (Cormen, Leiserson, Rivest, 2-е издание, раздел 9.1). Реализация, которую я даю, не выполняет ненужных сравнений (результат которых мог быть вычислен по транзитивности от предыдущих сравнений).

Похоже, чтопервый_min_last_max_elementможет быть немного медленнее, чемтолько первый_min_element, все еще намного меньше, чемпервый_min_elementипоследний_max_element, называемый отдельно

. Почему алгоритмы, а не аккумуляторы?

Алгоритмы minmax полезны для вычисления степени диапазона. В компьютерной графике нам нужен ограничивающий ящик из набора объектов. В этом случае необходимость в одном проходе еще более жесткая, поскольку все три направления должны быть сделаны сразу. Пища для размышлений: существует материя для хорошей общей библиотеки программирования со стекируемымиupdate_minиupdate_maxфункциональными объектами, которые хранят ссылку наmin_resultиmax_resultпеременных, в сочетании сfor_eachалгоритмом.

Я считаю, что многие стандартные последовательные алгоритмы могут быть переформулированы с помощью аккумуляторов (и многие другие, такие как статистика, ожидание / дисперсия / и т. Д.). Кажется, что есть место для другой библиотеки, но я не вижу, чтобы она конкурировала с minmax, а скорее распространяла несколько алгоритмов (включая minmax) на каркас аккумулятора. Тем не менее, я чувствовал, что это выходит за рамки этой библиотеки, чтобы предоставить такие аккумуляторы.

My students in CS903 (Polytechnic Univ., http://photon.poly.edu/~hbr/cs903/) who had minmax_element as an assignment helped clarify the issues, and also come up with the optimum number of comparisons for first_min_last_max_element. The identification of the issue surrounding max_element is solely my own.

One minmax_element implementation, which performs 3(n/2)+O(log n) comparisons on the average when the elements are random_shuffled, was suggested by my student Marc Glisse. The current one, which performs 3(n/2)+1 comparisons in the worst case, was suggested by John Iacono.

Finally, Matthew Wilson and Jeremy Siek contributed pre-review comments, while Gennadiy Rozental, John Maddock, Craig Henderson, Gary Powell participated in the review of the library, managed by Thomas Witt. In particular, Gennadiy suggested a factorization of the code; while I haven't followed it all the way, his suggestions do make the code more readable and still work with older compilers. Late after the review, as I finally scrounged to add the library for a release, Eric Niebler noted the bad behavior of std::pair for minmax and suggested to use Boost.tuple instead. All my thanks for the excellent advice and reviews from all.

See also

© Copyright Hervé Brönnimann, Polytechnic University, 2002--2004. Use, modification, and distribution is subject to the Boost Software License, Version 1.0. (See accompanying file License_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

Статья Boost Minmax library раздела может быть полезна для разработчиков на c++ и boost.

:: Главная :: ::