c++ - 使用标准 C++ 库 vector 作为底层实现创建一个 Set 模板类

Question

我刚刚读了一章关于模板和迭代器的内容，但这仍然很难理解。基本上我想创建一个 Set 模板类，它只接受您放入其中的每种类型的对象中的一个，使用 vector 实现。

问题是，我不知道如何在 Set 类中编写插入函数，以及在嵌套迭代器类中编写构造函数。另外，我提供的大部分功能都是文中章节的例子，我什至不知道它们是否必要或我做对了。评论？因为这是一个非常困惑的问题。这是我的代码:

//testSetClass.cpp

#include <iostream>
#include <vector>
using namespace std;

/****************************CLASS DEFINITION*********************************/

// -----------------------------------------
 //         SET
 // -----------------------------------------
template <class T>
class Set
{
    vector<T> theSet;
public:
    Set() {}
    Set(const Set& s): theSet(s.theSet){} //copy constructor
    ~Set(){ theSet.clear(); }

    void insert(T t) 
    {
        //insert in orderly fashion? as set class does too
        //also, how do i check for duplicates?
        theSet.push_back(t);
    }

    //nested iterator class: that supports the begin() and end() sentinel
    class iterator; //declaration
    friend class iterator;
    class iterator //definition
    {
        Set<T>& s;
        int index;
    public:
        iterator(const Set<T>& ss): s(ss), index(0){}
        //to create the "end sentinel" operator:
        iterator(Set<T>& ss,bool):s(ss){} //???

        T operator*() {return s.theSet.at(index);} //is this right?

        T operator++() //prefix form
        {
            return ++s.theSet.at(index);
        }
        T operator++(int) //postfix form
        {
            return s.theSet.at(index)++;
        }
        bool operator!=(const iterator& ri)const {return index!=ri.index;}
    };

    //iterators begin() and end()
    iterator begin()const { return iterator (*this); }
    //create the end sentinel:
    iterator end() { return iterator (*this,true); } //why?
};


/*************************************END OF CLASS DEFINITIONS*********************************/


/* *****************************************************************************
 *  MAIN 
 * *****************************************************************************
 *  
 *  REMARKS:
 *     to test that the class works correctly.
 * *****************************************************************************/

int main (int argv, char const *argc[])
{
    Set<int> other;


    for(int i = 0; i<10; ++i)
        other.insert(i);

    for(Set<int>::iterator start = other.begin(); start != other.end(); start++)
        cout<<*start<<endl;

    cout << "\n\nProgram ends successfully!" <<endl;
}

Answer 1

使用 std::vector<T>::iterator为你的迭代器。和你的 const_iterator 类似.

要查找，请使用 std::equal_range .如果first==second , 返回 end() .

要插入，查找。如果它已经存在，请停止。如果不存在，请插入它。偷懒的插入方式是推回，然后排序。首先以懒惰的方式进行。

完成上述操作后，您就有了一个可用的 Set<T> .针对 std::set<T> 进行测试一堆数据。编写一堆单元测试以确保这个 Set<T>就像 std::set<T> 一样工作关于重复、排序、查找等。

---

现在让你的Set<T>更高效。替换那个Find调用 lower_bound和 < , 然后将元素插入到它应该在的位置，而不是先插入再排序。 (没关系，这对您来说毫无意义；在阅读本文之前先获取一个可用的 Set，然后花一些时间打开它)。

或者，进行惰性排序 Set<T>盲目追加，并且很少在插入时按指数排序。在读取时，它要么排序，要么用二进制搜索检查排序的部分，并用线性搜索检查剩余的(小)部分。或者类似的东西。

另一个改进是编写手册 iterator像上面一样；一个不像 std::vector 那样容易失效的迭代器。这……很难做到正确。

但是在你有了正确性之后再去提高效率。