STL 之 list源码自行实现（iterator）

首页 > 代码库 > STL 之 list源码自行实现（iterator）

STL 之 list源码自行实现（iterator）

2024-09-21 04:40:19 216人阅读

（0）文件夹

STL 之 vector源码实现(云算法<< [] = 重载, new delete,throw catch)

STL c++中string类的源码

堆（stack）之 c 和 c++模板实现（空类默认成员函数初谈引用内联函数）

第一次实现list模板（幼稚的我）

浅析STL 谓词 + 仿函数 + 函数指针(c)

队列（queue) 之 c++模板实现（友元函数和运算符重载）

STL 之初识set multiset（map multimap）

C++map类型之简单介绍

c++ string 之 find_first of 实现（更改篇）

泛型算法 —— 独立于容器的算法

初识迭代器 C++ Iterator

哈希（hash) 之插入和查找（链地址法）

c++ fstream + string 处理大数据（与c 的fread）

c++中的悬浮指针和野指针

二级指针

一：起因（參考）

（1）数据结构里面两种很重要的存储结构，线性结构中的连续存储结构（代表vector数组）和非连续存储结构（代表list链表），他们两者被广泛的应用在

各个领域。是最基本最基础的两种存储结构。

（2）vector 已经简单的实现了，请看STL 之 vector的实现之前还实现了STL的string类，请看 STL 之 string 的实现

（3）之前的友元类仅仅是停留在理论层面，真正实现还是头一次。（尽管友元函数，无数次的实现过了）这个友元类正是 Iterator 类，也是初次实现

Iterator。见识了Iterator ++ --运算符的重载，注意只实现了单一方向的++ --（这是源码这样处理的）。友元类很像java中的内部类。

。

（4）我也幼稚过，请看第一次实现list模板

（5）list 自己也是结合STL的源码，结合数据结构简单的实现的。里面可能有一些处理不当，请大神们指正，谢谢。

二：list实现

（1）list的分析

List是一种可在常数时间内在不论什么位置运行插入和删除操作的顺序容器。

list是双向链表。其迭代器是双向的。与其它顺序容器(array, vector, deque)相比。list

容器在任何位置运行插入、提取、和移动元素的操作更高效，但它不能通过在容器中的位置直接获取元素。

（2）list中的一些主要函数（注意。自己只实现了一部分）

Operations

list::splice() ———— 将一个list A中的元素转移到list B的指定位置。并将A中被转移的元素删除。

list::remove() ———— 将list中指定的元素删除。

list::unique() ———— 删除list中具有同样值的元素，仅仅保留第一个。也能够依据条件删除具有同样条件的元素，仅仅保留第一个。

list::merge() ———— 合并两个list。在合并之前两个list应该先排序，合并之后的list依旧有序。

也能够自己定义排序的条件。

list::sort() ———— 对list中的元素进行排序，变更它们在容器中的位置。sort()还能够按给定条件进行排序。

list::reverse() ——_ 改变list中元素的顺序。

（3）list的实现

a 构造函数 MyList(const MyList<T>& list0)

