[C++] list basic interface

Parents are like iterators that encapsulate their vulnerability ……

Hand torn list catalog:

I. List’s common interfaces and their use

1.1 List Constructors and Adding, Deleting, Checking and Changing

1.2list Special Interfaces

1.3 List Sorting Performance Analysis

Second, list iterator implementation (focus + difficulty)

Introductory knowledge about iterators:

2.1 Classification of Iterators

2.2 List Iterator Failure Problems (Differences from vector)

2.3list Iterator Source Code Template

2.4list Overall basic framework

III. Hand-tearing list iterator

3.1 Overloading operator*()

3.2 Overloading ++, -,! =

3.3 Optimization using class templates

IV. Additions, deletions and changes

4.1 insert (parameters must be referenced, worry about non-built-in types) and erase

4.2 push_back and push_front

4.3 pop_back and pop_front

V. List Construct + Assignment Overloading

5.1 Default Constructs + Iterator Interval Constructs + Copy Constructs

5.2 Assignment Overloading Modern Writings

5.3 Problems with class names and types (a C++ pitfall)

VI. Comparison of lists and vectors (emphasis added)

VII. Source Code Collection

I. List’s common interfaces and their use

1.1 List Constructors and Adding, Deleting, Checking and Changing

A list is a sequential container that can be inserted and deleted at any position within a constant range.bounded bi-directional recurring tableThe use of common interfaces for lists is the same as for string and vector containers, so I won’t go into detail here, see our old friend:cplusplus.com – The C++ Resources Network

Constructor:

Add, delete, check and change:

Caution:

1, because the physical structure of the list is non-contiguous – the positional relationship between the address of the previous node and the address of the next node is random, so the list does not support random access, and naturally theThe [ ] operation is not supported.；

2, list does not support reserve operation, because the list of nodes is used to open, used to destroy, can not reserve space;

(It is also easy to see from this characterization thatIf you need to keep inserting and deleting elements, it’s better to utilize lists.）

1.2list Special Interfaces

In addition to the general interfaces that STL containers basically have, lists also provide some unique and specialized interfaces, as follows:

Off-topic: Why do lists need to implement the sort interface themselves? Does it mean that the encapsulation in the library is not good? Is it not efficient?

We start by using the library’s own sort function:

We use the sort function from the algorithm library:

void test_sort()
{
     list<int> l1{5,6,4,8,9,2,7}; //C++ 11
     sort(l1.begin(),l1.end());
     for(auto l : l1)
     {
        cout << l << " ";
     }
     cout << endl;
}

Reported an error (unexpectedly, why would I write about this if I didn’t report an error doge) The reason for the error says that there is no – iterator.

Let’s take a look at the sort source code

All of this is caused by the iterator of the sort!

Caution:

1、Chained lists can only be sorted using the sort interface provided by the list, not the sort interface provided by the algorithm.Because chained listsPhysical address discontinuity, the iterator is a bidirectional iterator.The + – operation is not supported，The sort function in the algorithm library needs to support random iterators of + –；

2. Chained tablesBefore de-duplication, you must ensure that the list is ordered, otherwise the de-weighting is incomplete;

3. Two ordered linked lists remain ordered after merging;

Finally, while lists provide interfaces with special features that do serve a purpose, these special interfaces are actually used very infrequently, including the sort interface (which is too inefficient for chaining lists).

1.3 List Sorting Performance Analysis

Although chained list sort can only use the sort interface provided by the list, but not the sort interface provided by the algorithm, but its frequency of use is still very low, this is due to the efficiency of the chained list sort is too low, we can through the comparison of the two sets of test data to intuitively feel the efficiency of the chained list sort.

Test 1: Comparison of vector sorting and list sorting performance

//vector sort vs. list sort -- release version
void test_op1() {
	srand((size_t)time(0));
	const int N = 1,000,000; //1,000,000 data

	vector<int> v;
	v.reserve(N);
	list<int> lt;
	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		v.push_back(e);
		lt.push_back(e);
	}

	//vector sort
	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	//list sort
	int begin2 = clock();
	lt.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

Test 2: Sorting list directly vs. copying data to vector, sorting with vector, and then copying data back to list.

Performance comparison of //list sort vs. transferring data to a vector, sorting it, and then copying it back -- under the release version.
void test_op2()
{
	srand(time(0));
	const int N = 1,000,000; //1,000,000 data
	list<int> lt1;
	list<int> lt2;
	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		lt1.push_back(e);
		lt2.push_back(e);
	}

	//list sort -- lt1
	int begin1 = clock();
	lt1.sort();
	int end1 = clock();

	// Copy the data into a vector and sort it, then copy it back when you're done -- lt2
	int begin2 = clock();
	vector<int> v;
	v.reserve(N);
	for (auto e: lt2) // Copy
	{
		v.push_back(e);
	}
	sort(v.begin(), v.end());  // Sort
	lt2.assign(v.begin(), v.end());  // Copy
	int end2 = clock();

	printf("list1 sort:%d\n", end1 - begin1);
	printf("list2 sort:%d\n", end2 - begin2);
}

