如何設置性病針式:: binary_search

Question

我有以下簡單的程序，將binary_search一個項目：

#include <vector> 
#include <algorithm> 
#include <string> 
#include <iostream> 

class Record 
{ 
public: 
    Record() = default; 
    Record(std::string name, int data) : mName(name), mData(data) { } 
    std::string mName; 
    int mData = 0; 
}; 

int main(int, char**) 
{ 
    std::vector<Record> recs; 

    recs.emplace_back(Record("1", 1)); 
    recs.emplace_back(Record("55555", 2)); 
    recs.emplace_back(Record("333", 3)); 
    recs.emplace_back(Record("qwertyuiop", 4)); 
    recs.emplace_back(Record("22", 5)); 
    recs.emplace_back(Record("4444", 6)); 

    std::cout << "Unsorted:" << std::endl; 
    for (auto& rec : recs) 
    { 
     std::cout << "Name: " << rec.mName << " Data: " << rec.mData << std::endl; 
    } 
    std::cout << std::endl; 

    std::stable_sort(recs.begin(), recs.end(), [](const Record& lhs, const Record& rhs) -> bool 
    { 
     return lhs.mName.length() < rhs.mName.length(); 
    }); 

    std::cout << "Sorted:" << std::endl; 
    for (auto& rec : recs) 
    { 
     std::cout << "Name: " << rec.mName << " Data: " << rec.mData << std::endl; 
    } 
    std::cout << std::endl; 

    if (std::binary_search(
     recs.begin(), 
     recs.end(), 
     Record("qwertyuiop", 4), 
     [](const Record& lhs, const Record& rhs) -> bool 
    { 
     return lhs.mName < rhs.mName; 
    })) 
    { 
     std::cout << "Found" << std::endl; 
    } 
    else 
    { 
     std::cout << "Not found" << std::endl; 
    } 


    return 0; 
} 

如何搜索記錄的基礎上另一種類型T的載體？例如std :: string而不是Record？

喜歡的東西：

if (std::binary_search(
      recs.begin(), 
      recs.end(), 
      "qwertyuiop", 
      [](const Record& lhs, const std::string& rhs) -> bool 
     { 
      return lhs.mName < rhs.mName; 
     })) 
     { 
      std::cout << "Found" << std::endl; 
     } 
     else 
     { 
      std::cout << "Not found" << std::endl; 
     } 

就是我想要的 - 基本上我並不想構建一個記錄，以尋找它，因爲這提出了一個性能問題對我來說。

Answer 1

您可以創建一個處理異構比較的函數對象類型：

struct comp_t 
{ 
    bool operator()(Record const& lhs, std::string const& rhs) const { 
     return lhs.mName < rhs; 
    } 

    bool operator()(std::string const& lhs, Record const& rhs) const { 
     return lhs < rhs.mName; 
    } 
}; 

然後就可以調用binary_search這樣的：

std::binary_search(recs.begin(), recs.end(), 
        std::string("qwertyuiop"), 
        comp_t{}) 

Answer 2

您可以通過添加implicit構造函數std::string轉換爲Record和操作員Record轉換爲std::string做到這一點。

operator std::string() const { 
    return mName; 
} 

Record(std::string name) : mName(name), mData(int()) {} 

，或者您可以將現有的構造轉換爲該

Record(std::string name, int data = int()) : mName(name), mData(data) {} 

但不管怎麼說，你需要創建一個std::string對象進行搜索。

/// create std::string object from "qwertyuiop" 
if (std::binary_search(recs.begin(), recs.end(), std::string("qwertyuiop"), 
    [](const Record & lhs, const std::string & rhs) -> bool 
     { 
      return lhs.mName < rhs; /// rhs is a std::string type 
     })) { 
    std::cout << "Found" << std::endl; 
} 
else { 
    std::cout << "Not found" << std::endl; 
} 

請參閱http://ideone.com/0f16GE演示。