Tôi đang tìm một lớp chứa C++ được lập chỉ mục như một số std::vector, nhưng có chèn nhanh, xóa và lập chỉ mục. Ví dụ, một giao diện vector được thực hiện với một cây cân bằng cơ bản sẽ có các phép chèn/xóa O (logN) và lập chỉ mục O (logN).Container có chèn nhanh và chỉ mục?
Để rõ ràng: Tôi không tìm kiếm std::map<int, T>. Chèn phần tử tại chỉ mục N sẽ tăng chỉ mục của tất cả các phần tử tiếp theo trong mảng mà không phải là trường hợp với std::map<int, T>.
Tôi đã tìm thấy AVL Array làm chính xác những gì tôi đang tìm kiếm. Nó có giao diện phù hợp, nhưng tôi muốn xem nếu có các tùy chọn khác.
Bạn có biết bất kỳ triển khai nào khác (chất lượng sản xuất) không? Có lẽ một cái gì đó phổ biến hơn (không tăng có một cái gì đó của loại?). Một cái gì đó với một dấu chân bộ nhớ nhỏ hơn? (Một nút giữ con trỏ trong Mảng AVL là 64 byte trên máy của tôi.)
bạn có thể xây dựng trên lý do tại sao bạn yêu cầu truy cập ngẫu nhiên? – BeyelerStudios
Điều này dường như không có chủ đề - tìm kiếm các khuyến nghị về phần mềm/thư viện. –
Tôi không nghĩ rằng có một điều đơn giản hơn (về cấu trúc dữ liệu) làm những gì bạn muốn, vì vậy nó đòi hỏi 2 ptrs cho next/prev và 3 ptrs cho parent/left/right cộng với con trỏ ban đầu. Tổng cộng, 6 con trỏ = 48 byte cho môi trường 64 bit. Đó là ít nhất bạn có thể đạt được trong điều khoản của bộ nhớ (tôi nghĩ). – mostruash