使用标准 C++ 库向量作为基础实现创建一个 Set 模板 class

Question

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

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

//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

//also, how do i check for duplicates?

与theSet.find()...

iterator(Set& ss,bool):s(ss){} //???

那是行不通的。许多选项，最简单的是也将 index 设置为 s.theSet.size()，这样现有的 != 就可以工作了。

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

不...您需要 return 一个 T& 到 - 而不是 copy - vector 的元素。

operator++ / operator++(int)

您需要递增迭代器（即 index），而不是递增迭代器地址，并且应该 return *this（使用 return 类型 iterator&).研究一些迭代器实现....

iterator end() { return iterator (*this,true); } //why?

为什么什么？无论如何，您最好提供 begin() 和 end() 的 const 版本 return const_iterator s（这与 iterator 非常相似，但是仅公开 const T&)，以及非 const 版本 returning iterators：您将这两个想法与 iterator begin() const.

Answer 2

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

类似

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

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

完成上述操作后，您就有了工作 Set<T>。用一堆数据对 std::set<T> 进行测试。编写一堆单元测试以确保此 Set<T> 在重复、排序、查找等方面与 std::set<T> 一样工作

现在让您的 Set<T> 更有效率。将 Find 替换为对 lower_bound 和 < 的调用，并将元素插入到它应该位于的位置，而不是先插入再排序。（没关系，这对你来说毫无意义；在阅读这篇文章之前得到一个工作 Set，然后花一些时间打开它）。

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

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

但是在正确之后再努力工作

使用标准 C++ 库向量作为基础实现创建一个 Set 模板 class

create a Set template class using the Standard C++ Library vector as an underlying implementation

c++

generics

templates

iterator

set