temporaries Tránh trong std :: bản đồ/std :: tra cứu unordered_map với std :: string key

Question

Xét đoạn mã sau:

std::map<std::string, int> m1; 
auto i = m1.find("foo"); 

const char* key = ... 
auto j = m1.find(key); 

này sẽ tạo ra một đối tượng std :: string tạm thời cho mỗi tra cứu bản đồ. Những cách kinh điển để tránh nó là gì?

Answer 1

Không sử dụng con trỏ; thay vào đó, hãy chuyển trực tiếp chuỗi. Sau đó, bạn có thể tận dụng lợi thế của tài liệu tham khảo:

void do_something(std::string const & key) 
{ 
    auto it = m.find(key); 
    // .... 
} 

C++ thường trở nên "chính xác hơn" bạn càng sử dụng thành ngữ của nó và không cố viết chữ C với thành ngữ đó.

Answer 2

Vâng, bản đồ find thực sự chấp nhận tham chiếu không đổi đối với khóa, vì vậy bạn không thể tránh tạo tài liệu này tại điểm này hay điểm khác.

Đối với phần đầu tiên của mã, bạn có thể có hằng số tĩnh std :: string with value "foo" để tra cứu. Bằng cách đó bạn sẽ không tạo bản sao.

Nếu bạn muốn đi theo cách của Spartan, bạn luôn có thể tạo loại của riêng bạn có thể được sử dụng như một chuỗi, nhưng cũng có thể giữ con trỏ đến chuỗi ký tự chuỗi.

Nhưng trong mọi trường hợp, chi phí liên quan đến tra cứu bản đồ quá lớn nên điều này không thực sự hợp lý. Nếu tôi là bạn, tôi sẽ thay thế bản đồ/unordered_map bằng băm dày đặc của google. Sau đó, tôi sẽ chạy VTune của Intel (bộ khuếch đại những ngày này) và xem nơi mà thời gian là đi và tối ưu hóa những nơi đó. Tôi nghi ngờ dây như chìa khóa sẽ hiển thị tại một danh sách top 10 nút cổ chai.

Answer 3

Hãy xem lớp StringRef từ llvm.

Chúng có thể được xây dựng rất rẻ từ c-strings, string literals hoặc std :: string. Nếu bạn tạo một bản đồ của những người đó, thay vì std :: string, việc xây dựng sẽ rất nhanh.

Đó là một hệ thống rất mong manh. Bạn cần phải chắc chắn rằng bất kỳ nguồn gốc của các chuỗi bạn chèn vẫn còn sống và chưa sửa đổi cho suốt đời của bản đồ.

Answer 4

Bạn có thể tránh tạm thời bằng cách cung cấp lớp so sánh tùy chỉnh std::map, có thể so sánh char * s. (Giá trị mặc định sẽ sử dụng địa chỉ của con trỏ, mà không phải là những gì bạn muốn Bạn cần phải so sánh về giá trị của chuỗi..)

Do đó, một cái gì đó như:

class StrCmp 
{ 
public: 
    bool operator() (const char *a, const char *b) 
    { 
    return strcmp(a, b) < 0; 
    } 
}; 

// Later: 
std::map<const char *, int, StrCmp> m; 

Sau đó, sử dụng giống như một bản đồ bình thường , nhưng vượt qua char * 's. Lưu ý rằng bất cứ điều gì bạn lưu trữ trong bản đồ phải còn hoạt động trong thời gian của bản đồ. Điều đó có nghĩa là bạn cần char literals, hoặc bạn phải giữ dữ liệu được trỏ đến bởi con trỏ còn sống trên của riêng bạn. Vì những lý do này, tôi sẽ đi với một số std::map<std::string> và ăn tạm thời cho đến khi hồ sơ cho thấy rằng ở trên là thực sự cần thiết.

Answer 5

Không có cách nào để tránh một phiên bản std::string tạm thời sao chép dữ liệu ký tự. Lưu ý rằng chi phí này rất thấp và không phải phân bổ bộ nhớ động nếu việc triển khai thư viện chuẩn của bạn sử dụng tối ưu hóa chuỗi ngắn.

Tuy nhiên, nếu bạn cần chuỗi proxy kiểu C thường xuyên, bạn vẫn có thể đưa ra các giải pháp tùy chỉnh sẽ vượt qua phân bổ này.Điều này có thể trả hết nếu bạn phải thực hiện điều này thực sự thường xuyên và các chuỗi của bạn đủ dài để không được hưởng lợi từ tối ưu hóa chuỗi ngắn.

Nếu bạn chỉ cần rất tập con nhỏ của chức năng chuỗi (ví dụ: chỉ gán và sao chép), thì bạn có thể viết một chuỗi chuỗi mục đích đặc biệt nhỏ lưu trữ con trỏ const char * và chức năng giải phóng bộ nhớ.

class cheap_string 
{ 
public: 
    typedef void(*Free)(const char*); 
private: 
    const char * myData; 
    std::size_t mySize; 
    Free myFree; 
public: 
    // direct member assignments, use with care. 
    cheap_string (const char * data, std::size_t size, Free free); 

    // releases using custom deleter (a no-op for proxies). 
    ~cheap_string(); 

    // create real copies (safety first). 
    cheap_string (const cheap_string&); 
    cheap_string& operator= (const cheap_string&); 
    cheap_string (const char * data); 
    cheap_string (const char * data, std::size_t size) 
     : myData(new char[size+1]), mySize(size), myFree(&destroy) 
    { 
     strcpy(myData, data); 
     myData[mySize] = '\0'; 
    } 

    const char * data() const; 
    const std::size_t size() const; 

    // whatever string functionality you need. 
    bool operator< (const cheap_string&) const; 
    bool operator== (const cheap_string&) const; 

    // create proxies for existing character buffers. 
    static const cheap_string proxy (const char * data) 
    { 
      return cheap_string(data, strlen(data), &abandon); 
    } 

    static const cheap_string proxy (const char * data, std::size_t size) 
    { 
      return cheap_string(data, size, &abandon); 
    } 

private: 
    // deleter for proxies (no-op) 
    static void abandon (const char * data) 
    { 
     // no-op, this is used for proxies, which don't own the data! 
    } 

    // deleter for copies (delete[]). 
    static void destroy (const char * data) 
    { 
     delete [] data; 
    } 
}; 

Sau đó, bạn có thể sử dụng lớp này như:

std::map<cheap_string, int> m1; 
auto i = m1.find(cheap_string::proxy("foo")); 

Các tạm cheap_string dụ không tạo ra một bản sao của bộ đệm nhân vật như std::string không, nhưng nó bảo ngữ nghĩa bản sao an toàn để lưu trữ các trường hợp cheap_string trong các thùng chứa tiêu chuẩn.

ghi chú: nếu thực hiện của bạn không sử dụng tối ưu hóa giá trị trả về, bạn sẽ muốn tìm một cú pháp thay thế cho phương pháp proxy, chẳng hạn như một nhà xây dựng với một tình trạng quá tải đặc biệt (dùng một kiểu tùy chỉnh proxy_t à la std::nothrow cho vị trí mới).