cách tăng cường multi_index được thực hiện

Question

Tôi gặp một số khó khăn khi hiểu cách Boost.MultiIndex được triển khai. Hãy nói tôi có như sau:

typedef multi_index_container< 
    employee, 
    indexed_by<  
     ordered_unique<member<employee, std::string, &employee::name> >, 
     ordered_unique<member<employee, int, &employee::age> > 
    > 
> employee_set; 

Tôi tưởng tượng rằng tôi có một mảng, Employee[], mà thực sự lưu trữ các employee đối tượng, và hai bản đồ

map<std::string, employee*> 
map<int, employee*> 

với tên và tuổi tác như phím. Mỗi bản đồ có giá trị employee* trỏ đến đối tượng được lưu trữ trong mảng. Được không?

Answer 1

Một giải thích ngắn gọn về cấu trúc cơ bản được đưa ra here, trích dẫn dưới đây:

Việc thực hiện dựa trên các nút liên kết với nhau với con trỏ, cũng giống như nói yêu thích std::set thực hiện của bạn.Tôi sẽ xây dựng một chút về vấn đề này: Một std::set thường được thực hiện như một rb-cây nơi nút trông giống như

struct node 
{ 
    // header 
    color  c; 
    pointer parent,left,right; 
    // payload 
    value_type value; 
}; 

Vâng, Một nút multi_index_container 's cơ bản là một 'multinode' với càng nhiều tiêu đề như các chỉ số như cũng như trọng tải. Ví dụ, một multi_index_container với hai cái gọi là ra lệnh cho các chỉ số sử dụng một nút nội bộ mà trông giống như

struct node 
{ 
    // header index #0 
    color  c0; 
    pointer parent0,left0,right0; 
    // header index #1 
    color  c1; 
    pointer parent1,left1,right2; 
    // payload 
    value_type value; 
}; 

(Thực tế là phức tạp hơn, các nút được tạo ra thông qua một số lập trình meta vv nhưng bạn sẽ có được ý tưởng) [. ..]

Answer 2

Về mặt khái niệm, có.

Từ những gì tôi hiểu về Boost.MultiIndex (tôi đã sử dụng nó, nhưng không thấy triển khai), ví dụ của bạn với hai chỉ số ordered_unique thực sự sẽ tạo hai thùng chứa được liên kết đã sắp xếp (như std::map), lưu trữ con trỏ/tham chiếu/chỉ mục vào một tập hợp phổ biến là employee s.

Trong mọi trường hợp, mọi employee chỉ được lưu trữ một lần trong vùng chứa nhiều chỉ mục, trong khi kết hợp map<string,employee> và map<int,employee> sẽ lưu trữ mọi nhân viên hai lần.

Nó có thể rất tốt được rằng có thực sự là một (động) mảng bên trong một số container đa lập chỉ mục, nhưng có no guarantee rằng đây là đúng:

[chỉ số truy cập ngẫu nhiên] không cung cấp tiếp giáp bộ nhớ , thuộc tính của std::vector s theo đó các phần tử được lưu trữ bên cạnh một phần tử khác trong một khối bộ nhớ.

Ngoài ra, Boost.Bimap is based on Boost.MultiIndex và trước đây cho phép các biểu diễn khác nhau của cấu trúc "xương sống" của nó.

Answer 3

Thực ra tôi không nghĩ vậy.

Dựa trên những gì được đặt trong detail/node_type.hpp. Dường như với tôi giống như một nút std::map, nút này sẽ chứa cả giá trị và chỉ mục. Ngoại trừ trong trường hợp này các chỉ số khác nhau khác nhau và do đó nút xen kẽ sẽ thực sự khác nhau tùy thuộc vào chỉ mục bạn đang theo dõi.

Tôi không chắc chắn về điều này tuy nhiên, tăng cường tiêu đề là chắc chắn khó có thể phân tích, tuy nhiên nó sẽ có ý nghĩa nếu bạn nghĩ trong nhiệm kỳ của bộ nhớ:

• ít phân bổ: nhanh phân bổ/deallocation
• tốt hơn cache locality

Tôi sẽ đánh giá cao câu trả lời dứt khoát, nếu có ai biết về máu me.