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

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

  v = original;

  // Move iterator to a quarter position

  it = v.begin();

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

    it++;

  // Less elements to copy from than to the destination

  partial_sort_copy(v.begin(), it, w.begin(), w.end());

  print(w.begin(), w.end(), "partial_sort_copy");

  // Not enough room in destination

  partial_sort_copy(v.begin(), v.end(), w.begin(),

    w.end());

  print(w.begin(), w.end(), "w partial_sort_copy");

  // v remains the same through all this process

  assert(v == original);

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

  cout << "The nth_element = " << *it << endl;

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

  string f = original[rand() % original.size()];

  cout << "binary search: "

    << binary_search(v.begin(), v.end(), f)

    << endl;

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

  it = lower_bound(v.begin(), v.end(), f);

  it2 = upper_bound(v.begin(), v.end(), f);

  print(it, it2, "found range");

  pair ip =

    equal_range(v.begin(), v.end(), f);

  print(ip.first, ip.second,

    "equal_range");

} ///:~

This example uses the NString class seen earlier, which stores an occurrence number with copies of a string. The call to stable_sort( ) shows how the original order for objects with equal strings is preserved. You can also see what happens during a partial sort (the remaining unsorted elements are in no particular order). There is no "partial stable sort.".

Notice in the call to nth_element( ) that, whatever the nth element turns out to be (which will vary from one run to another because of URandGen), the elements before that are less, and after that are greater, but the elements have no particular order other than that. Because of URandGen, there are no duplicates, but if you use a generator that allows duplicates, you’ll see that the elements before the nth element will be less than or equal to the nth element.

This example also illustrates all three binary search algorithms. As advertised, lower_bound( ) refers to the first element in the sequence equal to a given key, upper_bound( ) points one past the last, and equal_range( ) returns both results as a pair.

<p>Merging sorted ranges</p>

As before, the first form of each function assumes the intrinsic operator< performs the sort. The second form 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.

OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);

Copies elements from [first1, last1) and [first2, last2) into result, such that the resulting range is sorted in ascending order. This is a stable operation.

void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, StrictWeakOrdering binary_pred);

This assumes that [first, middle) and [middle, last) are each sorted ranges in the same sequence. The two ranges are merged so that the resulting range [first, last) contains the combined ranges in sorted order.

<p>Example</p>

It’s easier to see what goes on with merging if ints are used; the following example also emphasizes how the algorithms (and our own print template) work with arrays as well as containers.

//: C06:MergeTest.cpp

// Test merging in sorted ranges

#include

#include "PrintSequence.h"

#include "Generators.h"

using namespace std;

int main() {

  const int sz = 15;

  int a[sz*2] = {0};

  // Both ranges go in the same array:

  generate(a, a + sz, SkipGen(0, 2));

  a[3] = 4;

  a[4] = 4;

  generate(a + sz, a + sz*2, SkipGen(1, 3));

  print(a, a + sz, "range1", " ");

  print(a + sz, a + sz*2, "range2", " ");

  int b[sz*2] = {0}; // Initialize all to zero

  merge(a, a + sz, a + sz, a + sz*2, b);

  print(b, b + sz*2, "merge", " ");

  // Reset b

  for(int i = 0; i < sz*2; i++)

    b[i] = 0;

  inplace_merge(a, a + sz, a + sz*2);

  print(a, a + sz*2, "inplace_merge", " ");

  int* end = set_union(a, a + sz, a + sz, a + sz*2, b);

  print(b, end, "set_union", " ");

} ///:~

In main( ), instead of creating two separate arrays, both ranges are created end to end in the same array a. (This will come in handy for the inplace_merge.) The first call to merge( ) places the result in a different array, b. For comparison, set_union( ) is also called, which has the same signature and similar behavior, except that it removes duplicates from the second set. Finally, inplace_merge( ) combines both parts of a.

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

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

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

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

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

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

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

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

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