CODEWITHSUNDEEP
c++stlfindset
shijie xu
shijie xu

Reputation: 2097

STL set find performance

How to overwrite operator() inside of class MyNode so that set::find can use, and a sets that stores MyNode*. Then I try to find pointer in set, whose data field is the same as in given object. The below code does not work as I expected. I set breakpoints in of operator method, but none stopped.

I understand I can define find struct compare{} outside of class MyNode, and then define sets like: set sets This is oK for me. Here I am wondering whether it is possible I can define compare inside of class MyNode.

My code is like: 

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;   
}

}

Another question is if I only define set like: 

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

Is this complexity O(N) or O(log N)?

Upvotes: 0

Views: 2965

Answers (1)

Frerich Raabe
Frerich Raabe

Reputation: 94299

As for the first question: std::set doesn't care about operator()(); it cares about operator<().

As for your second question: the std::find algorithm, unlike the std::set<T>::find method, is O(n).

Upvotes: 2

Related Questions