Операции над множеством для сортированных структур (Set operations on sorted structures)
Операции над множеством для сортированных структур (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- сравнений. Результат 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 не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.
Более 800 000 книг и аудиокниг! 📚
Получи 2 месяца Литрес Подписки в подарок и наслаждайся неограниченным чтением
ПОЛУЧИТЬ ПОДАРОКЧитайте также
Заполнение структур
Заполнение структур Структуры заполняются таким образом, чтобы каждый ее элемент имел естественное выравнивание. Например, рассмотрим следующую структуру данных на 32- разрядной машине.struct animal_struct { char dog; /* 1 байт */ unsigned long cat; /* 4 байт */ unsigned short pig; /* 2 байт
Инициализация структур
Инициализация структур Структуры необходимо инициализировать, используя метки полей. Это позволяет предотвратить некорректную инициализацию при изменении структур. Это также позволяет выполнять инициализацию не всех полей. К сожалению, в стандарте C99 принят довольно
Выбор вершин со множеством рёбер
Выбор вершин со множеством рёбер В идеале меш должен содержать грани, которые состоят из только четырех вершин (эти грани обычно именуются quads — четырёхугольники), и у них должны быть относительно одинаковые размеры. Такая конфигурация оптимальна при деформации меша,
Интерфейсы с множеством базовых интерфейсов
Интерфейсы с множеством базовых интерфейсов При построении иерархии интерфейсов вполне допустимо создавать интерфейсы, которые оказываются производными от нескольких базовых интерфейсов. Однако напомним, что нельзя строить классы, которые будут производными от
Объекты DataSet с множеством таблиц и объекты DataRelation
Объекты DataSet с множеством таблиц и объекты DataRelation До этого момента во всех примерах данной главы объекты DataSet содержали по одному объекту DataTable. Однако вся мощь несвязного уровня ADO.NET проявляется тогда, когда DataSet содержит множество объектов DataTable. В этом случае вы можете
Операции с итераторами (Iterator operations)
Операции с итераторами (Iterator operations) Так как только итераторы произвольного доступа обеспечивают + и - операторы, библиотека предоставляет две шаблонные функции advance и distance. Эти функции используют + и - для итераторов произвольного доступа (и имеют, поэтому, сложность
Арифметические операции (Arithmetic operations)
Арифметические операции (Arithmetic operations) Библиотека обеспечивает базовые классы функциональных объектов для всех арифметических операторов языка.template ‹class T›struct plus: binary_function‹T, T, T› { Т operator()(const T& x, const T& y) const {return x + y;}};template ‹class T›struct minus: binary_function‹T, T, T› { Т operator()(const T&
Логические операции (Logical operations)
Логические операции (Logical operations) template ‹class T›struct logical_and: binary_function‹T, T, bool› { bool operator()(const T& x, const T& y) const {return x&& y;}};template ‹class T›struct logical_or: binary_function‹T, T, bool› { bool operator()(const T& x, const T& y) const {return x || y;}};template ‹class T›struct logical_not: unary_function‹T, bool› { bool operator()(const T& x) const
Не меняющие последовательность операции (Non-mutating sequence operations)
Не меняющие последовательность операции (Non-mutating sequence operations) Операции с каждым элементом (For each) template <class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f);for_each применяет f к результату разыменования каждого итератора в диапазоне [first, last) и возвращает f. Принято,
Меняющие последовательность операции (Mutating sequence operations)
Меняющие последовательность операции (Mutating sequence operations) Копировать (Copy) template ‹class InputIterator, class OutputIterator›OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);copy копирует элементы. Для каждого неотрицательного целого числа n ‹ (last - first) выполняется присваивание *(result + n) = *(first + n).
Операции сортировки и отношения (Sorting and related operations)
Операции сортировки и отношения (Sorting and related operations) Все операции в этом разделе имеют две версии: одна берёт в качестве параметра функциональный объект типа Compare, а другая использует operator‹.Compare - функциональный объект, который возвращает значение, обратимое в bool. Compare comp
Операции над пирамидами (Heap operations)
Операции над пирамидами (Heap operations) Пирамида - специфическая организация элементов в диапазоне между двумя итераторами произвольного доступа [a, b). Два её ключевые свойства: (1) *a - самый большой элемент в диапазоне, (2) *a может быть удалён с помощью pop_heap или новый элемент
Обобщённые численные операции (Generalized numeric operations)
Обобщённые численные операции (Generalized numeric operations) Накопление (Accumulate) template ‹class InputIterator, class T›T accumulate(InputIterator first, InputIterator last, T init);template ‹class InputIterator, class T, class BinaryOperation›T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);accumulate подобен оператору APL reduction и функции Common Lisp reduce, но он
Метод Sorted
Метод Sorted Описание методовМетоды приведены для последовательности sequence of T. function Sorted(): sequence of T; Возвращает отсортированную по возрастанию
Замечание о пустоте структур
Замечание о пустоте структур Предусловие в процедуре создания (конструкторе) make класса STACK1 требует комментария. Оно устанавливает n>=0 и, следовательно, допускает пустые стеки. Если n=0, то make вызовет процедуру создания для массивов, также имеющую имя make, с аргументами 1 и 0