10.6. Алгоритмы, специфические для контейнеров
В отличие от других контейнеров, контейнеры list и forward_list определяют несколько алгоритмов в качестве членов. В частности, тип list определяют собственные версии алгоритмов sort(), merge(), remove(), reverse() и unique(). Обобщенная версия алгоритма sort() требует итераторов произвольного доступа. В результате она не может использоваться с контейнерами list и forward_list, поскольку эти типы предоставляют двунаправленные и прямые итераторы соответственно.
Обобщенные версии других алгоритмов, определяемых типом list, вполне применимы со списками, но ценой производительности. Эти алгоритмы меняют элементы в исходной последовательности. Список может "поменять" свои элементы, поменяв ссылки на элементы, а не перемещая значения этих элементов. В результате специфические для списка версии этих алгоритмов могут обеспечить намного лучшую производительность, чем соответствующие обобщенные версии.
Эти специфические для списка функции приведены в табл. 10.6. В ней нет обобщенных алгоритмов, которые получают соответствующие итераторы и выполняются одинаково эффективно как для других контейнеров, так и для контейнеров list и forward_list.
Предпочтительней использовать алгоритмы-члены классов list и forward_list, а не их обобщенные версии.
Таблица 10.6. Алгоритмы-члены классов list и forward_list
Эти функции возвращают void. lst.merge(lst2) lst.merge(lst2, comp) Объединяет элементы списков lst2 и lst. Оба списка должны быть отсортированы. Элементы из списка lst2 удаляются, и после объединения список lst2 оказывается пустым. Возвращает тип void. В первой версии используется оператор <, а во второй — указанная функция сравнения lst.remove(val) lst.remove_if(pred) При помощи функции lst.erase() удаляет каждый элемент, значение которого равно переданному значению, или для которого указанный унарный предикат возвращает значение, отличное от нуля lst.reverse() Меняет порядок элементов списка lst на обратный lst.sort() lst.sort(comp) Сортирует элементы списка lst, используя оператор < или другой заданный оператор сравнения lst.unique() lst.unique(pred) При помощи функции lst.erase() удаляет расположенные рядом элементы с одинаковыми значениями. Вторая версия использует заданный бинарный предикат
Алгоритм-член splice()
Типы списков определяют также алгоритм splice(), описанный в табл. 10.7. Этот алгоритм специфичен для списочных структур данных. Следовательно, обобщенная версия этого алгоритма не нужна.
Таблица 10.7. Аргументы алгоритма-члена splice() классов list и forward_list
lst.splice(аргументы) или flst.splice_after(аргументы) (p, lst2) p — итератор на элемент списка lst или итератор перед элементом списка flst. Перемещает все элементы из списка lst2 в список lst непосредственно перед позицией p или непосредственно после в списке flst. Удаляет элементы из списка lst2. Список lst2 должен иметь тот же тип, что и lst (или flst), и не может быть тем же списком (p, lst2, p2) p2 — допустимый итератор в списке lst2. Перемещает элемент, обозначенный итератором p2, в список lst или элемент после обозначенного итератором p2 в списке flst. Список lst2 может быть тем же списком, что и lst или flst (p, lst2, b, е) b и е обозначают допустимый диапазон в списке lst2. Перемещает элементы в заданный диапазон из списка lst2. Списки lst2 и lst (или flst) могут быть тем же списком, но итератор p не должен указывать на элемент в заданном диапазонеСпецифические для списка функции, изменяющие контейнер
Большинство специфических для списков алгоритмов подобны (но не идентичны) их обобщенным аналогам. Но кардинально важное различие между специфическими и обобщенными версиями в том, что специфические версии изменяют базовый контейнер. Например, специфическая версия алгоритма remove() удаляет указанные элементы. Специфическая версия алгоритма unique() удаляет второй и последующий дубликаты элемента.
Аналогично алгоритмы merge() и splice() деструктивны к своим аргументам. Например, обобщенная версия функции merge() запишет объединенную последовательность по заданному итератору назначения; две исходных последовательности останутся неизменны. Специфическая для списка функция merge() разрушит заданный список — элементы будут удаляться из списка аргумента по мере их объединения в объект, для которого был вызван аргумент merge(). После объединения элементы из обоих списков продолжают существовать, но принадлежат уже одному списку.
Упражнения раздела 10.6
Упражнение 10.42. Переделайте программу, устранявшую повторяющиеся слова, написанную в разделе 10.2.3, так, чтобы использовался список, а не вектор.
Более 800 000 книг и аудиокниг! 📚
Получи 2 месяца Литрес Подписки в подарок и наслаждайся неограниченным чтением
ПОЛУЧИТЬ ПОДАРОК