As you can see, list sort is much less efficient than vector sort, even if it is possible to use list sort is not as efficient as copying the data into a vector, then using vector sort, and then copying the data back into the list after sorting;So the sort interface in list is frustrating!

Second, list iterator implementation (focus + difficulty)

Introductory knowledge about iterators:

The value of iterators is in encapsulating the underlying implementation of theDoes not specifically expose the underlying implementation details and provides uniform access

The iterator is just the spokesperson! The real big bully is actually _list_iterator

Why is the trick of making iterators into pointers in lists not working well anymore?

In the array, * pointer is the element, pointer ++ is +sizeof(T) object size, no way, who called them physical space continuous, structure NB, soFor vector and string classes, the physical space is contiguous, the native pointers are iterators now, and the dereferences are data。But for the list here, the space is discontinuous

Solution:

At this point you can’t get the data if you dereference it (space is not contiguous), let alone ++ pointing to the next node. So, for list iterators, the native pointer no longer meets our needs, and we need to go for special treatment: class wrapping.We can support this through class encapsulation as well as operator overloading, so that we can implement operators like the built-in types

Two features of iterators:

1. Dereferencing 2. ++ / —

The big task of operator overloading:

realizationDereferencing operator*()and ++ functions

2.1 Classification of Iterators

Iterators can be categorized into a total of three types according to their function:

• one-way iterator – Iterators only support ++ and reference operations (single linked tables, hashes).

• bidirectional iterator – Iterators support ++, –, and reference operations, but not + and – operations (lists).

• randomizer – Iterators support not only ++, — and reference operations, but also + and – operations, i.e., iterators can access random (string, vector)

This is also a good indication that vectors and strings can be used with the library’s sort function

Iterators can also be divided into two categories: normal iterators and const iterators:

//1.const T* p1
list<int>::const_iterator cit = lt.begin();
//2.T* const p2
const list<int>::iterator cit = lt.begin();
// doesn't match the behavior of const iterators, since the protected iterator itself cannot be modified, then we can't ++ iterators either

Soul torture: is the const iterator p1 or p2? p1

The const iterator resembles the behavior of p1 in that it protects the object it points to from being modified, and the iterator itself can be modified.

2.2 List Iterator Failure Problems (Differences from vector)

vector iterator failure: insert expand + erase will fail when

Unlike vector, theThe list does not suffer from iterator failure after an insert operation.Because the new nodes inserted by list are dynamically opened, and because the physical addresses of each node of list are uncorrelated, theThe insertion of a new node does not affect the addresses of the other nodes.；

However, iterator failure occurs after list erase because thelist Deleting a node releases the node directly, and accessing it again will result in out-of-bounds access.

2.3list Iterator Source Code Template

We know that an iterator is something like a pointer, i.e., an iterator has to be able to implement all or some of the operations associated with pointers – ++, -, *, +, -; for our previous string and vector iterators, an iterator is a native pointer, so it naturally supports the above operations;

But for a list, the nodes of the list are a structure, and the physical address of each node of the list is not continuous, if we still simply typedef the pointer to the node as an iterator, then it is obviously not able to realize the operation of dereferencing, ++, etc..So we need to encapsulate the iterator with a structure/class, and then with operator overloading and other operations so that the iterator can realize operations such as dereferencing, ++, –, etc.

The framework code is as follows:

//Node definition
template <class T>
struct __list_node {
    typedef void* void_pointer;
    void_pointer next;
    void_pointer prev;
    T data;
};

//Iterator definition
typedef __list_iterator<T, T&, T*>   iterator;
typedef __list_iterator<T, const T&, const T*>  const_iterator;

// Iterator class
template<class T, class Ref, class Ptr>
struct __list_iterator {
     typedef __list_iterator<T, Ref, Ptr>  self;
     typedef __list_node<T>* link_type; // pointer to the node
     link_type node; // class member variable
    
     __list_iterator(link_type x) : node(x) {} //construct node pointer as class object
    
    //... Using operator overloading to support various behaviors of iterators
    self& operator++() {...}
    self& operator--() {...}
    Ref operator*() const {...}
};

