std :: unordered_map :: tìm cách sử dụng loại khác với loại Khóa?

Question

Tôi có một unordered_map có sử dụng một chuỗi kiểu như một chìa khóa:

std::unordered_map<string, value> map; 

Một chuyên std::hash được cung cấp cho string, cũng như một phù hợp operator==.

Bây giờ tôi cũng có một "chuỗi view" class, mà là một con trỏ yếu thành một chuỗi hiện có, tránh phân bổ đống:

class string_view { 
    string *data; 
    size_t begin, len; 
    // ... 
}; 

Bây giờ tôi muốn để có thể kiểm tra xem một chìa khóa tồn tại trên bản đồ bằng cách sử dụng đối tượng string_view. Thật không may, std::unordered_map::find có một đối số Key, không phải là đối số chung T.

(Chắc chắn, tôi có thể "thúc đẩy" một đến một string, nhưng điều đó gây ra sự phân bổ Tôi muốn tránh.)

Những gì tôi sẽ đã thích thay vì là một cái gì đó giống như

template<class Key, class Value> 
class unordered_map 
{ 
    template<class T> iterator find(const T &t); 
}; 

sẽ yêu cầu operator==(T, Key) và std::hash<T>() để được xác định phù hợp và sẽ trả về một trình lặp cho một giá trị phù hợp.

Có cách giải quyết nào không?

Answer 1

Bạn có thể cho phép bạn xem được ngầm chuyển đổi thành một std::string:

class StringView { 
    // ... 
    operator std::string() const 
    { 
     return data->substr(begin, len); 
    } 
    // ... 
}; 

Answer 2

Dường như chỉ là thời gian gần đây như C++ 14 thậm chí cơ bản map có được một phát templated như vậy cho is_transparent loại trong so sánh. Nhiều khả năng việc triển khai chính xác đối với các vùng chứa được băm không hiển nhiên ngay lập tức.

Theo như tôi có thể thấy hai tùy chọn của bạn là:

• Chỉ cần làm việc phân bổ và hồ sơ để xem nếu có thể nó không thực sự là một vấn đề.
• Hãy xem boost::multi_index (http://www.boost.org/doc/libs/1_60_0/libs/multi_index/doc/index.html) và có cả chỉ mục string và string_view vào vùng chứa.

Answer 3

Như đã đề cập ở trên, C++ 14 không cung cấp tra cứu không đồng nhất cho std::unordered_map (không giống như std::map). Bạn có thể sử dụng Boost.MultiIndex để xác định một sự thay thế khá chặt chẽ cho std::unordered_map cho phép bạn nhìn lên string_view s mà không phân bổ tạm thời std::string s:

Live Coliru Demo

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/hashed_index.hpp> 
#include <boost/multi_index/member.hpp> 
#include <string> 

using namespace boost::multi_index; 

struct string_view 
{ 
    std::string *data; 
    std::size_t begin,len; 
}; 

template<typename T,typename Q> 
struct mutable_pair 
{ 
    T   first; 
    mutable Q second; 
}; 

struct string_view_hash 
{ 
    std::size_t operator()(const string_view& v)const 
    { 
    return boost::hash_range(
     v.data->begin()+v.begin,v.data->begin()+v.begin+v.len); 
    } 
    std::size_t operator()(const std::string& s)const 
    { 
    return boost::hash_range(s.begin(),s.end()); 
    } 
}; 

struct string_view_equal_to 
{ 
    std::size_t operator()(const std::string& s1,const std::string& s2)const 
    { 
    return s1==s2; 
    } 
    std::size_t operator()(const std::string& s1,const string_view& v2)const 
    { 
    return s1.size()==v2.len&& 
      std::equal(
       s1.begin(),s1.end(), 
       v2.data->begin()+v2.begin); 
    } 
    std::size_t operator()(const string_view& v1,const std::string& s2)const 
    { 
    return v1.len==s2.size()&& 
      std::equal(
       v1.data->begin()+v1.begin,v1.data->begin()+v1.begin+v1.len, 
       s2.begin()); 
    } 
}; 

template<typename Q> 
using unordered_string_map=multi_index_container< 
    mutable_pair<std::string,Q>, 
    indexed_by< 
    hashed_unique< 
     member< 
     mutable_pair<std::string,Q>, 
     std::string, 
     &mutable_pair<std::string,Q>::first 
     >, 
     string_view_hash, 
     string_view_equal_to 
    > 
    > 
>; 

#include <iostream> 

int main() 
{ 
    unordered_string_map<int> m={{"hello",0},{"boost",1},{"bye",2}}; 

    std::string str="helloboost"; 
    auto it=m.find(string_view{&str,5,5}); 
    std::cout<<it->first<<","<<it->second<<"\n"; 
} 

Output

boost,1 

Answer 4

này giải pháp có drawba cks, có thể hoặc không thể làm cho nó không đáng tin cậy cho bối cảnh của bạn.

Bạn có thể tạo một lớp wrapper:

struct str_wrapper { 
    const char* start, end; 
}; 

Và thay đổi bản đồ của bạn để sử dụng str_wrapper như chìa khóa của nó. Bạn sẽ phải thêm 2 constructors vào str_wrapper, một cho std :: string và một cho string_view của bạn. Quyết định chính là liệu các nhà thầu này có thực hiện các bản sao sâu hay nông. Ví dụ, nếu bạn sử dụng std :: string chỉ cho chèn và str_view chỉ cho tra cứu, bạn sẽ làm cho std :: string constructor sâu và str_view one cạn (điều này có thể được thi hành tại thời gian biên dịch nếu bạn sử dụng một trình bao bọc tùy chỉnh xung quanh unordered_map). Nếu bạn quan tâm để tránh rò rỉ bộ nhớ trên bản sao sâu, bạn sẽ cần thêm các lĩnh vực để hỗ trợ phá hủy thích hợp.

Nếu việc sử dụng của bạn đa dạng hơn, (nhìn lên std :: chuỗi hoặc chèn bởi str_view), sẽ có những hạn chế, một lần nữa, có thể làm cho cách tiếp cận quá khó chịu để không còn tồn tại. Nó phụ thuộc vào mục đích sử dụng của bạn.