Обмен технологиями

[C Элементарный] Предварительное понимание класса списка

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Стандартная библиотекасписокдобрый

Нижний уровень списка представляет собой двустороннюю циклическую структуру связанного списка со сторожевыми битами.
По сравнению со структурой односвязного спискаforward_list, итератор списка является двунаправленным итератором.
По сравнению с контейнерами с последовательной структурой, такими как вектор, список более эффективен при вставке и удалении в любой позиции, но он не поддерживает произвольный доступ в любой позиции.
Список — это класс шаблона. При его использовании нам необходимо указать тип элемента.

При использовании класса списка вам необходимо включить файл заголовка<list>

2. Общие интерфейсы класса списка

1. Часто используемые конструкторы

1. Конструктор по умолчанию, создает пустой связанный список.

list();

Например:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. }

2. Создайте объект списка и инициализируйте его n значениями.

list(size_type n, const value_type& val =  value_type());

Например:

  1. void test()
  2. {
  3. 	list<int> lt(3, 1);
  4. 	for (auto i : lt)
  5. 	{
  6. 		cout << i << " ";
  7. 	}
  8. }

результат операции:

3.Копировать конструктор класса списка.

list(const list& x);

Например:

  1. void test()
  2. {
  3. 	list<int> lt(3, 1);
  4. 	list<int> lt1(lt);
  5. 	for (auto i : lt1)
  6. 	{
  7. 		cout << i << " ";
  8. 	}
  9. }

результат операции:

4. Используйте конструктор инициализации итератора.

  1. Template<class InputIterator>
  2.  
  3. list(InputIterator first, InputIterator last);

Например:

  1. void test()
  2. {
  3. 	list<int> lt(3, 1);
  4. 	list<int> lt1(lt.begin(), lt.end());
  5. 	for (auto i : lt1)
  6. 	{
  7. 		cout << i << " ";
  8. 	}
  9. }

результат операции:

2. Часто используемые интерфейсы емкости

Это все то же самое, позвольте мне поговорить об этом вместе здесь.

1.размер,пустой,макс_размер,изменение_размера

размер:возвращатьсясвязанный списокКоличество элементов в контейнере.

size_type size() const;

пустой:возвращатьсясписокПустой ли контейнер (т.е. егоразмерравен 0).
(Примечание. Эта функция никоим образом не изменяет контейнер. Чтобы очиститьсвязанный списокСодержимое контейнера см.список::очистить。）

bool empty() const;

максимальный_размер(не часто используется): возвратсвязанный списокМаксимальное количество элементов, которые может содержать контейнер.
(Из-за известных ограничений реализации системы или библиотеки это максимальный потенциал, которого может достичь контейнер.размер , но нет никакой гарантии, что контейнер достигнет этого размера: он все равно не сможет выделить хранилище в любой момент до достижения этого размера. )

size_type max_size() const;

изменить размер:Измените размер контейнера, чтобы он содержалнэлементы.
еслинменьше текущего контейнераразмер, содержимое будет уменьшено до предыдущегонэлементы, удаляя те, которые превышают (и уничтожая их).
еслинБольше, чем текущий контейнерразмер, затем содержимое расширяется путем вставки необходимого количества элементов в конце для достижениян размер.Если указановал, то новый элемент будет инициализирован каквалкопии, в противном случае они инициализируются значением.
(Обратите внимание, что эта функция изменяет фактическое содержимое контейнера, вставляя или удаляя элементы из контейнера.)

void resize (size_type n, value_type val = value_type());

Например:

  1. ​
  2. void test()
  3. {
  4. 	list<int> lt(3, 1);
  5. 	/*list<int> lt1(lt);*/
  6. 	list<int> lt1(lt.begin(), lt.end());
  7. 	list<int> lt2;
  8. 	cout << lt1.size() <<endl;
  9. 	cout << lt1.empty() <<endl;
  10. 	cout << lt2.empty() <<endl;
  11. 	lt1.resize(10);
  12. 	cout << lt1.size() << endl;
  13. 	for (auto i : lt1)
  14. 	{
  15. 		cout << i << " ";
  16. 	}
  17. }
  18.  
  19. ​

результат операции:

3. Общий доступ и обход

1.Итератор

  1. iterator begin();
  2.  
  3. const_iterator begin() const;
  4.  
  5. iterator end();
  6.  
  7. const_iterator end() const;

Итератор: используется для получения положения первого узла и последнего узла в связанном списке.Следующая позиция (т. е. позиция дозорного)

Например:

  1. void test()
  2. {
  3. 	list<int> lt(5, 2);
  4. 	list<int> ::iterator it = lt.begin();
  5. 	while (it != lt.end())
  6. 	{
  7. 		cout << *it << " ";
  8. 		++it;
  9. 	}
  10. }

результат операции:

2. Обратный итератор

обратный_итератор rbegin();

const_reverse_iterator rbegin() const;

обратный_итератор rend();

const_reverse_iterator rend() const;

Обратный итератор: rbegin получает позицию последнего узла в контейнере, rend получает позицию сторожевого бита в контейнере.

  1. void test()
  2. {
  3. 	list<int> lt = { 1,23,4,4,5,2 };
  4. 	list<int> ::reverse_iterator rit = lt.rbegin();
  5. 	while (rit != lt.rend())
  6. 	{
  7. 		cout << *rit << " ";
  8. 		++rit;
  9. 	}
  10. }

результат операции:

Примечание. Обратный итератор rit также должен использовать ++ вместо --

3.спереди и сзади

передний:

ссылка front();

const_reference front() const;

Возвращает ссылку на данные, хранящиеся в первом узле связанного списка.

назад:

ссылка назад();

const_reference back() const;

Возвращает ссылку на данные, хранящиеся в последнем узле связанного списка.

Например:

  1. void test()
  2. {
  3. 	list<int> lt = {213123,123,34524,213};
  4. 	cout << lt.front() << endl;
  5. 	cout << lt.back() << endl;
  6.  
  7. }

результат операции:

4.Добавить, удалить, проверить и изменить список

1) push_front и pop_front