2.4list Overall basic framework

namespace lzy
{
    // Nodes
	template<class T>
	struct list_node
	{
		list_node* _next;
		list_node* _prev;
		T _data;

		list_node(const T& x)//constructor and initialization list for node
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};

	template<class T>
	class list
	{
		typedef list_node<T> node;
	public:
        //Iterators
		typedef __list_iterator<T> iterator;
        typedef __list_const_iterator<T> const_iterator;
        //construction
		list()
		{
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
		}
	private:
		node* _head;
        size_t _size;
	};
}

III. Hand-tearing list iterator

For the implementation of iterator we need to go for normal iterator and const iterator. The difference between these two types of iterators also brings about different interfaces. We can go separately to the implementation, we first look at a simple construct iterator, just need to provide a node can be, look at the basic framework for implementation:

    template<class T>
	struct __list_iterator
	{
		typedef list_node<T> node;
		node* _pnode;

		__list_iterator(node* p)
			:_pnode(p)
		{}
    }

Why don’t iterators write copy constructors? Does shallow copying really work?

We don’t need to manually implement copy construction and assignment overloading for iterators ourselves.By default, the compiler generates a shallow copy, which is what we need.And that’s saying something.It’s not that we need to implement deep copy if there are pointersand iterators don’t need to write destructors, so there’s no need for deep copies.

Why are we talking about this? Because list<int>::iterator it=v.begin() which is a copy construction

3.1 Overloading operator*()

This one is relatively simple, it’s all about getting the data pointed to by the iterator and returning a reference to the data:

T& operator*()
{
    return _pnode->_data;
}

 3.2Overloading ++, -,! =

	   __list_iterator<T>& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		__list_iterator<T>& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		bool operator!=(const __list_iterator<T>& it)
		{
			return _pnode != it._pnode;
		}

If we follow the above, let’s take a look at the difference between a normal iterator and a const iterator at this point:

//typedef __list_iterator<T> iterator;
//typedef __list_const_iterator<T> const_iterator;
    template<class T>
	struct __list_iterator
	{
		typedef list_node<T> node;
		node* _pnode;

		__list_iterator(node* p)
			:_pnode(p)
		{}

		T& operator*()
		{
			return _pnode->_data;
		}

		__list_iterator<T>& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		__list_iterator<T>& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		bool operator!=(const __list_iterator<T>& it)
		{
			return _pnode != it._pnode;
		}
	};

	// Difference from normal iterator: traversal, can't modify data with *it
	template<class T>
	struct __list_const_iterator
	{
		typedef list_node<T> node;
		node* _pnode;

		__list_const_iterator(node* p)
			:_pnode(p)
		{}

		const T& operator*()
		{
			return _pnode->_data;
		}

		__list_const_iterator<T>& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		__list_const_iterator<T>& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		bool operator!=(const __list_const_iterator<T>& it)
		{
			return _pnode != it._pnode;
		}
	};

Code redundancy!!! Code redundancy!!! Code redundancy!!!

If this is the way to implement it, we will see that there is not much difference between the two iterator implementations, the only difference is the operator*.The only difference between a const iterator and a regular iterator is that a regular iterator returns T&, which is readable and writable, and a const iterator returns const T&, which is readable and unwritable.We can refer to the source code for the implementation:Class Template ParametersSolving this problem is what makes iterators so powerful

3.3 Optimization using class templates

template <class T,class Ref,class Ptr>
//typedef __list_iterator<T, T&, T*> iterator;
//typedef __list_iterator<T, const T&, const T*> const_iterator;

Code after correction using class template parameters:

//  typedef __list_iterator<T, T&, T*> iterator;
	//  typedef __list_iterator<T, const T&, const T*> const_iterator;
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> node;
		typedef __list_iterator<T, Ref, Ptr> Self;
		node* _pnode;
		__list_iterator(node*p)
			:_pnode(p)
		{
		}
		// Pointer to return data
		Ptr operator->()
		{
			return &_pnode->_data;
		}
		//Template parameters for return values
		Ref operator *()
		{
			return _pnode->_data;
		}

		//++it
		Self& operator ++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		//it++
		Self operator ++(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}

		Self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		Self operator--(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}

		bool operator !=(const Self& it)const
		{
			return _pnode != it._pnode;
		}

		bool operator ==(const Self& it)const
		{
			return _pnode == it._pnode;
		}
	};

Same class template, at this point we pass different parameters instantiated into different iterators now!!!! This solves the code redundancy problem we just described

