содержание
Создайте список и присвойте значение
Используйте assign для добавления новых элементов в контейнер
Используйте изменение размера, чтобы изменить размер списка.
Используйте функцию splice для управления списками
удалить повторяющиеся элементы
Разница между списком и вектором
вводить
список представляет собой структуру линейного двусвязного списка, его данные состоят из нескольких узлов, каждый узел включает в себяинформационный блок(то есть фактически сохраненные данные),указатель впередиЗадний фланкер. Ему не нужно выделять определенный объем памяти, и его можно масштабировать произвольно, поскольку он хранится в несмежном пространстве памяти, а упорядоченные элементы связаны указателями. Из-за своей структуры производительность случайного поиска по списку очень низкая, потому что он не находит напрямую адрес элемента, как вектор, а должен искать последовательно один за другим с самого начала, так что чем позже целевой элемент , тем короче время его поиска. Время поиска пропорционально позиции целевого элемента. Хотя случайный поиск недостаточно быстр, он может быстро выполнять операции вставки и удаления в любом узле. Поскольку каждый узел списка сохраняет свою позицию в связанном списке, вставка или удаление элемента влияет только на три элемента, в отличие от вектора, который влияет на адреса хранения всех элементов после точки операции.Одним из пунктов является то, что вектор несравним.
list специальность:
(1) Не используйте непрерывное пространство памяти, чтобы можно было выполнять динамические операции по желанию;
(2) Его можно быстро вставить или удалить в любом месте внутри, и, конечно же, можно выполнять нажатие и выталкивание с обоих концов.
(3) Внутренний произвольный доступ невозможен, то есть оператор [ ] и vector.at() не поддерживаются;
(4) Занимает больше памяти, чем verctor.
Общие функции
| Конструктор списка и деструктор | |
|---|---|
| list<Elem> c | создает пустой список без элементов в нем |
| list<Elem> c1(c2) | Сделать еще одну копию списка того же типа (копируются все элементы) |
| list<Elem> c(n) | Используйте конструктор элемента по умолчанию для создания списка размера n |
| list<Elem> c(n,elem) | Создайте список размера n, каждое значение элемента равно elem |
| list<Elem> c(beg, end) | Создайте список с интервалом [beg, end) в качестве начального значения элемента |
| c.~list<Elem>() | Уничтожить все элементы и освободить память |
| Неизменяемые операции над списками | |
| size() | Возвращает размер контейнера |
| empty() | Определить, пуст ли контейнер, эквивалентно size()==0, но может быть быстрее |
| max_size() | Возвращает самый большой элемент, который может хранить контейнер |
| reserve() | Если мощности недостаточно, увеличьте ее. |
| c1 == c2 | Определить, равен ли c1 c2 |
| c1 != c2 | Определить, не равен ли c1 c2 |
| c1 < c2 | Определить, меньше ли c1, чем c2 |
| c1 > c2 | Определить, больше ли c1, чем c2 |
| c1 <= c2 | Определить, меньше ли c1, чем c2, или равно ему. |
| c1 >= c2 | Определить, является ли c1 больше или равным c2 |
| Операция присваивания списку | |
| c1 = c2 | Присвоить все элементы c2 элементу c1 |
| assign(n, elem) | Скопируйте n elem, скопируйте в c |
| assign(beg, end) | Присвойте элементам в диапазоне [beg;end) значение c |
| c1.swap(c2) | Поменяйте местами элементы c1 и c2 |
| swap(c1,c2) | Как и выше, это глобальная функция |
| доступ к элементам | |
| front | Возвращает первый элемент, не проверяя, существует ли этот элемент или нет. |
| back | Возвращает последний элемент, не проверяя, существует ли этот элемент или нет. |
| Функции, связанные с итератором | |
| begin() | Возвращает двунаправленный итератор, указывающий на первый элемент |
| end() | Возвращает двунаправленный итератор, указывающий на следующую позицию последнего элемента |
| rbegin() | Возвращает обратный итератор, указывающий на первый элемент обратной итерации. |
| end() | Возвращает обратный итератор, указывающий на следующую позицию последнего элемента обратной итерации. |
| список функций вставки и удаления операций | |
| insert(pos, elem) | Вставьте копию элемента в позицию, на которую указывает позиция итератора, и верните позицию нового элемента. |
| insert(pos,n,elem) | Вставьте n копий элемента в позицию pos, без возвращаемого значения |
| insert(pos,beg,end) | Вставьте копию всех элементов интервала [beg,end) в позицию pos без возвращаемого значения. |
| push_back(elem) | Добавьте копию elem в хвост |
| pop_back() | удалить последний элемент, без возвращаемого значения |
| push_front() | Добавьте копию elem в голову |
| pop_front() | удалить первый элемент, но не возвращать |
| remove(val) | удалить все элементы, значение которых равно val |
| remove_if() | Удалить из связанного списка все элементы, удовлетворяющие условию |
| erase(pos) | Удалить элемент в позиции pos и вернуть позицию следующего элемента |
| erase(beg, end) | Удалить все элементы в интервале [beg, end) и вернуть позицию следующего элемента |
| resize(num) | Измените количество элементов на num (если size() станет больше, все дополнительные новые элементы должны быть завершены с помощью конструктора по умолчанию) |
| resize(num,elem) | Измените количество элементов на num (если size() становится больше, все новые элементы являются копиями elem) |
| clear() | Удалить все элементы, очистить контейнер |
| Примечания: вставка и удаление элементов сделает недействительными итераторы каждого элемента после «точки действия».Если произойдет перераспределение памяти, все итераторы в контейнере будут недействительными. | |
| Специальные операции изменчивости для списков | |
| unique() | Если есть несколько соседних элементов с одинаковым значением, повторяющиеся элементы удаляются, оставляя |
| unique(op) | Если есть несколько смежных элементов, все делают результат op() истинным, затем удаляют повторяющийся элемент, оставляя только один. |
| c1.splice(pos, c2) | Переместите все элементы в c2 в c1, прежде чем позиция итератора |
| c1.splice(pos, c2, c2pos) | Переместите элемент, на который указывает c2pos в c2, в позицию, на которую указывает pos в c1 (c1, c2 могут быть одинаковыми) |
| c1.splice(поз., c2, c2beg, c2end) | Перед интервалом [C2BEG, C2END) передается на все элементы в POS C1 в C2 (C1, C2 может быть одинаковым) |
| sort() | Сортировать все элементы с оператором |
| sort(op) | Отсортируйте все элементы, используя op() в качестве ориентира |
| c1.merge(c2) | Предполагая, что оба контейнера c1 и c2 содержат отсортированные (одинакового порядка) элементы, перенесите все элементы c2 в c1 и убедитесь, что объединенный список по-прежнему отсортирован. |
| c1.merge(c2, op) | Предполагая, что контейнеры c1 и c2 содержат упорядоченные (с одинаковой сортировкой) элементы в соответствии с принципом op(), перенесите все элементы из c2 в c1 и убедитесь, что объединенный список по-прежнему упорядочен в соответствии с принципом op(). |
| reverse() | Перевернуть все элементы |
Пример использования функции
Создайте список и присвойте значение
#include <iostream>
#include <list>
using namespace std;
int main() {
//Первый, через конструктор
int myints[] = { 44,77,22,11,12 };
list<int> mylist1(myints, myints + 5);
list
//Второй, используйте push_back или push_front
for (int i = 1; i <= 5; ++i) mylist1.push_back(i);
mylist2.push_front(20);
mylist2.push_front(30);
//Третий, используйте assign
list<int> first;
list<int> second;
First.assign(7, 10);// Добавляем 7 значений от 10 до 10
second.assign(first.begin(), first.end()); // копируем первое во второе
int myints1[] = { 32, 8, 4 };
first.assign(myints1, myints1 + 3);// добавить содержимое массива myints в первый
return 0;
}
Пройди и найди
#include <iostream>
#include <list>
using namespace std;
int main() {
//Первый, через конструктор
int myints[] = { 44,77,22,11,12};
list<int> myList(myints, myints + 5);
cout << "mylist contains:";
//переход
for (list<int>::iterator it = myList.begin(); it != myList.end(); ++it)
{
cout << " " << *it;
}
cout << "\n";
//найти
for (list<int>::iterator it = myList.begin(); it != myList.end(); ++it)
{
if (*it == 22)
{
cout
}
}
cout << "\n";
// добавить
for (int i = 1; i <= 5; ++i)
myList.push_back(i);
// обход в обратном порядке
for (list<int>::reverse_iterator rit = myList.rbegin(); rit != myList.rend(); ++rit)
cout << ' ' << *rit;
return 0;
}
удалить элемент
// создаем экземпляр и назначаем
#include <iostream>
#include <list>
using namespace std;
bool single_digit(const int& value) { return (value < 20); }
struct is_odd {
//оператор перегрузки()
bool operator() (const int& value) { return (value % 2) == 1; }
};
int main() {
//Первый, через конструктор
int myints[] = { 44,77,22,11,12 };
list<int> myList(myints, myints + 5);
cout << "mylist contains:";
//переход
for (list<int>::iterator it = myList.begin(); it != myList.end(); ++it)
{
cout << " " << *it;
}
cout << "\n";
//удаляем и удаляем_если удаляем элементы
myList.remove(22);
myList.remove_if(single_digit);
myList.remove_if(is_odd());
//переход
for (list<int>::iterator it = myList.begin(); it != myList.end(); it++)
{
cout << " " << *it;
}
cout << "\n";
// добавить
myList.push_back(22);
for (list<int>::iterator it = myList.begin(); it != myList.end(); it++) {
cout << " " << *it;
}
cout << "\n";
// Проходим и удаляем, это неправильный способ написания.
/*for (auto it = myList.begin(); it != myList.end(); it++)
{
if (*it == 11) {
myList.erase(it);
}
}*/
//Первый способ записи
for (auto it = myList.begin(); it != myList.end();)
{
if (*it == 22) {
myList.erase(it++);
}
else
{
cout << " " << *it;
it++;
}
}
//Второй способ записи
for (auto it = myList.begin(); it != myList.end();)
{
if (*it == 22) {
it=myList.erase(it);
}
else
{
cout << " " << *it;
it++;
}
}
return 0;
}
очистить список
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> mylist;
list<int>::iterator it;
mylist.push_back(10);
mylist.push_back(20);
mylist.push_back(30);
cout << "mylist contains:";
for (it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
mylist.clear();
mylist.push_back(2121);
mylist.push_back(3232);
cout << "mylist contains:";
for (it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
вставить элемент в список
#include <iostream>
#include <list>
#include <vector>
using namespace std;
int main() {
list<int> mylist;
list<int>::iterator it;
// инициализируем
for (int i = 1; i <= 5; ++i) mylist.push_back(i); // 1 2 3 4 5
it = mylist.begin();
++it; // итератор it теперь указывает на число 2 ^
// Вставляем элемент 10 в позицию, на которую указывает i0t
mylist.insert(it, 10); // 1 10 2 3 4 5
// "it" по-прежнему указывает на число 2 ^
// Вставляем два элемента 20 в позицию, на которую он указывает
mylist.insert(it, 2, 20); // 1 10 20 20 2 3 4 5
--it; // теперь он указывает на число 20 ^
vector
// Вставляем значение векторного контейнера в список
mylist.insert(it, myvector.begin(), myvector.end());
// 1 10 20 30 30 20 2 3 4 5
// он по-прежнему указывает на число 20 // ^
cout << "mylist contains:";
for (it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
Используйте assign для добавления новых элементов в контейнер
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> first;
list<int> second;
first.assign(7, 10);//Добавить 7 элементов со значением 10 к первому
second.assign(first.begin(), first.end()); // копируем первое во второе
int myints[] = { 22, 33, 44 };
first.assign(myints, myints + 3);// добавить содержимое массива myints в первый
cout << "Size of first: " << int(first.size()) << '\n';
cout << "Size of second: " << int(second.size()) << '\n';
return 0;
}
обмен двумя списками
// swap lists
#include <iostream>
#include <list>
using namespace std;
int main() {
list
Список
first.swap(second);
cout << "first contains:";
for (list<int>::iterator it = first.begin(); it != first.end(); it++)
cout << ' ' << *it;
cout << '\n';
cout << "second contains:";
for (list<int>::iterator it = second.begin(); it != second.end(); it++)
cout << ' ' << *it;
cout << '\n';
return 0;
}
Используйте изменение размера, чтобы изменить размер списка.
// resizing list
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> mylist;
// инициализируем
for (int i = 1; i
mylist.resize(5);//длина списка становится равной 5, а элементы: 0 1 2 3 4
mylist.resize(8, 100);//Длина списка становится равной 8, часть, превышающая 5, становится равной 100, а элементы: 0 1 2 3 4 100 100 100
mylist.resize(12);//Длина списка становится 12, части, превышающей 5, присваивается значение по умолчанию 0, а элементы: 0 1 2 3 4 100 100 100 0 0 0 0
cout << "mylist contains:";
for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
Используйте функцию splice для управления списками
// splicing lists
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> mylist1, mylist2;
list<int>::iterator it;
// инициализируем
for (int i = 1; i <= 10; ++i)
mylist1.push_back(i); // mylist1: 1 2 3 4 5 6 7 8 9
for (int i = 1; i <= 3; ++i)
mylist2.push_back(i * 10); // mylist2: 10 20 30
it = mylist1.begin();
++it; // указывает на число 2
mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
// mylist2 (empty)
// "it" по-прежнему указывает на номер 2
mylist2.splice(mylist2.begin(), mylist1, it);
// mylist1: 1 10 20 30 3 4
// mylist2: 2
// "это" в настоящее время недействительно
it = mylist1.begin();
advance(it, 3); // "it" указывает на число 30
mylist1.splice(mylist1.begin(), mylist1, it, mylist1.end());
// mylist1: 30 3 4 1 10 20
cout << "mylist1 contains:";
for (it = mylist1.begin(); it != mylist1.end(); ++it)
cout << ' ' << *it;
cout << '\n';
cout << "mylist2 contains:";
for (it = mylist2.begin(); it != mylist2.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
удалить повторяющиеся элементы
// list::unique
#include <iostream>
#include <cmath>
#include <list>
using namespace std;
// a binary predicate implemented as a function:
bool same_integral_part(double first, double second) { return (int(first) == int(second)); }
// a binary predicate implemented as a class:
struct is_near {
bool operator() (double first, double second) { return (fabs(first - second) < 5.0); }
};
int main() {
double mydoubles[] = { 12.15, 2.72, 73.0, 12.77, 3.14,
12.77, 73.35, 72.25, 15.3, 72.25 };
list<double> mylist(mydoubles, mydoubles + 10);
cout << "mylist contains:";
for (list<double>::iterator it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
mylist.unique();
cout << "mylist contains:";
for (list<double>::iterator it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
mylist.sort(); // 2.72, 3.14, 12.15, 12.77, 12.77,
// 15.3, 72.25, 72.25, 73.0, 73.35
mylist.unique(); // 2.72, 3.14, 12.15, 12.77
// 15.3, 72.25, 73.0, 73.35
cout << "mylist contains:";
for (list<double>::iterator it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
mylist.unique(same_integral_part); // 2.72, 3.14, 12.15 // 15.3, 72.25, 73.0
cout << "mylist contains:";
for (list<double>::iterator it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
mylist.unique(is_near()); // 2.72, 12.15, 72.25
cout << "mylist contains:";
for (list<double>::iterator it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
объединить список
#include <iostream>
#include <list>
using namespace std;
bool mycomparison(double first, double second) { return ((first) < (second)); }
int main() {
list<double> first, second;
first.push_back(3.1);
first.push_back(2.2);
first.push_back(2.9);
second.push_back(3.7);
second.push_back(7.1);
second.push_back(1.4);
first.sort();
second.sort();
first.merge(second);
cout << "first contains:";
for (list<double>::iterator it = first.begin(); it != first.end(); ++it)
cout << ' ' << *it;
cout << '\n';
// (секунда теперь пуста)
second.push_back(1.1);
second.push_back(2.1);
second.push_back(2.5);
first.merge(second, mycomparison);
cout << "first contains:";
for (list<double>::iterator it = first.begin(); it != first.end(); it++)
cout << ' ' << *it;
cout << '\n';
return 0;
}
Сортировать
// list::sort
#include <iostream>
#include <list>
#include <string>
#include <cctype>
using namespace std;
// comparison, not case sensitive.
bool compare_nocase(const string& first, const string& second) {
unsigned int i = 0;
while ((i < first.length()) && (i < second.length())) {
// Преобразование заглавных букв в строчные
if (tolower(first[i]) < tolower(second[i])) return true;
else if (tolower(first[i]) > tolower(second[i])) return false;
++i;
}
return (first.length() < second.length());
}
int main() {
list<string> mylist;
list<string>::iterator it;
mylist.push_back("one");
mylist.push_back("two");
mylist.push_back("Three");
mylist.push_back("Four");
mylist.push_back("Five");
mylist.push_back("Six");
mylist.sort();
cout << "mylist contains:";
for (it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
mylist.sort(compare_nocase);
cout << "mylist contains:";
for (it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
Разница между списком и вектором
-
vector структура данных
Подобно массиву, вектор имеет непрерывное пространство памяти с одним и тем же начальным адресом.
Следовательно, произвольный доступ может выполняться эффективно, а временная сложность составляет O(1);
Однако, поскольку пространство памяти является непрерывным, при вставке и удалении операций это приведет к копированию блока памяти, а временная сложность равна o (n).
Кроме того, когда места в памяти в массиве недостаточно, будет запрошено новое место в памяти и будет выполнено копирование памяти.
Вектор имеет непрерывное пространство памяти и может очень хорошо поддерживать произвольный доступ. Объем памяти списка может быть прерывистым, произвольный доступ не поддерживается, И vector Короче говоря, если вам нужен эффективный произвольный доступ и вас не волнует эффективность вставки и удаления, используйте вектор; Ссылаться на: 1,woo woo woo.cn blog on.com/I am 0816/afraid/65…
Итак, vector
Список реализуется двусвязным списком, поэтому пространство памяти является прерывистым.
Доступ к данным возможен только через указатели, поэтому произвольный доступ к списку очень неэффективен, а временная сложность равна o(n);
Однако благодаря характеристикам связанных списков вставка и удаление могут выполняться эффективно.
Поэтому list
Если вам нужно много вставок и удалений и вам не нужен произвольный доступ, вы должны использовать список.