push_front называется вставкой головы, вставляя элемент из головы связанного списка.

void push_front(const тип_значения& значение);

pop_front называется удалением заголовка, при котором элемент удаляется из заголовка связанного списка.

void pop_front();

void pop_front();

Например:

  1. void test()
  2. {
  3. 	list<int> lt = {213123,123,34524,213};
  4. 	cout << lt.front() << endl;
  5. 	lt.push_front(21345);
  6. 	cout << lt.front() << endl;
  7. 	lt.pop_front();
  8. 	cout << lt.front() << endl;
  9. }

результат операции:

2) push_back и pop_back

push_back называется вставкой хвоста, вставляя элемент из конца связанного списка.

void push_back(const value_type& val);

pop_back называется удалением хвоста, которое удаляет элемент из конца связанного списка.

void pop_back();

Например:

  1. void test()
  2. {
  3. 	list<int> lt = {213123,123,34524,213};
  4. 	cout << lt.back() << endl;
  5. 	lt.push_back(21345);
  6. 	cout << lt.back() << endl;
  7. 	lt.pop_back();
  8. 	cout << lt.back() << endl;
  9. }

результат операции:

3) найти

  1. template <class InputIterator, class T>
  2.  
  3. InputIterator find(InputIterator first, InputIterator last, const T& val);

Найдите значение в диапазоне двух итераторов и верните итератор там, где оно находится.

Например:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 3; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
  9. 	*pos = 114514;
  10. 	for (auto i : lt)
  11. 	{
  12. 		cout << i << " ";
  13. 	}
  14. }

результат операции:

Примечание. Эта функция не является функцией-членом списка, а является функцией стандартной библиотеки. Функция поиска совместно используется несколькими контейнерами.

Как видите, мы можем напрямую разыменовать итератор списка и изменить его содержимое, но не должен ли итератор указывать на узел? Почему разыменование может изменить данные?

Фактически, итератор списка не моделируется и не реализуется с использованием исходного экологического указателя, и его необходимо инкапсулировать внизу, что будет отражено в исходном коде моделируемой реализации списка.

4) вставить

вставка итератора(позиция итератора, const value_type& val);

void insert(позиция итератора, size_type n, const value_type& val);

————————————————————————————————————————

шаблон<class InputIterator>

void insert(позиция итератора, InputIterator первый, InputIterator последний);

