Technology Sharing

[C Beginner] Preliminary understanding of list class

2024-07-12

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

1. Standard Librarylistkind

The bottom layer of the list is a bidirectional circular linked list structure with a sentinel position.
Compared with the single linked list structure of forward_list, the iterator of list is a bidirectional iterator
Compared with sequential containers such as vector, list is more efficient in inserting and deleting at any position, but does not support random access at any position.
List is a template class. When using it, we need to give the type of the element.

When using the list class, you need to include the header file<list>

2. Common interfaces of list class

1. Commonly used constructors

1. Default constructor, construct an empty linked list

list();

For example:

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

2. Construct a list object and initialize it with n val

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

For example:

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

operation result:

3. Copy constructor of list class

list(const list& x);

For example:

  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. }

operation result:

4. Use iterator initialization construction

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

For example:

  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. }

operation result:

2. Commonly used capacity interfaces

It’s still the same old things, let me talk about them one by one.

1.size,empty,max_size,resize

size:returnLinked ListThe number of elements in the container.

size_type size() const;

empty:returnListIs the container empty (i.e. itssizeis 0).
(Note: This function does not modify the container in any way. To clearLinked ListContainer contents, seelist::clear。）

bool empty() const;

max_size(uncommon): returnLinked ListThe maximum number of elements the container can hold.
(Due to known system or library implementation limitations, this is the maximum potential that the container can achieve.size, but the container is by no means guaranteed to reach that size: it may still fail to allocate storage at any time before that size is reached.)

size_type max_size() const;

resize:Resize the container to containnelements.
ifnSmaller than the current containersize, the content will be reduced to its previousnelements, removing those that exceed that limit (and destroying them).
ifnLarger than the current containersize, the contents are extended by inserting the required number of elements at the end to achievenIf you specifyval, then the new element will be initialized tovalOtherwise, they are value-initialized.
(Note that this function changes the actual contents of the container by inserting or erasing elements from it.)

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

For example:

  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. ​

operation result:

3. Common access and traversal

1. Iterators

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

Iterator: used to get the position of the first node and the last node in the linked listNext position (i.e. sentinel position)

For example:

  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. }

operation result:

2. Reverse Iterator

reverse_iterator rbegin();

const_reverse_iterator rbegin() const;

reverse_iterator rend();

const_reverse_iterator rend() const;

Reverse iterator, rbegin gets the position of the last node in the container, and rend gets the position of the sentinel in the container

  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. }

operation result:

Note: The reverse iterator rit should also use ++ instead of --

3.front and back

front:

reference front();

const_reference front() const;

Returns a reference to the data stored in the first node in the linked list

back:

reference back();

const_reference back() const;

Returns a reference to the data stored in the last node in the linked list

For example:

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

operation result:

4. Add, delete, check and modify the list

1) push_front and pop_front

push_front is called head insertion, inserting an element from the head of the linked list

void push_front(const value_type& val);

pop_front is called head deletion, which deletes an element from the head of the linked list

void pop_front();

void pop_front();

For example:

  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. }

operation result:

2) push_back and pop_back

push_back is called tail insertion, inserting an element from the end of the linked list

void push_back(const value_type& val);

pop_back is called tail deletion, which deletes an element from the tail of the linked list

void pop_back();

For example:

  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. }

operation result:

3) find

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

Searches for val in two iterator intervals and returns the iterator at that location.

For example:

  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. }

operation result:

Note: This function is not a member function of list, but a function in the standard library. Multiple containers share the find function.

As you can see, we can directly dereference the iterator of the list and modify its content, but shouldn't the iterator point to the node? Why can dereferencing it modify the data?

In fact, the iterator of the list is not simulated using native pointers, but requires underlying encapsulation, which will be reflected in the source code of the simulated implementation of the list.

4）insert

iterator insert(iterator position, const value_type& val);

void insert(iterator position, size_type n, const value_type& val);

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

template<class InputIterator>

void insert(iterator position, InputIterator first, InputIterator last);

Insert one or more elements before position

For example:

  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. }

operation result:

Careful students may have discovered that the insert operation of list isWill not cause iterators to become invalidBecause the node pointed to by pos does not change, the relative position does not change.

However, the deletion operation of the list will definitely cause the iterator to become invalid, and only the iterator pointing to the deleted node will become invalid, and other iterators will not be affected.

5) erase

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

Delete the element at position or all elements in the interval [first, last)

For example:

  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. }

operation result:

  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. }

operation result:

6) swap

void swap(vector& x);

Swap two list objects

For example:

  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. }

operation result:

7）assign

template <class InputIterator>

void assign(InputIterator first, InputIterator last);

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

Assign new content to the list, replace its current content and modify the number of nodes

For example:

  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. }

operation result:

8）clear

void clear();

Delete all nodes in the linked list

For example:

  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. }

operation result:

5.List order modification interface

(1）sort

void sort();

template<class Compare>

void sort(Compare comp);

Due to the special structure of the list, the sort function in the standard library cannot be used, because the iterator cannot perform subtraction operations.

And in the C++ documentation, we can see that the sort in the standard library also limits the iterator type to be able to perform random access (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);

Iterators have several functional categories:

  • One-way iterator, can only perform ++
  • Bidirectional iterator, can be ++ and --
  • Random iterator, can be ++, --, + and -

But the list sort function is unnecessary, because sorting the linked list directly is much slower than copying it to a vector, sorting it, and then copying it back to the linked list.

(2）reverse

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

Reverse the linked list

For example:

  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. }

operation result:

If there are any errors, please feel free to point them out.

Personal profile

I have devoted myself to the research of technology for more than 30 years. I am proficient in various languages ​​such as Java, Linux, JavaScript, PHP, CSS, etc. I have made many contributions in the field of open source. I have established a developer documentation site to share some problems in technology development for everyone to read.

my contact information

Mail