c++ - STL集查找性能

Question

如何覆盖 MyNode 类内部的 operator() 以便 set::find 可以使用，以及存储 MyNode* 的集合。然后我尝试在集合中找到指针，其数据字段与给定对象中的相同。下面的代码没有像我预期的那样工作。我在操作符方法中设置断点，但没有停止。

我知道我可以在 MyNode 类之外定义 find struct compare{}，然后定义集合，例如: 套套这对我来说没问题。在这里我想知道是否可以在 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 如下:

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

这个复杂度是 O(N) 还是 O(log N)？

Answer 1

至于第一个问题:std::set不关心operator()() ;它关心 operator<() .

关于你的第二个问题: std::find 算法，不像 std::set<T>::find方法，是 O(n)。