Dân số biên dịch của cấu trúc dữ liệu khác với mảng?

Question

Trong C++, bạn có thể làm điều này:

static const char * [4] = { 
    "One fish", 
    "Two fish", 
    "Red fish", 
    "Blue fish" 
}; 

... và cung cấp cho bạn một mảng cấu trúc dữ liệu chỉ đọc thoải mái mà không mất bất kỳ chu kỳ CPU để khởi tạo trong thời gian chạy, bởi vì tất cả các dữ liệu đã được đặt ra cho bạn (trong các trang bộ nhớ chỉ đọc của trình thực thi) bởi trình biên dịch.

Nhưng nếu tôi muốn sử dụng cấu trúc dữ liệu khác thay vì một mảng thì sao? Ví dụ, nếu tôi muốn cấu trúc dữ liệu của tôi để có tra cứu nhanh thông qua một phím, tôi sẽ phải làm một cái gì đó như thế này:

static std::map<int, const char *> map; 

int main(int, char **) 
{ 
    map.insert(555, "One fish"); 
    map.insert(666, "Two fish"); 
    map.insert(451, "Red fish"); 
    map.insert(626, "Blue fish"); 

    [... rest of program here...] 
} 

... đó là ít thanh lịch và kém hiệu quả như các cấu trúc dữ liệu bản đồ là nhận được dân cư tại thời gian chạy, mặc dù tất cả các dữ liệu cần thiết đã được biết tại thời gian biên dịch và do đó công việc đó có thể có (về mặt lý thuyết) đã được thực hiện sau đó.

Câu hỏi của tôi là, có cách nào trong C++ (hoặc C++ 11) để tạo cấu trúc dữ liệu chỉ đọc (như bản đồ) có dữ liệu được thiết lập hoàn toàn tại thời gian biên dịch và do đó được điền trước và sẵn sàng để sử dụng tại thời gian chạy, cách một mảng có thể được?

Answer 1

Không dễ dàng, không có. Nếu bạn đã cố gắng làm ví dụ đầu tiên của mình bằng cách sử dụng malloc, rõ ràng là nó sẽ không hoạt động vào thời gian biên dịch. Vì mỗi vùng chứa tiêu chuẩn duy nhất sử dụng new (tốt, std::allocator<T>::allocate(), nhưng chúng tôi sẽ giả vờ rằng bây giờ là new), chúng tôi không thể thực hiện việc này vào lúc biên dịch.

Điều đó đã được nói, điều đó tùy thuộc vào mức độ đau đớn mà bạn sẵn sàng trải qua và số tiền bạn muốn đẩy lùi thời gian biên dịch. Bạn chắc chắn không thể làm điều này bằng cách sử dụng các tính năng thư viện chuẩn. Sử dụng boost::mpl mặt khác ...

#include <iostream> 

#include "boost/mpl/map.hpp" 
#include "boost/mpl/for_each.hpp" 
#include "boost/mpl/string.hpp" 
#include "boost/mpl/front.hpp" 
#include "boost/mpl/has_key.hpp" 

using namespace boost::mpl; 

int main() 
{ 
    typedef string<'One ', 'fish'> strone; 
    typedef string<'Two ', 'fish'> strtwo; 
    typedef string<'Red ', 'fish'> strthree; 
    typedef string<'Blue', 'fish'> strfour; 

    typedef map<pair<int_<555>, strone>, 
     pair<int_<666>, strtwo>, 
     pair<int_<451>, strthree>, 
     pair<int_<626>, strfour>> m; 

    std::cout << c_str<second<front<m>::type>::type>::value << "\n"; 
    std::cout << has_key<m, int_<666>>::type::value << "\n"; 
    std::cout << has_key<m, int_<111>>::type::value << "\n"; 
} 

Answer 2

Nếu bạn muốn bản đồ (hoặc đặt), hãy xem xét thay vì sử dụng binary tree stored as an array. Bạn có thể khẳng định rằng nó được sắp xếp đúng lúc chạy trong các bản xây dựng gỡ lỗi, nhưng trong các bản dựng tối ưu, bạn có thể giả định mọi thứ được sắp xếp đúng cách, và sau đó có thể thực hiện các hoạt động tìm kiếm nhị phân giống như trong std :: map, nhưng với lưu trữ là một mảng. Chỉ cần viết một chương trình nhỏ để heapify dữ liệu cho bạn trước khi dán nó vào chương trình của bạn.

Answer 3

Vâng, C++ 11 cho phép cú đúp initializers:

std::map<int, const char *> map = { 
    { 555, "One fish" }, 
    { 666, "Two fish" }, 
    // etc 
}; 

Answer 4

Điều đáng nói là vấn đề của bạn xuất phát từ thực tế bạn đang sử dụng bản đồ. Bản đồ thường bị lạm dụng. Giải pháp thay thế cho bản đồ là một mảng/mảng được sắp xếp. Bản đồ chỉ trở thành "tốt hơn" so với bản đồ khi được sử dụng để lưu trữ dữ liệu có độ dài không xác định hoặc (và đôi khi chỉ) khi dữ liệu thay đổi thường xuyên.

Chức năng std :: sort, std :: lower_bound/std :: upper_bound là những gì bạn cần. Nếu bạn có thể tự sắp xếp dữ liệu, bạn chỉ cần một hàm, lower_bound và dữ liệu có thể là const.