Список (List)
Список (List)
list - вид последовательности, которая поддерживает двунаправленные итераторы и позволяет операции вставки и стирания с постоянным временем в любом месте последовательности, с управлением памятью, обрабатываемым автоматически. В отличие от векторов и двусторонних очередей, быстрый произвольный доступ к элементам списка не поддерживается, но многим алгоритмам, во всяком случае, только и нужен последовательный доступ.
template ‹class T, template ‹class U› class Allocator = allocator›
class list {
public:
// определения типов:
typedef iterator;
typedef const_iterator;
typedef Allocator‹T›::pointer pointer;
typedef Allocator‹T›::reference reference;
typedef Allocator‹T›::const_reference const_reference;
typedef size_type;
typedef difference_type;
typedef Т value_type;
typedef reverse_iterator;
typedef const_reverse_iterator;
// размещение/удаление:
list()
list(size_type n, const T& value = T());
template ‹class InputIterator›
list(InputIterator first, InputIterator last);
list(const list‹T, Allocator›& x);
~list();
list‹T, Allocator›& operator=(const list‹T,Allocator›& x);
void swap(list‹T, Allocator& x);
// средства доступа:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rend();
bool empty() const;
size_type size() const;
size_type max_size() const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// вставка/стирание:
void push_front(const T& x);
void push_back(const T& x);
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x);
template ‹class InputIterator›
void insert(iterator position, InputIterator first, InputIterator last);
void pop_front();
void pop_back();
void erase(iterator position);
void erase(iterator first, iterator last);
// специальные модифицирующие операции cо списком:
void splice(iterator position, list‹T, Allocator›& x);
void splice(iterator position, list‹T, Allocator›& x, iterator i);
void splice(iterator position, list‹T, Allocator›& x, iterator first, iterator last);
void remove(const T& value);
template ‹class Predicate›
void remove_if(Predicate pred);
void unique();
template ‹class BinaryPredicate›
void unique(BinaryPredicate binary_pred);
void merge(list‹T, Allocator›& x);
template ‹class Compare›
void merge(list‹T,Allocator›& x, Compare comp);
void reverse();
void sort();
template ‹class Compare› void sort(Compare comp);
};
template ‹class T, class Allocator›
bool operator==(const list‹T, Allocator›& x, const list‹T, Allocator›& y);
template ‹class T, class Allocator›
bool operator‹(const list‹T, Allocator›& x, const list‹T, Allocator›& y);
iterator - двунаправленный итератор, ссылающийся на T. Точный тип зависит от исполнения и определяется в Allocator.
const_iterator - постоянный двунаправленный итератор, ссылающийся на const T. Точный тип зависит от исполнения и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.
size_type - беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.
difference_type - знаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.
insert не влияет на действительность итераторов и ссылок. Вставка единственного элемента в список занимает постоянное время, и ровно один раз вызывается конструктор копирования T. Вставка множественных элементов в список зависит линейно от числа вставленных элементов, а число вызовов конструктора копирования T точно равно числу вставленных элементов.
erase делает недействительными только итераторы и ссылки для стёртых элементов. Стирание единственного элемента - операция постоянного времени с единственным вызовом деструктора T. Стирание диапазона в списке занимает линейное время от размера диапазона, а число вызовов деструктора типа T точно равно размеру диапазона.
Так как списки позволяют быструю вставку и стирание в середине списка, то некоторые операции определяются специально для них:
list обеспечивает три операции стыковки, которые разрушительно перемещают элементы из одного списка в другой:
void splice(iterator position, list‹T, Allocator›& x) вставляет содержимое x перед position, и x становится пустым. Требуется постоянное время. Результат не определён, если &x==this.
void splice(iterator position, list‹T, Allocator›& x, iterator i) вставляет элемент, указываемый i, из списка x перед position и удаляет элемент из x. Требуется постоянное время. i - допустимый разыменовываемый итератор списка x. Результат не изменяется, если position==i или position==++i.
void splice(iterator position, list‹T, Allocator›& x, iterator first, iterator last) вставляет элементы из диапазона [first, last) перед position и удаляет элементы из x. Требуется постоянное время, если &x==this; иначе требуется линейное время. [first, last) - допустимый диапазон в x. Результат не определён, если position - итератор в диапазоне [first, last).
remove стирает все элементы в списке, указанном итератором списка i, для которого выполняются следующие условия: *i==value, pred(*i)==true. remove устойчиво, то есть относительный порядок элементов, которые не удалены, тот же самый, как их относительный порядок в первоначальном списке. Соответствующий предикат применяется точно size() раз.
unique стирает все, кроме первого элемента, из каждой последовательной группы равных элементов в списке. Соответствующий бинарный предикат применяется точно size() - 1 раз.
merge сливает список аргумента со списком (предполагается, что оба сортированы). Слияние устойчиво, то есть для равных элементов в двух списках элементы списка всегда предшествуют элементам из списка аргумента. x пуст после слияния. Выполняется, самое большее, size() + x.size() - 1 сравнений.
reverse переставляет элементы в списке в обратном порядке. Операция линейного времени.
sort сортирует список согласно operator‹ или сравнивающему функциональному объекту. Она устойчива, то есть относительный порядок равных элементов сохраняется. Выполняется приблизительно NlogN сравнений, где N равно size().
Более 800 000 книг и аудиокниг! 📚
Получи 2 месяца Литрес Подписки в подарок и наслаждайся неограниченным чтением
ПОЛУЧИТЬ ПОДАРОКЧитайте также
Создание списка: <fo:list-block>
Создание списка: <fo:list-block> Для начала воспользуйтесь элементом <fo:list-block>, чтобы создать список XSL-FO; этот объект содержит элементы <fo:list-item>, содержащие данные списка.С элементом <fo:list-block> можно применять следующие свойства:• общие свойства доступа: source-document,
Создание элементов списка: <fo:list-item>
Создание элементов списка: <fo:list-item> Затем при помощи элемента <fo:list-item> нужно поместить в список метку и тело элемента списка. В каждом элементе списка должен присутствовать один из этих объектов.С элементом <fo:list-item> можно применять следующие свойства:• общие
Создание меток элемента списка: <fo:list-item-label>
Создание меток элемента списка: <fo:list-item-label> Метка для элемента списка создается элементом <fo:list-item-label>, при помощи которого можно перенумеровать или пометить дело элемента списка.К элементу <fo:list-item-label> можно применять следующие свойства:• общие свойства
Создание тел элементов списка: <fo:list-item-body>
Создание тел элементов списка: <fo:list-item-body> Для включения тела элемента списка служит элемент <fo:list-item-body>. Заметьте, что для форматирования тела элемента списка требуемым вам образом вы можете включить в элемент <fo:list-item-body> объект <fo:block>.С элементом
12.6.2. Операция list::remove()
12.6.2. Операция list::remove() void list::remove( const elemType &value );Операция remove() удаляет все элементы с заданным значением:ilist1.remove( 1
12.6.3. Операция list::remove_if()
12.6.3. Операция list::remove_if() template class Predicate void list::remove_if( Predicate pred );Операция remove_if() удаляет все элементы, для которых выполняется указанное условие, т.е. предикат pred возвращает true. Например:class Even {public:bool operator()( int elem ) { return ! (elem % 2 ); }};ilist1.remove_if( Even() );удаляет все четные числа из списка,
12.6.4. Операция list::reverse()
12.6.4. Операция list::reverse() void list::reverse();Операция reverse() изменяет порядок следования элементов списка на
12.6.5. Операция list::sort()
12.6.5. Операция list::sort() void list::sort();template class Comparevoid list::sort( Compare comp );По умолчанию sort() упорядочивает элементы списка по возрастанию с помощью оператора "меньше", определенного в классе элементов контейнера. Вместо этого можно явно передать в качестве аргумента оператор
12.6.6. Операция list::splice()
12.6.6. Операция list::splice() void list::splice( iterator pos, list rhs );void list::splice( iterator pos, list rhs, iterator ix );void list::splice( iterator pos, list rhs,iterator first, iterator last );Операция splice() имеет три формы: перемещение одного элемента, всех элементов или диапазона из одного списка в другой. В каждом случае передается итератор,
12.6.7. Операция list::unique()
12.6.7. Операция list::unique() void list::unique();template class BinaryPredicatevoid list::unique( BinaryPredicate pred );Операция unique() удаляет соседние дубликаты. По умолчанию при сравнении используется оператор равенства, определенный для типа элементов контейнера. Например, если даны значения {0,2,4,6,4,2,0}, то после
9.3.1. Файл /etc/apt/sources.list и репозитории пакетов
9.3.1. Файл /etc/apt/sources.list и репозитории пакетов Откройте файл /etc/apt/sources.list (рис. 9.2): gksudo gedit /etc/apt/sources.list Найдите и раскомментируйте следующую строку: deb http://ru.archive.ubuntu.com/ubuntu/ lucid-backports main restricted universe multiverse Эта строка подключает репозиторий backports, содержащий много полезных
9.3.2. Графическая оболочка для редактирования файла /etc/apt/sources.list
9.3.2. Графическая оболочка для редактирования файла /etc/apt/sources.list Лично мне удобнее редактировать файл /etc/apt/sources.list вручную, но вам, возможно, будет удобнее пользоваться для этого графической оболочкой, так что было бы несправедливо, если бы я не рассказал вам о ней. Для