template<class T>
MyList<T>::MyList(const MyList<T>& list0)
{
    size = list0.size;
    node *cur0 = list0.head;
    node *tp = new node;
    tp->data = http://www.mamicode.com/cur0->data;>b  +=重载（注意自加）


// MyList 的+= 感觉能够改进的，别两个while了
        MyList<T>& operator += (const MyList<T>& list)
        {
            if(list.head == (*this).head)
            {// meichuli
                //cout << "****" << endl;
                MyList<T> other(list);
                //cout << "&&&&&" << endl;
                return *this += other;
            }
            if(NULL == list.head)// list 空串
                return *this;
            node *cur = list.head;
            node *tp = new node;
            tp->data = http://www.mamicode.com/cur->data;>

c  友元类（内部类）


//Iterator class
    class MyIterator
    {
        friend class MyList<T>;
        protected:
            node* Iter;
            MyIterator(node *iter)
            {
                Iter = iter;
            }
        public:
            MyIterator(){}
            // 先加上
            MyIterator& operator ++()
            {
                Iter = Iter->next;
                return *this;
            }
            // 先减去
            MyIterator& operator --()
            {
                Iter = Iter->last;
                return *this;
            }
            MyIterator& operator = (MyIterator& it)
            {
                Iter = it.Iter;
                return *this;
            }
            bool operator ==(const MyIterator& iter)
            {
                return Iter==iter.Iter?true:false;
            }
            bool operator !=(const MyIterator& iter)
            {
                return Iter!=iter.Iter?true:false;
            }
            T operator *()
            {
                return Iter->data;
            }
            MyIterator &operator[](int n)
            {
                for(int i=0;i<n;i++)
                {
                    assert(NULL!=Iter);
                    Iter=Iter->next;
                }
                return *this;
            }
            MyIterator &operator +(int n)
            {
                for(int i=0;i<n;i++)
                {
                    assert(NULL!=Iter);
                    Iter=Iter->next;
                }
                return *this;
            }
    };// MyIterator 内部类


d  字符串反转


// reverse 对于同一个串进行交换。
。
template<class T>
void MyList<T>::reserve(MyIterator& it1,MyIterator& it2)
{
    node *le = it1.Iter;
    node *ri = it1.Iter;
    int c = 1;
    // 不是非常理解的
    for(;ri!=it2.Iter;ri=ri->next)
    {
        c++;
    }
    for(;c>1;c-=2)
    {
        // 值交换，指针交换？？
        le->data ^= ri->data;
        ri->data ^= le->data;
        le->data ^= ri->data;
        le = le->next;
        ri = ri->last;
    }
}e   移除指定元素


// remove value
template<class T>
void MyList<T>::remove(T val)
{
    node *tp = head;
    for(;tp!=NULL;)
    {
        if(tp->data=http://www.mamicode.com/=val)>

（4）完整代码例如以下：MyList.h


#ifndef MYLIST_H_INCLUDED
#define MYLIST_H_INCLUDED
#include <iostream>
#include <cassert>
#include <cstdio>
#include <string>
using namespace std;

template<class T>
class MyList
{
    friend class MyIterator;
    protected:
        struct node
        {
            T data;
            node *next;
            node *last;
        };
    private:
        node *head;
        node *rear;
        int size;
    public:
    //constructor
        MyList();
        MyList(const MyList<T>&);
        MyList(T,int);
        MyList(T);
    //disconstructor
        ~MyList(){this->clear();}
    //Iterator class
    class MyIterator
    {
        friend class MyList<T>;
        protected:
            node* Iter;
            MyIterator(node *iter)
            {
                Iter = iter;
            }
        public:
            MyIterator(){}
            // 先加上
            MyIterator& operator ++()
            {
                Iter = Iter->next;
                return *this;
            }
            // 先减去
            MyIterator& operator --()
            {
                Iter = Iter->last;
                return *this;
            }
            MyIterator& operator = (MyIterator& it)
            {
                Iter = it.Iter;
                return *this;
            }
            bool operator ==(const MyIterator& iter)
            {
                return Iter==iter.Iter?
true:false;
            }
            bool operator !=(const MyIterator& iter)
            {
                return Iter!=iter.Iter?true:false;
            }
            T operator *()
            {
                return Iter->data;
            }
            MyIterator &operator[](int n)
            {
                for(int i=0;i<n;i++)
                {
                    assert(NULL!=Iter);
                    Iter=Iter->next;
                }
                return *this;
            }
            MyIterator &operator +(int n)
            {
                for(int i=0;i<n;i++)
                {
                    assert(NULL!=Iter);
                    Iter=Iter->next;
                }
                return *this;
            }
    };// MyIterator 内部类

   // public:// 功能函数
        MyList<T> sublist(MyIterator&,MyIterator&);
        MyList<T> sublist(MyIterator&,int);
        MyList<T> sublist(MyIterator&);
        void push_back(const T);
        void push_front(const T);
        void pop_back();
        void pop_front();
        void clear();
        void reserve();
        void reserve(MyIterator&,MyIterator&);
        void replace(T,T);
        void swap(MyList<T>&);
        void display();
        void display_rear();
        void insert(MyIterator&,T);
        void f_insert(MyIterator&,T);
        void remove(T);
        bool exist(T);
        bool up_order();
        bool down_order();
        int get_size(){return size;}
        // swap 值
        friend void swap(MyIterator& it1,MyIterator& it2)
        {
            (it1.Iter)->data ^= (it2.Iter)->data;
            (it2.Iter)->data ^= (it1.Iter)->data;
            (it1.Iter)->data ^= (it2.Iter)->data;
        }
        // erase 当前的it,返回it->next
        MyIterator erase(MyIterator& it)
        {
            assert(0 != size);
            size--;
            if(0 == size)
            {
                head = NULL;
                rear = NULL;
                return MyIterator(NULL);
            }
            if(it.Iter == head)
            {
                node *tp = head;
                head = head->next;
                head->last = NULL;
                delete(tp);
                return MyIterator(head);
            }
            if(it.Iter == rear)
            {
                node *tp = rear;
                rear = rear->last;
                rear->next = NULL;
                delete(tp);
                return MyIterator(NULL);
            }
            (it.Iter)->last->next = (it.Iter)->next;
            (it.Iter)->next->last = (it.Iter)->last;
            node *ans = it.Iter->next;
            delete(it.Iter);
            return MyIterator(ans);// 返回结果
        }
        // find 返回ter指针
        MyIterator find(T val)
        {
            node *tp = head;
            for(;tp!=NULL;tp=tp->next)
            {
                if((tp->data)==val) return MyIterator(tp);
            }
            return MyIterator(NULL);
        }
        MyIterator begin(){return MyIterator(head);}
        MyIterator end(){return MyIterator(rear);}
        T& front(){return head->data;}
        T& back(){return rear->data;}
        bool empty(){return 0==size?true:false;}
        void link(MyList<T>& list0){*this += list0;}
        void reset(MyIterator& it,T val){(it.Iter)->data = http://www.mamicode.com/val;}"****" << endl;
                MyList<T> other(list);
                //cout << "&&&&&" << endl;
                return *this += other;
            }
            if(NULL == list.head)// list 空串
                return *this;
            node *cur = list.head;
            node *tp = new node;
            tp->data = http://www.mamicode.com/cur->data;" ";
    }
    cout << *(iter) << endl;// 输出end end是rear
}
// display_rear
template<class T>
void MyList<T>::display_rear()
{
    if(NULL==this->rear)
    {
        cout << ‘\0‘ << endl;
        return;
    }
    MyList<T>::MyIterator iter = this->end();
    for(;iter!=this->begin();--iter)
    {
        cout << *(iter) << " ";
    }
    cout << *(iter) << endl;// begin()
}
// push_back
template<class T>
void MyList<T>::push_back(const T val)
{
    node *tp = new node;
    tp->data = http://www.mamicode.com/val;>
。
template<class T>
void MyList<T>::reserve(MyIterator& it1,MyIterator& it2)
{
    node *le = it1.Iter;
    node *ri = it1.Iter;
    int c = 1;
    // 不是非常理解的
    for(;ri!=it2.Iter;ri=ri->next)
    {
        c++;
    }
    for(;c>1;c-=2)
    {
        // 值交换，指针交换？？
        le->data ^= ri->data;
        ri->data ^= le->data;
        le->data ^= ri->data;
        le = le->next;
        ri = ri->last;
    }
}
// replace
template<class T>
void MyList<T>::replace(T val1,T val2)
{
    node *tp = head;
    while(tp!=NULL)
    {
        if(tp->data=http://www.mamicode.com/=val1)>


(5) 測试韩式main


#include "MyList.h"

using namespace std;
int main()
{
    MyList<string> list0;
    MyList<string> list7("ccc",3);
    list0 += list7;
    list0.display_rear();
    string tmp = "aaa";
    list0.push_back(tmp);
    list0.push_front("bbbb");

    list7.display();
    list0 += list0;
    list0.display_rear();
    cout << "1: " << list0.get_size() << " ," <<  endl;
    //MyList<string> list1(tmp);
    list0.clear();
    //list1.display();
    //list1.clear();
    //list1.display();
    MyList<int> list1(5,4);
    list1.push_back(1111);
    MyList<int>::MyIterator it = list1.begin();
    //++it;
    list1.insert(it+2,2222);
    list1.f_insert(it,555);
    //list1.push_front(5555);
    //list1.pop_back();
    //list1.pop_front();
    cout << "2: " << list1.get_size() << ", ";
    list1.display();
    MyList<int> list2(list1);
    cout << "3: " << list2.get_size() << ", ";
    list2.display();
    list2.reserve(list2.begin()+2,list2.begin()+4);
    list2.display_rear();
    MyList<int> list3(3,6);
    list3.swap(list1);
    list1.reserve();
    cout << "4: " << list1.get_size() << ",";
    list1.display();
    list1.push_back(33);
    cout << "5:" << list1[6] << ",," << list1.down_order() << list1.up_order() << endl;
    //list1.display_rear();
    MyList<int> list4= list2.sublist(list2.begin()+2,list2.begin()+4);
    list4.display();
    return 0;
}

STL 之 list源码自行实现（iterator）

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > STL 之 list源码自行实现（iterator）

STL 之 list源码自行实现（iterator）

看完仍有疑问？有类似问题直接问程序猿