Читаем Thinking In C++. Volume 2: Practical Programming полностью

Just like partial_sort( ), nth_element( ) partially orders a range of elements. However, it’s much "less ordered" than partial_sort( ). The only thing that nth_element( ) guarantees is that whatever location you choose will become a dividing point. All the elements in the range [first, nth) will pair-wise satisfy the binary predicate (operator< by default, as usual), and all the elements in the range (nth, last] will not. However, neither subrange is in any particular order, unlike partial_sort( ) which has the first range in sorted order.

If all you need is this very weak ordering (if, for example, you’re determining medians, percentiles, and that sort of thing), this algorithm is faster than partial_sort( ).

<p>Locating elements in sorted ranges</p>

Once a range is sorted, you can use a group of operations to find elements within those ranges. In the following functions, there are always two forms. One assumes the intrinsic operator< performs the sort, and the second operator must be used if some other comparison function object performs the sort. You must use the same comparison for locating elements as you do to perform the sort; otherwise, the results are undefined. In addition, if you try to use these functions on unsorted ranges, the results will be undefined.

bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);

Tells you whether value appears in the sorted range [first, last).

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value); ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);

Returns an iterator indicating the first occurrence of value in the sorted range [first, last). If value is not present, an iterator to where it would fit in the sequence is returned.

ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value); ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);

Returns an iterator indicating one past the last occurrence of value in the sorted range [first, last). If value is not present, an iterator to where it would fit in the sequence is returned.

pair equal_range(ForwardIterator first, ForwardIterator last, const T& value); pair equal_range(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);

Essentially combines lower_bound( ) and upper_bound( ) to return a pair indicating the first and one-past-the-last occurrences of value in the sorted range [first, last). Both iterators indicate the location where value would fit if it is not found.

You may find it surprising that the binary search algorithms take a forward iterator instead of a random access iterator. (Most explanations of binary search use indexing.) Remember that a random access iterator "is-a" forward iterator, and can be used wherever the latter is specified. If the iterator passed to one of these algorithms in fact supports random access, then the efficient logarithmic-time procedure is used, otherwise a linear search is performed.[88]

<p>Example</p>

The following example turns each input word into an NString and added to a vector. The vector is then used to demonstrate the various sorting and searching algorithms.

//: C06:SortedSearchTest.cpp

// Test searching in sorted ranges

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include "NString.h"

#include "PrintSequence.h"

#include "../require.h"

using namespace std;

int main(int argc, char* argv[]) {

  typedef vector::iterator sit;

  char* fname = "test.txt";

  if(argc > 1) fname = argv[1];

  ifstream in(fname);

  assure(in, fname);

  srand(time(0));

  cout.setf(ios::boolalpha);

  vector original;

  copy(istream_iterator(in),

    istream_iterator(), back_inserter(original));

  require(original.size() >= 4, "Must have four elements");

  vector v(original.begin(), original.end()),

    w(original.size() / 2);

  sort(v.begin(), v.end());

  print(v.begin(), v.end(), "sort");

  v = original;

  stable_sort(v.begin(), v.end());

  print(v.begin(), v.end(), "stable_sort");

  v = original;

  sit it = v.begin(), it2;

  // Move iterator to middle

  for(size_t i = 0; i < v.size() / 2; i++)

    it++;

  partial_sort(v.begin(), it, v.end());

  cout << "middle = " << *it << endl;

Перейти на страницу:

Похожие книги

1С: Бухгалтерия 8 с нуля
1С: Бухгалтерия 8 с нуля

Книга содержит полное описание приемов и методов работы с программой 1С:Бухгалтерия 8. Рассматривается автоматизация всех основных участков бухгалтерии: учет наличных и безналичных денежных средств, основных средств и НМА, прихода и расхода товарно-материальных ценностей, зарплаты, производства. Описано, как вводить исходные данные, заполнять справочники и каталоги, работать с первичными документами, проводить их по учету, формировать разнообразные отчеты, выводить данные на печать, настраивать программу и использовать ее сервисные функции. Каждый урок содержит подробное описание рассматриваемой темы с детальным разбором и иллюстрированием всех этапов.Для широкого круга пользователей.

Алексей Анатольевич Гладкий

Программирование, программы, базы данных / Программное обеспечение / Бухучет и аудит / Финансы и бизнес / Книги по IT / Словари и Энциклопедии
1С: Управление торговлей 8.2
1С: Управление торговлей 8.2

Современные торговые предприятия предлагают своим клиентам широчайший ассортимент товаров, который исчисляется тысячами и десятками тысяч наименований. Причем многие позиции могут реализовываться на разных условиях: предоплата, отсрочка платежи, скидка, наценка, объем партии, и т.д. Клиенты зачастую делятся на категории – VIP-клиент, обычный клиент, постоянный клиент, мелкооптовый клиент, и т.д. Товарные позиции могут комплектоваться и разукомплектовываться, многие товары подлежат обязательной сертификации и гигиеническим исследованиям, некондиционные позиции необходимо списывать, на складах периодически должна проводиться инвентаризация, каждая компания должна иметь свою маркетинговую политику и т.д., вообщем – современное торговое предприятие представляет живой организм, находящийся в постоянном движении.Очевидно, что вся эта кипучая деятельность требует автоматизации. Для решения этой задачи существуют специальные программные средства, и в этой книге мы познакомим вам с самым популярным продуктом, предназначенным для автоматизации деятельности торгового предприятия – «1С Управление торговлей», которое реализовано на новейшей технологической платформе версии 1С 8.2.

Алексей Анатольевич Гладкий

Финансы / Программирование, программы, базы данных