楼上的，你永远都不会明白我强调用链表的真实用意。

你不懂算法。

难得理你这种表达不清楚的题目。我不用懂算法，做项目，不管是分布式，还是图形方面。只要拿来用就可以。
算法，已经不重要了。要的是对象组合封装就可以。

即使最强的虚幻引擎的内存管理代码，也是偶而看一下，懂得其中意思就行。

至于你懂什么，你自己就去懂吧。 最强的人给你。

如果你到了算法不重要的地步了。

那你真的是不重要了。

#include<iostream>
#include<cstdlib>
#include<utility>
#include<cassert>
using std::pair;
template<class Type>
class List
{
public:
    struct Node{
        Type val;
        Node():pre(this),next(this){}
        Node(Type key):pre(this),next(this)
            {
                val=key;
            }
        Node(Node &node)
            {
                this->val=node.val;
            }
        Node &operator=(Node & node)
            {
                this->val=node.val;
            }
        ~Node()
            {

            }
        friend std::ostream & operator<<(std::ostream &os,Node &node)
            {
                os<<node.val<<" ";
                return os;
            }
        Node* pre;
        Node* next;
    };
    typedef Node* iter;
    List()
        {
            tail=new Node();
        }
    virtual ~List(){
        destroy();
        assert( tail->next==tail);
        delete tail;
    }
    std::size_t size();
    virtual void insert(Type key);
    virtual void erase(iter it);
    iter begin(){ return tail->next;}
    iter end(){ return tail;}
    void walk();
protected:
    void swap(Node  &n1,Node &n2)
        {
            Node tmp=n1;
            n1=n2;
            n2=tmp;
        }
    void destroy();
private:
    iter tail;
};

template<class Type>
void List<Type>::insert(Type key)
{
    if( NULL==tail )
    {
        tail=new Node(key);
        tail->pre=tail;
        tail->next=tail;
    }
    else
    {
        iter it=new Node(key);
        it->pre=tail->pre;
        it->pre->next=it;
        it->next=tail;
        it->next->pre=it;
    }
}
template<class Type>
void List<Type>::erase(iter it)
{
    it->pre->next=it->next;
    it->next->pre=it->pre;
    delete it;
}
template<class Type>
std::size_t List<Type>::size()
{
    if( tail==tail->next)
        return 0;
    else
    {
        std::size_t sz=0;
        for(iter it=begin();it!=end();it=it->next)
        {
            sz++;
        }
        return sz;
    }
}
template<class Type>
void List<Type>::walk()
{
    iter it=tail;
    if( NULL != tail)
    {
        for(it=tail->next;it!=tail;it=it->next)
        {
            std::cout<<*it<<" ";
        }
        std::cout<<std::endl;
    }
}
template<class Type>
void List<Type>::destroy()
{
    for(List<Type>::iter it=begin();it !=end();it=it->next)
    {
        erase(it);
    }
}
template<class Type>
class Rank:public List<Type>{
public:
    Rank():List<Type>(){}
    void qsort()
        {
            sort(1,List<Type>::size(),List<Type>::begin(),(List<Type>::end())->pre);
        }
    typename List<Type>::Node * _rank_k(int k);
    ~Rank(){}
protected:
    pair<typename List<Type>::Node*,int> 
    partition(int p,int r,typename List<Type>::Node * pt,typename List<Type>::Node* rt)
        {
            Type x=rt->val;
            int i=p-1,j;
            typename List<Type>::Node* it;
            typename List<Type>::Node* jt;
            it=pt->pre;
            jt=pt;
            for(j=p;j<r;j++)
            {
                if(jt->val<=x)
                {
                    i=i+1;
                    it=it->next;
                    swap(*it,*jt);
                }
                jt=jt->next;
            }
            swap(*(it->next),*rt);
            return std::make_pair(it->next,i+1);
        }
    void sort(int p,int r,typename List<Type>::Node* pt,typename List<Type>::Node* rt)
        {
            if( p< r )
            {
                pair<typename List<Type>::Node*,int> qt;
                qt=partition(p,r,pt,rt);
                sort(p,qt.second-1,pt,qt.first->pre);
                sort(qt.second+1,r,qt.first->next,rt);
            }
        }
    typename List<Type>::Node* select(int p,int r,int i,typename List<Type>::Node* pt,typename List<Type>::Node* rt);
}; 
template<class Type>
typename List<Type>::Node * Rank<Type>::_rank_k(int k)
{
    assert(k+1<=List<Type>::size() &&k+1>0);
    return select(1,List<Type>::size(),k+1,List<Type>::begin(),List<Type>::end());
}
template<class Type>
typename List<Type>::Node* 
Rank<Type>::select(int p,int r,int i,typename List<Type>::Node*pt,typename List<Type>::Node * rt)
{
    if( p == r )
    {
        return pt;
    }
    pair<typename List<Type>::Node *,int>qt;
    qt=partition(p,r,pt,rt);
    int k=(qt.second)-p+1;
    if( i == k )
        return qt.first;
    else if( i< k)
        return select(p,qt.second-1,i,pt,qt.first->pre);
    else
        return select(qt.second+1,r,i-k,qt.first->next,rt);
}
int main()
{
    srand(time(NULL));
    Rank<int> rank;
    for(int i=0;i<10;i++)
    {
        int key=rand()%50;
        rank.insert(key);
    }
    rank.walk();
    //std::cout<<rank.size()<<std::endl;
    std::cout<<*(rank._rank_k(5))<<std::endl;
    //rank.qsort();
    //rank.walk();
    return 0;
}