IV. Additions, deletions and changes

4.1 insert (parameters must be referenced, worry about non-built-in types) and erase

insert: an insert at position pos, return the insert position of the iterator, for list insert iterator will not fail, vector failure is due to the expansion of the pos position caused by the expansion of wild pointer problems

		iterator insert(iterator pos,const T& x)
		{
			node* newnode = new node(x);
			node* cur = pos._pnode;
			node* prev = cur->_prev;

			newnode->_prev = prev;
			prev->_next = newnode;
			newnode->_next = cur;
			cur->_prev = newnode;

			++_size;
			return iterator(newnode);
		}

erase: here with the head (sentinel position) head node can not be deleted, the return value is to delete the position of the next, for the list of erase iterator is invalidated

		iterator erase(iterator pos)
		{
			assert(pos != end());
			node* prev = pos._pnode->_prev;
			node* next = pos._pnode->_next;

			prev->_next = next;
			next->_prev = prev;
			delete pos._pnode;
			--_size;
			return iterator(next);
		}

4.2 push_back and push_front

        void push_back(const T& x)
		{
			insert(end(), x);
		}

		void push_front(const T& x)
		{
			insert(begin(), x);
		}

Caution!Position of the begin and end of the list

Also this question extends to another question:Why are iterators written this way when accessing elements?

In vector, the physical address is consecutive, so this writing is still justifiable, after analyzing the begin and end of the list, you still dare to write this way?

Straight away it reports an error, so the correct one should be! =, not <

void test3()
{
    vector<int> vv={1,5,7,8,9,3,4};
    list<int> l={1,5,6,7};
    vector<int>::iterator it1=vv.begin();
    list<int>::iterator it2=l.begin();
    while(it1 < vv.end())
    {
        cout << *it1 << " ";
        it1++;
    }
    cout << endl;
    // while(it2 < l.end())
    // {
    //     cout << *it2 << " ";
    //     it2++;
    // }
    while(it2 != l.end())
    {
        cout << *it2 << " ";
        it2++;
    }
    cout << endl;
}

4.3 pop_back and pop_front

For tail and head deletions, reuse erase.

		void pop_front()
		{
			erase(begin());
		}

		void pop_back()
		{
			erase(--end());
		}

The tail deletion here just happens to use our overloaded

V. List Construct + Assignment Overloading

5.1 Default Constructs + Iterator Interval Constructs + Copy Constructs

Default construction:

list()
{
    _head = new node(T());
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}

We can use empty_initialize() to encapsulate the initialization for easy reuse without having to write it every time:

void empty_initialize()
{
    _head = new node(T());
    _head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}

Iterator interval construction:

//Iterator interval construction
		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_initialize();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

Copy construction:

Tradition:
 

		list(const list<T>& lt)
		{
			empty_initialize();
			for (const auto& e : lt)
			{
				push_back(e);
			}
		}

userange for the tail insertion, but be careful to add &, range for is *it assigned to the e, another copy, e is the type of object T, in turn, to obtain the data in the container, T if it is a string type, and constantly copy, push_back and then destroy the

