Shulou(Shulou.com)06/02 Report--

Editor to share with you the example analysis of list in C++ data structures. I hope you will get something after reading this article. Let's discuss it together.

Preface

List is more complex than vector, and its advantage is that inserting and deleting anywhere is an O (1) time complexity.

1. The node template struct _ _ list_node {typedef void* void_pointer; void_pointer next; void_pointer prev; T data;} of list

This is the definition of the node of list in the stl3.0 version, where there is a front pointer, a back pointer, and a data data. We can only know that it is a two-way linked list, and we can take another look at list's constructor about it.

Class list-- > list () {empty_initialize (); void empty_initialize () {node = get_node (); node- > next = node; node- > prev = node;}

If you look at its list (), you can see that the empty_initialize () he calls creates a header node and is a circular structure.

To sum up: the overall structure of list is a leading circular two-way linked list.

2. Iterator of list

How iterators are usually used, take a look at the following code.

Int main () {list 1; l.push_back (1); l.push_back (2); l.push_back (3); l.push_back (4); l.push_back (5); l.push_back (6); list::iterator it = l.begin () While (it! = l.end ()) {cout _ next; return * this;} T & operator* () {return _ node- > node;} private: Node* _ node }

The implementation here is incomplete, but it is very illustrative. By overloading opertaor++, and opertaor*, we can access a node like a pointer, so that we can access data with the same interface as vector and string, which is a very powerful technology.

Note:

We realize the access to a node by overloading operator++ and other interfaces on the node, and when we access it, we actually create an iterator object to access our data, so we encapsulate the pointer of the node.

Because the underlying structure of list is different from that of vector, list's iterator will not cause iterator failure in insert operation and engagement operation (splice). Only when deleted, only the iterator of the deleted element will fail, without affecting the later, and vector will all fail.

Why are there three template parameters?

2.1 const iterator

There is a situation where we need a const object to traverse, if we have a function called print_list (const list)

& lt)

Passing parameters: const in passing parameters is because the object will not be modified, and references are added because there is no need for deep copy to improve efficiency.

Function: this function is to print the contents of the linked list. But according to our above implementation, what will happen?

This is normal, when const iterators generate const iterator objects, when vector,string iterators are native pointers, we only need typedef const T* const_iterator, so if we do a similar operation in our generated list, let's see the results.

As a result, we found that it didn't seem to be a big problem, but when we tried to modify the contents of the const iterator, we found that we could change it successfully. How can the const iterator modify the data in it? This is a problem! It shows that we have a huge hidden danger in it.

2.2 Modification method

Of course, the easiest way is to write another iterator and replace _ _ list_iterator with _ _ list_const_iterator and so on, but if we observe carefully, in fact, a lot of things in these two classes are duplicated, only the return value needed when operator*,operator- >, we need to find a way to make the return value of the const object is also the const object, the answer is to add two more template parameters.

Let's add a template parameter as an example to implement a Ref operator* ()

Template class _ _ list_node {public: _ _ list_node (const T & val = T ()) / / it is better to use a full default: _ next (nullptr), _ pre (nullptr) Node (val) {} public: _ _ list_node* _ next _ _ list_node* _ pre; T node;}; template class _ list_itertaor {public: typedef _ _ list_node Node; _ _ list_itertaor (Node* node) {_ node = node } bool operators = (const _ _ list_itertaor& it) {return _ node! = it._node;} _ _ list_itertaor& operator++ () {_ node = _ node- > _ next Return * this;} Ref operator* () / / returns Ref, and the returned value is different {return _ node- > node;} private: Node* _ node;} Template class list {typedef _ list_node Node; public: typedef _ _ list_itertaor iterator; typedef _ _ list_itertaor const_iterator;// modifies iterator begin () {return iterator (_ node- > _ next) } iterator end () {return iterator (_ node);} const_iterator begin () const {return const_iterator (_ node- > _ next) } const_iterator end () const {return const_iterator (_ node);} list () {_ node = new Node; _ node- > _ next = _ node _ node- > _ pre = _ node;} void push_back (const T & val) {Node* newnode = new Node (val); Node* tail = _ node- > _ pre; tail- > _ next = newnode Newnode- > _ pre = tail; newnode- > _ next = _ node; _ node- > _ pre = newnode;} private: Node* _ node;}

Figure 1: that is, list is defined in our test side test function

:: const_iterator cit= l.begin (); the iterator object will recognize the defined const iterator, and its second template parameter is const arguments, so we only need to return the second template parameter when we return operator* ().

By the same token, there will also be calls to const objects and normal objects in the interface operator- > we are going to use. We put the implementation of the code out here, take it if necessary.

-"Code Cloud Link"-

Second, inadequacies in beauty

List seems to have all the advantages mentioned above.

With the insertion and deletion of O (1) time anywhere, the problem of iterator failure becomes less. But what are his shortcomings?

Random access is not supported

The efficiency of sorting is slow, and the sort in the library uses merge sorting-> Quick sorting requires three-digit sorting, and it is inefficient for linked lists to be implemented, so when the elements of the linked list need to be sorted, we usually copy them to vector and then use the sorting in vector.

In the same way, the inversion efficiency of linked lists is not high!

III. Classification of iterators

From a functional point of view, iterators can be divided into const iterators / ordinary iterators + forward and reverse.

From the point of view of the bottom structure of the container, it is divided into one-way, two-way and random.

Unidirectional: single linked list iterator (forward_list) / hash table iterator; these only support unidirectional + +

Bidirectional: double-linked list iterator / map iterator; these supported + /-operations

Random iterators: string/vector/deque; these support + + /-/ + /-operations, similar to native pointers.

Let's take a look at some functions, for example, if the template parameter in sort is written as RandomAccessIterator, we want to make it clear that what the user needs here is a random iterator, and the + operation of the iterator will be called at its bottom, so it's not good if you pass a two-way or one-way iterator at this time!

/ / sort's function declaration template void sort (RandomAccessIterator first, RandomAccessIterator last); custom (2) template void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp)

For example, the reverse function declares that its template parameter is BidirectionalIterator, that is, it needs a bidirectional iterator. At this time, we can actually pass a random iterator and a bidirectional iterator. From the operations supported by the iterator above, we can see that the random iterator supports all the operations of the bidirectional iterator.

By the same token, if it is a place that needs an one-way iterator, we can pass a two-way, random, one-way iterator!

Std::reversetemplate void reverse (BidirectionalIterator first, BidirectionalIterator last)

From the stl_iterator.h in stl3.0, we can see the inheritance relationship in it. We'll talk about that later.

Note: difference_type is the distance between two iterators. Type ptrdiff_t is unsigned shaping.

3.x an error in std::find

When we implement our own data structure, such as list, we will report an error if we use the std:find in the library to find the data in our implemented data structure. The blogger's test version is vs2013, which may not be checked and will not report an error in other versions.

Void test_list () {list 1; l.push_back (5); list::iterator it = std::find (l.begin (), l.end (), 5);}

Error report: the error here says that iterator_category is not in our iterator, which is a check on our iterator type.

The following declaration has been added to the iterator in stl_list.h to solve this problem.

Solution: we can use the declaration of iterators in stl_list.h under the stl3.0 version. You can also use the release version, you can run through it.

Typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef ptrdiff_t difference_type

After reading this article, I believe you have some understanding of "sample Analysis of list in C++ data structures". If you want to know more about it, you are welcome to follow the industry information channel. Thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.