list Source code 1( Reference resources STL Source code -- Hou Jie ):list node 、 iterator 、 data structure

list Source code 2( Reference resources STL Source code -- Hou Jie ):constructor、push_back、insert

list Source code 3( Reference resources STL Source code -- Hou Jie ):push_front、push_back、erase、pop_front、pop_back、clear、remove、unique

list Source code 4( Reference resources STL Source code -- Hou Jie ):transfer、splice、merge、reverse、sort

transfer

list Internally, it provides a so-called migration technology :transfer, Before migrating elements of a continuous range to a specified location :

// take [first,last] Move all elements in to position Before 
void transfer(iterator position,iterator first,iterator last){
if(position!=last){
(*(link_type((*last.node).prev))).next=position.node; //
(*(link_type((*first.node).prev))).next=last.node; //
(*(link_type((*position.node).prev))).next=first.node; //
link_type temp=link_type((*position.node).prev); //
(*position.node).prev=(*last.node).prev; //
(*last.node).prev=(*first.node).prev; //
(*first.node).prev=temp; //
}
}

transfer Accepted [first,last] Section , There can be the same list Inside , Above transfer Not a public interface ,list The public interface for is splice;splice: Take a continuous range of elements from a list Move to another list At a certain point of , Use as follows :

#include<bits/stdc++.h>
using namespace std; int main() {
list<int> l1={,,,,,};
int a[]={,,,};
list<int> l2={a,a+}; list<int>::iterator it=find(l1.begin(),l1.end(),);
list<int>::iterator first=l2.begin();
list<int>::iterator last=l2.end();
if(*it==){
// l1.splice(it,l2);
l1.splice(it,l2,first,last);
} for(auto i:l1) cout<<i<<' ';//0 1 2 11 12 13 14 3 4 5
cout<<endl; l1.reverse();
for(auto i:l1) cout<<i<<' ';//5 4 3 14 13 12 11 2 1 0
cout<<endl; l1.sort();
for(auto i:l1) cout<<i<<' ';//0 1 2 3 4 5 11 12 13 14
cout<<endl;
return ;
}

splice

public:
// take x Join in position Before
void splice(iterator position,list& x){
if(!x.empty()){
transfer(position,x.begin(),x.end());
}
}
// take i The element in question is joined to position Before the position indicated ,position and i Can point to the same list
void splice(iterator position, list&, iterator i){
iterator j=i;
++j;
if(position==i||position==j) return;
transfer(position,i,j);
}
// take [first,last] All the elements in are joined to position Before the position indicated
//position and [first,last] Can point to the same list
//position Can't be in [first,last] within
void splice(iterator position, list&, iterator first,iterator last){
if(last!=first){
transfer(position,first,last);
}
}

merge

//merge() take x Merge into *this On the body , Two list All of the content must be sorted incrementally 
template<class T,class Alloc>
void list<T,Alloc>::merge(list<T,Alloc>& x){
iterator first1=begin();
iterator last1=end();
iterator first2=x.begin();
iterator last2=x.end(); // Be careful : The premise is that both linked lists are sorted incrementally
while(first1!=last1&&first2!=last2){
if(*first2<*first1){
iterator next=first2;
tranfer(first1,first2,++next);
first2=next;
}
else
++first1;
if(first2!=last2)
transfer(last1,first2,last2);
}
}

 reverse

//reverse() Content inversion 
template<class T,class Alloc>
void list<T,Alloc>::reverse(){
// The following judgment : If there is an empty list or only one element , We don't do anything
// Use size()==0||size()==1 To judge , Although it can be , But it's slower
if(node->next==node||link_type(node->next)->next==node)
return;
iterator first=begin();
++first;
while(first!=end()){
iterator old=first;
++first;
transfer(begin(),old,first);
}
}

sort

//list Out of commission STL Algorithm sort(), You have to use your own member functions sort()
// This function uses quicksort( The code doesn't seem to be fast , It's merging
template<class T,class Alloc>
void list<T,Alloc>::sort(){
// The following judgment : If there is an empty list or only one element , We don't do anything
// Use size()==0||size()==1 To judge , Although it can be , But it's slower
if(node->next==node||link_type(node->next)->next==node)
return;
// new list As a secondary data store
list<T,Alloc> carry;
list<T,Alloc> counter[];
int fill=;
while(!empty()){
carray.splice(carry.begin(),*this,begin());
int i=;
while(i<fill&&!counter[i].empty()){
counter[i].merge(carray);
carray.swap(counter[i++]);
}
carray.swap(counter[i]);
if(i==fill)
++fill;
}
for(int i=;i<fill;++i){
counter[i].merge(counter[i-]);
}
swap(counter[fill-]);
}

Let's explain sort The implementation of the , With 21,45,1,30,52,3,58,47,22,59,0,58 For example :

1、counter[0]:21      notes :counter[i] Deposit 2i+1 Number , When you reach the third 2i+1 Number of hours , Move data to counter[i+1] in

2、counter[0]:21,45 notes :counter[0] The elements are full

counter0]:NULL

counter[1]:21,45

3、counter[0]:1

  counter[1]:21,45

4、counter[0]:1,30 notes :counter[0] The elements are full , utilize merge Merge counter[0] to counter[1]

  counter[1]:21,45

counter[0]:NULL

counter[1]:1,30,21,45 notes :counter[1] The elements are full ,

counter[0]:NULL

counter[1]:NULL

counter[2]:1,30,21,45

......

Finally get :

  counter[0]:58

counter[1]:0,59

counter[2]:NULL

  counter[3]:1,3,21,30,47,45,52,58

Merge again and get the final result .

Reference address :https://blog.csdn.net/shoulinjun/article/details/19501811

