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設置查找性能

回答

相關問題