STL设置查找性能

如何覆盖类MyNode中的operator（）以便set :: find可以使用，以及一组存储MyNode *的设置。然后我尝试在set中找到指针，其数据字段与给定对象中的相同。下面的代码不能按我的预期工作。我在运算符方法中设置了断点，但没有停止。STL设置查找性能

我明白我可以在MyNode类之外定义find struct compare {}，然后定义如下集合： set sets 这对我来说是oK。在这里我想知道是否可以在类MyNode中定义比较。

我的代码是这样的：

class MyNode { 
    std::string data; 
public: 
    MyNode(); 
MyNode(std::string str); 
MyNode(const MyNode& orig); 
virtual ~MyNode(); 

std::string getData(); 


bool operator<(const MyNode& node){ 
    return data<node.data; 
} 

bool operator<(const MyNode* node){ 
    return data<node->data; 
}

};

void testset(){ 
MyNode* node1 = new MyNode("5S"); 

MyNode* node2 = new MyNode("AH"); 
MyNode* node3 = new MyNode("AH"); 
std::cout<<" "<<node2<<std::endl; 
std::set<MyNode*> sets; 
sets.insert(node1); 
sets.insert(node2); 

std::set<MyNode*>::iterator iter =sets.find(node3); // I expected node2 can be found, but it does not.. 
if(iter != sets.end()){ 
    MyNode* no = *iter; 
    std::cout<<"find it "<<no<<std::endl; 
}

}

另一个问题是，如果我只定义设置，如：

  set<MyNode> sets. 
      std::find(sets.begin(), sets.end(), findmethod("aa"))

这是复杂度为O（N）或O（日志N）？

来源

2013-11-22 shijie xu

搜索'std :: set'中的元素是O（log N）。 –

@MarcClaesen它是？该标准要求它对于设定的尺寸是对数的。使用*算法* std :: find而不是* container *'std :: set :: find'确实是线性的，这可能就是你的意思。不确定。 – WhozCraig

@WhozCraig我的意思是'std :: set :: find'。我想我还不够具体。 –

至于第一个问题：std::set不在乎operator()();它关心的是operator<()。

至于你的第二个问题：std::find算法，不像std::set<T>::find方法，是O（n）。

来源

2013-11-22 21:36:09

我用operator <方法更新了类MyNode，但它仍然无法设置.find（）仍然无法获取node2。有什么不对吗？ sets.find（）是O（日志N）无论setname中的typename是多少，而std :: find（）是O（N） –

那么你正在存储'set '而不是'set '。如果你想用'set'来以不同的方式比较'MyNode *'，你将不得不提供你自己的自定义比较器。 – greatwolf

在类MyNode外定义一个名为MyNodeCompare的比较器，并将init设置为“set sets”works ..但是我想要的是寻求解决方案，我可以在类MyNode中定义覆盖运算符并声明集集合，以便sets.find（）可以工作.. –

STL设置查找性能

回答

相关问题