2016-02-09 70 views
0
#include <iostream> 
#include <set> 
#include <tuple> 

struct Key { 
    int field1; 
    int field2; 

    Key(int field1, int field2) : field1(field1), field2(field2) {} 

    bool operator<(const Key& other) const { 
    // Is this acceptable?! Seems to work 
    if (field2 == 0 || other.field2 == 0) { 
     return field1 < other.field1; 
    } else { 
     return std::tie(field1, field2) < std::tie(other.field1, other.field2); 
    } 
    } 
}; 

int main() { 
    std::set<Key> values{Key(4,3), Key(5,9), Key(5,7), Key(5,8), Key(6,1)}; 
    std::cout << values.find(Key(5,0))->field2 << std::endl; // Prints '7' 
    auto range = values.equal_range(Key(5,0)); 
    for (auto i = range.first; i != range.second; i++) { 
     std::cout << i->field2; // Prints '789' 
    } 
    return 0; 
} 

Field2在我的數據中並不總是可用,所以有時我使用通配符值0,它可以匹配field1匹配的任何值。如果我從不插入具有通配符值的元素,並且只能在集合中查找它們,那麼這在C++中是否有效?我很滿意find函數在這種情況下返回的任何值,這在我的代碼中很少發生,儘管希望它在重複調用時會是相同的值。嚴格的弱排序和std :: set/std :: map

根據specification,binary_search似乎不需要嚴格的弱排序,它應該是執行查找時在數據結構上使用的唯一算法,對嗎?還是有一些我不應該擔心的不確定行爲?

25.4排序和相關業務

...對於比25.4.3中描述的其他算法正常工作 ,補償具有誘導上的值了嚴格的弱序...

25.4.3二進制搜索

回答

1

你錯了。 std::set::find在二叉搜索樹中進行查找(在典型實現中)。這看起來像二分搜索算法,但是25.4.3中的算法通常不用於查找。樹只支持非隨機訪問迭代器,使用線性迭代器的二進制搜索比使用數據在BST中的知識的查找慢得多。

std::set的比較器必須符合Compare概念,該概念確實需要strict weak ordering

如果我從不插入具有通配符值的元素,並且只能在集合中查找它們,這在C++中是否有效?

技術上不行,因爲你打破了要求。從包含{x, a}{x, b}的集合中查找{x, 0}時,至少您會得到不確定的結果。要麼可以找到。如果那不重要,那麼我懷疑典型的實施會帶來麻煩。你所做的不能保證按標準工作,這對於大多數人來說已經足夠迴避了。