一个简易的Set容器

刺骨的言语ヽ痛彻心扉 2022-08-23 04:59 172阅读 0赞

由于临近期末，课都上的差不多了，所以最近多了很多空闲时间来思考和写代码。今天闲的无聊，决定撸一个简易的集合容器练练手。本以为是一件挺简单的事情，可是当完成起来的时候才发现没那么容易。  
惯例：先上代码。

//head.h
    #ifndef SET_H
    #define SET_H_
    template<typename T>
    class Set {
        struct member {
            T data;
            member * next;
            member() :next(nullptr) {}
        };
        member *head;
        member *current;
    public:
        Set() :head(nullptr) {}
        struct iterator {               
            member * ptmember;
            bool operator!=(const iterator & cmp)const
            {
                if (this->ptmember == nullptr&&cmp.ptmember == nullptr)
                    return false;
                return (this != &cmp);
            }
            T operator*()
            {
                return this->ptmember->data;
            }
            void operator++()
            {
                this->ptmember = this->ptmember->next;
            }
            void operator--()
            {
                if (ptmember == head)
                    return;
                else
                {
                    current = head;
                    while (current->next != this)
                    {
                        current = current->next;
                    }
                    this->ptmember = current;
                }
            }
        }ptmemtemp;
        typename Set::iterator  begin() { ptmemtemp.ptmember = head; return ptmemtemp; }
        typename Set::iterator  end();
        void push(T x);
        bool find(T x);
        void show();
    };
    template<typename T>
    void Set<T>::push(T x)
    {
        if (head == nullptr)
        {
            current = new member;
            current->data = x;
            head = current;
        }
        else if (x < head->data)
        {
            current = new member;
            current->data = x;
            current->next = head;
            head = current;
        }
        else
        {
            current = head;
            while (current->next != nullptr)
            {
                if (current->data == x)
                    return;
                if (x < current->next->data)
                {
                    member *temp = new member;
                    temp->data = x;
                    temp->next = current->next;
                    current->next = temp;
                    return;
                }
                current = current->next;
            }
            if (current->data == x)
                return;
            member *temp=new member;
            temp->data = x;
            current->next= temp;
        }
    }
    template<typename T>
    bool Set<T>::find(T x)
    {
        current = head;
        while (current != nullptr)
        {
            if (x == current->data)
            {
                return true;
            }
            current = current->next;
        }
        return false;
    }
    template<typename T>
    void Set<T>::show()
    {
        current = head;
        while (current != nullptr)
        {
            cout << current->data << "   ";
            current = current->next;
        }
        cout << endl;
    }
    template<typename T>
    typename Set<T>::iterator Set<T>::end()
    {
        current = head;
        while (current != nullptr)
            current = current->next;
        ptmemtemp.ptmember = current;
        return ptmemtemp;
    }
    
    #endif

//test.cpp
    #include"head.h"
    #include<iostream>
    #include<cstdlib>
    #include<ctime>
    using namespace std;
    int main()
    {
        srand(time(0));
        Set<double> test;
        for (int i = 0; i < 50; ++i)
        {
            double h = rand() % 20;
            test.push(h);
        }
        test.show();
        for (Set<double>::iterator a = test.begin(); a != test.end(); ++a)
        {
            cout << *a << "   ";
        }
        int testnum;
        testnum = rand() % 20;
        cout <<endl<< "testnum is: " << testnum << endl;
        if (test.find(testnum))
            cout << "find it.\n";
        else
            cout << "not find it.\n";
    
        system("pause");
        return 0;
    }

下面就来谈谈我这次写这个容器的艰难的心路历程吧。

一开始准备实现的功能就是插入数字的时候就自动的找到合适的位置插进去（已经有了的数就不插进去了），然后就是通过类似于容器中迭代器一样的东西来遍历Set，最后重载一下！=和++以及– \*操作符。（貌似功能也不多(●’◡’●)）  
到了第二个“迭代器”这个功能的时候就比较麻烦了。一开始想直接通过member实现++和–，所以就写了友元函数来实现这个功能，结果遇到了第一道坎：![这里写图片描述][20160608010305019]  
一开始并没有看懂（原谅我见识少(●’◡’●)），请教了一位浙大学长（厚颜无耻的我冒充了浙大学生混进了浙大编程群）。然后加上了typename，因为如果不声明的话编译器并不知道这是什么东西，加上了typename之后编译器才知道这是类型名。  
然后准备重载！=。重载！=是为了比较“迭代器”是否相等，关于迭代器我一开始的想法是用member指针来实现。这时候，问题又来了。类中的成员函数和友元函数参数列表不能有指针类型的参数，但是我要传的就是指针啊！于是又厚着脸皮去群里问了问题。大神学长告诉我外包一层iterator，这样一来根本就不用友元函数了，直接在iterator中重载刚才的运算符就行了呀！！！真是excited。  
关于上面说的不能传指针，msdn上是这么说的：  
\*\*\*Compiler Error C2803  
Visual Studio 2015 Other Versions  
‘operator operator’ must have at least one formal parameter of class type  
The overloaded operator lacks a parameter of class type.  
You need to pass at least one parameter by reference (not using pointers, but references) or by value to be able to write “a < b” (a and b being of type class A).  
If both parameters are pointers it will be a pure comparison of pointer addresses and will not use the user-defined conversion.*\**

然后把++，–，\*，！=这些符号全部重载在iterator中，因为本来这些操作符就是对“迭代器”进行的呀。

最后感觉从今天写这个Set容器中学到了不少。

[20160608010305019]: /images/20220721/68fecec32854476c9abcfb64ca55a9fc.png