Modern:

		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}		
		list(const list<T>& lt)
		{
			empty_initialize();
			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

5.2 Assignment Overloading Modern Writings

		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

5.3 Problems with class names and types (a C++ pitfall)

Checking the official documentation, we can see that list has no type:

list<T>& operator=(list<T> lt)
list& operator=(list lt) 

For common classes: the class name is equivalent to the type

For class templates: class name is not equivalent to type (e.g. list template, class name: list type: list)

Inside a class template you can use the name of the class to represent the type, but it is not recommended, outside the class you have to take the template parameter list

VI. Comparison of lists and vectors (emphasis added)

VII. Source Code Collection

#pragma once

#include <iostream>
#include <assert.h>
#include <algorithm>

namespace lzy {
	template<class T>
	struct list_node //list node structure definition
	{
		list_node<T>* _next;// It's correct not to add <T>, but it's better to write it
		list_node<T>* _prev;
		T _data;

		list_node(const T& x)// construction
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};

	// Iterator Final
	//const iterator -- add template parameter to solve operator*() return value vs operator->() return value problem
	//typedef __list_iterator<T, T&, T*> iterator;
	//typedef __list_iterator<T, const T&, const T*> const_iterator;
	//The way the big boys in the /STL source code wrote it, using multiple template parameters to avoid code redundancy caused by copies
	template<class T, class Ref, class Ptr>
	struct __list_iterator // iterator class
	{
		typedef list_node<T> node;  // Rename the list node
		typedef __list_iterator<T, Ref, Ptr> Self; // Renamed here so that it is the only thing that needs to be changed when the template parameter is added later.
		node* _pnode; // node pointer as the only member variable of the class

		__list_iterator(node* p)
			:_pnode(p)
		{}

		Ref operator*() // dereference
		{
			return _pnode->_data;
		}

		Ptr operator->()  //->
		{
			return &_pnode->_data;
		}

		Self& operator++() // Prefix ++
		{
			_pnode = _pnode->_next;
			return *this;
		}

		Self& operator++(int) // Postset to ++
		{
			Self it(*this);
			_pnode = _pnode->_next;
			return it;
		}

		Self& operator--() // prefix --
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		Self& operator--(int) // Postposition --
		{
			Self it(*this);
			_pnode = _pnode->_prev;
			return it;
		}

		bool operator!=(const Self& it) const //!=
		{
			return _pnode != it._pnode;
		}

		bool operator==(const Self& it) const  //==
		{
			return _pnode == it._pnode;
		}
	};

	//list class
	template<class T>
	class list
	{
		typedef list_node<T> node;  //list node
	public:
		typedef __list_iterator<T, T&, T*> iterator;  // iterator
		typedef __list_iterator<T, const T&, const T*> const_iterator; //const iterator

		//Iterators
		iterator begin() {
			return iterator(_head->_next);
		}

		iterator end() {
			//iterator it(_head);
			//return it;

			// It is easier to utilize anonymous objects directly
			return iterator(_head);
		}

		const_iterator begin() const {
			return const_iterator(_head->_next);
		}

		const_iterator end() const {
			return const_iterator(_head);
		}

		void empty_initialize() { //initialize -- sentinel bit head node
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0; // space for time, used to mark the number of nodes
		}

		list() { //construct, not list<T> for a reason: the constructor function name is the same as the class name, and list<T> is type
			empty_initialize();
		}

		//Iterators区间构造
		template <class InputIterator>
		list(InputIterator first, InputIterator last) {
			empty_initialize();
			while (first != last)
			{
				push_back(*first);
				++first;
				//first++;
			}
		}

		//Copy Construction Traditional Writing
		//list(const list<T>& lt) {
		//	empty_initialize();

		//	for (const auto& e : lt)
		//	{
		//		push_back(e);
		//	}
		//}

		// A modern way of writing copy constructs
		//list(const list& lt) This is how the official library writes it, due to the fact that class names are equivalent to types within classes, but it is not recommended that you write it yourself.
		list(const list<T>& lt) {
			empty_initialize(); //initialize the header node to prevent the tmp wild pointer from calling destructor properly after the swap
			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		//Assignment overloading traditional writing
		//list<T>& operator=(const list<T>& lt) {
		//	if (this != &lt)
		//	{
		//		clear();
		//		for (const auto& e : lt)
		//		{
		//			push_back(e);
		//		}
		//	}
		//	return *this;
		//}

		//Assignment overloading modern writing
		//list& operator=(list lt)
		list<T>& operator=(list<T> lt) { // can't add reference, lt is generated by calling copy constructs
			swap(lt);
			return *this;
		}

		~list() { //deconstruction
			clear();
			delete _head;
			_head = nullptr;
		}

		void swap(list<T>& lt) { // swap two linked lists, essentially swapping the head nodes of two linked lists
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		size_t size() const { //add a counting member to trade space for time
			return _size;
		}

		bool empty() {// bool empty
			return _size == 0;
		}

		void clear() {
			iterator it = begin();
			while (it != end()) {
				it = erase(it);
			}
			_size = 0;
		}

		void push_back(const T& x) {
			//node* newnode = new node(x);
			//node* tail = _head->_prev;
			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;

			insert(end(), x);  // Multiplex
		}

		void push_front(const T& x) {
			insert(begin(), x);  // Multiplex
		}

		void pop_front() {
			erase(begin());
		}

		void pop_back() {
			erase(--end());
		}

		iterator insert(iterator pos, const T& x) {
			node* newnode = new node(x);
			node* cur = pos._pnode;
			node* prev = cur->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;
			cur->_prev = newnode;
			newnode->_next = cur;

			++_size;
			return iterator(pos);
		}

		iterator erase(iterator pos) {
			assert(pos != end());

			node* prev = pos._pnode->_prev;
			node* next = pos._pnode->_next;

			prev->_next = next;
			next->_prev = prev;
			delete pos._pnode;

			--_size;
			return iterator(next);
		}

	private:
		node* _head;
		size_t _size;
	};
}

“Finished” and “Flowers”.