我刚刚读了一章关于模板和迭代器的内容,但这仍然很难理解。基本上我想创建一个 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;
}
最佳答案
使用 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
那样容易失效的迭代器。这……很难做到正确。
但是在你有了正确性之后再去提高效率。
关于c++ - 使用标准 C++ 库 vector 作为底层实现创建一个 Set 模板类,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32324392/