list Source code 4( Reference resources STL Source code -- Hou Jie ):transfer、splice、merge、reverse、sort More articles about

  1. list Source code 1( Reference resources STL Source code -- Hou Jie ):list node 、 iterator 、 data structure

    list Source code 1( Reference resources STL Source code -- Hou Jie ):list node . iterator . data structure list Source code 2( Reference resources STL Source code -- Hou Jie ):constructor.push_back.insert list Source code 3( Reference resources STL ...

  2. list Source code 2( Reference resources STL Source code -- Hou Jie ):constructor、push_back、insert

    list Source code 1( Reference resources STL Source code -- Hou Jie ):list node . iterator . data structure list Source code 2( Reference resources STL Source code -- Hou Jie ):constructor.push_back.insert list Source code 3( Reference resources STL ...

  3. list Source code 3( Reference resources STL Source code -- Hou Jie ):push_front、push_back、erase、pop_front、pop_back、clear、remove、unique

    list Source code 1( Reference resources STL Source code -- Hou Jie ):list node . iterator . data structure list Source code 2( Reference resources STL Source code -- Hou Jie ):constructor.push_back.insert list Source code 3( Reference resources STL ...

  4. vector Source code 3( Reference resources STL Source code -- Hou Jie ):pop_back、erase、clear、insert

    vector Source code 1( Reference resources STL Source code -- Hou Jie ) vector Source code 2( Reference resources STL Source code -- Hou Jie ): Space allocation .push_back vector Source code ( Reference resources STL Source code -- Hou Jie )----- Space allocation causes iterators to fail v ...

  5. vector Source code 2( Reference resources STL Source code -- Hou Jie ): Space allocation 、push_back

    vector Source code 1( Reference resources STL Source code -- Hou Jie ) vector Source code 2( Reference resources STL Source code -- Hou Jie ) vector Source code ( Reference resources STL Source code -- Hou Jie )----- Space allocation causes iterators to fail vector Source code 3( Reference resources STL Source ...

  6. vector Source code 1( Reference resources STL Source code -- Hou Jie ): Source code

    vector Source code 1( Reference resources STL Source code -- Hou Jie ) vector Source code 2( Reference resources STL Source code -- Hou Jie ) vector Source code ( Reference resources STL Source code -- Hou Jie )----- Space allocation causes iterators to fail vector Source code 3( Reference resources STL Source ...

  7. vector Source code ( Reference resources STL Source code -- Hou Jie ): Space allocation causes iterators to fail

    vector Source code 1( Reference resources STL Source code -- Hou Jie ) vector Source code 2( Reference resources STL Source code -- Hou Jie ) vector Source code ( Reference resources STL Source code -- Hou Jie )----- Space allocation causes iterators to fail vector Source code 3( Reference resources STL Source ...

  8. STL Source code analysis (SGI edition , By Hou Jie )

    Preface Before source code , No secret algorithm Importance The importance of efficiency use Cygnus C++ 2.91 for windows cygwin-b20.1-full2.exe Download address :http://d ...

  9. STL Source code reading -functor And adapter

    Why use a functor Function pointers are inflexible , Difficult to STL Use with other components Adapter Will a class Interface to another class The interface of , Make it impossible to cooperate due to interface incompatibility classes, Can work together STL in ...

Random recommendation

  1. BZOJ 4390: [Usaco2015 dec]Max Flow

    4390: [Usaco2015 dec]Max Flow Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 177  Solved: 113[Submi ...

  2. js Judge mobile access PC Jump to the mobile station

    <script type="text/javascript">(function() { // Get the domain suffix var path = location.pathname.s ...

  3. .NET Foundation open source projects

      .NET Compiler Platform ("Roslyn") .NET Core 5 .NET Micro Framework .NET SDK For Hadoop A ...

  4. WPF Histogram ( Support database dynamic update ) The data dynamic of the component

    WPF Histogram ( Support database dynamic update ) In this article, we show you how to package a histogram as a component , Open the attribute of the component to the outside world, bind the external attribute root and internal attribute of the component, and update the data dynamically without polling . I don't think the introduction of non polling update data is enough ...

  5. A very simple one jQuery Plug in instance tutorial ( Rookie level )

    Many front-end designers and developers are girls , And there are a lot of these girls JavaScript Skills are not very good . In the front-end development process ,JavaScript Skills are essential . therefore , If the front end is small MM For a JavaScript effect ...

  6. VR Panoramic join in - Panoramic smart city with thousands of entrepreneurs BAT

    In the end of the so-called Internet thinking . Wearable devices are basically a flash in the pan , A lot of Internet people switch to war VR market , Naturally, I like to think in terms of Internet thinking . I know some investors , When it comes to investment , They often ask the following questions :2B still 2C? How much in the future ...

  7. C++ Primer Plus 6 Chapter one

    One . machine language . assembly language .C\C++. High-level language machine language : Machines really recognize , A language that runs on a machine . assembly language : Low level language , Direct operation of hardware , Such as direct access cpu Registers and memory units . No portability . Because different platforms correspond to different hardware ...

  8. JavaScript Yes json Operation notes

    JSON Is a lightweight data exchange format , meanwhile ,JSON yes JavaScript Native format , So we can deal with it directly without relying on any toolkit or plug-in . therefore , Many backstage users will choose this very friendly data format to return to the front end . Introduction ...

  9. js Encountered the same... In an object in key The corresponding value Value addition

    Pictured : become : js Here's how it works : var abc=[ {typeid:1,ade:1}, {typeid:2,ade:1}, {typeid:1,ade:2}, {typeid:1,ade:2}, {t ...

  10. kernel ipc Mechanism

    Kernel version :linux2.6.22.6 Hardware platform :JZ2440 Driver source code  block_ipc_poll_key_int_drv.c : #include <linux/module.h> # ...