Вставьте один или несколько элементов перед позицией

Например:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 3; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
  9. 	lt.insert(pos, 8848);
  10. 	for (auto i : lt)
  11. 	{
  12. 		cout << i << " ";
  13. 	}
  14. }

результат операции:

Внимательные студенты, возможно, обнаружили, что операция вставки спискаНе приведет к тому, что итератор станет недействительным., поскольку узел, на который указывает pos, остается неизменным и относительное положение не меняется.

Однако операция удаления списка определенно приведет к тому, что итератор станет недействительным, и только итератор, указывающий на удаленный узел, будет недействительным, а другие итераторы не будут затронуты.

5) стереть

  1. iterator erase(iterator position);
  2.  
  3. iterator erase(iterator first, iterator last);

Удалить элемент в позиции или все элементы в диапазоне [первый, последний)

Например:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 3; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
  9. 	lt.erase(lt.begin());
  10. 	for (auto i : lt)
  11. 	{
  12. 		cout << i << " ";
  13. 	}
  14. }

результат операции:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 3; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
  9. 	lt.erase(lt.begin(),pos);
  10. 	for (auto i : lt)
  11. 	{
  12. 		cout << i << " ";
  13. 	}
  14. }

результат операции:

6) обмен

void swap(вектор& x);

Поменяйте местами два объекта списка

Например:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	list<int> lt2(6, 12);
  5. 	for (int i = 0; i < 10; i++)
  6. 	{
  7. 		lt.push_back(i);
  8. 	}
  9. 	lt.swap(lt2);
  10. 	for (auto i : lt2)
  11. 	{
  12. 		cout << i << " ";
  13. 	}
  14. 	cout << endl;
  15. }

результат операции:

7) назначить

шаблон<class InputIterator>

void assign(InputIterator первый, InputIterator последний);

void assign(size_type n, const value_type& val);

Укажите новое содержимое списка, замените его текущее содержимое и измените количество узлов.

Например:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 10; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	lt.assign(4, 0);
  9. 	for (auto i : lt)
  10. 	{
  11. 		cout << i << " ";
  12. 	}
  13. }

результат операции:

8) очистить

void очистить();

Удалить все узлы в связанном списке

Например:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 10; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	lt.clear();
  9. 	cout << lt.size() << endl;
  10. }

результат операции:

5.Интерфейс изменения порядка списка

(1）Сортировать

void сортировать();

шаблон<class Compare>

void sort(Сравнить comp);

Из-за особенностей структуры списка функцию сортировки в стандартной библиотеке использовать нельзя, поскольку итератор не может выполнять операции вычитания.

И в документации C++ мы видим, что эта сортировка в стандартной библиотеке также ограничивает тип итератора произвольным доступом (RandomAccess).

  1. default (1)	
  2. template <class RandomAccessIterator>
  3.   void sort (RandomAccessIterator first, RandomAccessIterator last);
  4. custom (2)	
  5. template <class RandomAccessIterator, class Compare>
  6.   void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Итераторы имеют несколько функциональных категорий:

  • Односторонний итератор, может делать только ++
  • Двунаправленный итератор, может быть ++ и --
  • Случайный итератор, может быть ++, --, + и -

Однако функция сортировки списка не требуется, поскольку эффективность прямой сортировки связанного списка намного медленнее, чем копирование в вектор, сортировка и последующее копирование обратно в связанный список.

(2）обеспечить регресс

template <class BidirectionalIterator>
  void reverse (BidirectionalIterator first, BidirectionalIterator last);

Инвертировать связанный список

Например:

  1. void test()
  2. {
  3. 	list<int> lt;
  4. 	for (int i = 0; i < 10; i++)
  5. 	{
  6. 		lt.push_back(i);
  7. 	}
  8. 	for (auto i : lt)
  9. 	{
  10. 		cout << i << " ";
  11. 	}
  12. 	cout << endl;
  13. 	lt.reverse();
  14. 	for (auto i : lt)
  15. 	{
  16. 		cout << i << " ";
  17. 	}
  18. 	cout << endl;
  19.  
  20. }

результат операции:

Если есть ошибки, пожалуйста, поправьте меня.

Личный профиль

Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.

моя контактная информация

Почта