Khi nào nên chọn std :: vector over std :: map cho dữ liệu khóa-giá trị?

Question

Xem xét hiệu ứng tích cực của bộ nhớ đệm và vị trí dữ liệu khi tìm kiếm trong bộ nhớ chính, tôi có xu hướng sử dụng std::vector<> với std::pair<> như các mục có giá trị khóa và thực hiện tìm kiếm tuyến tính cho cả hai, nếu tôi biết tổng số mục có giá trị không bao giờ là "quá lớn" để ảnh hưởng nghiêm trọng đến hiệu suất. Gần đây tôi đã có rất nhiều tình huống mà tôi biết trước rằng tôi sẽ có số lượng lớn các mục có giá trị khóa và do đó đã chọn số std::map<> ngay từ đầu.

Tôi muốn biết cách bạn đưa ra quyết định cho vùng chứa thích hợp trong các tình huống như các trường hợp được mô tả ở trên.

Bạn

• luôn luôn sử dụng std::vector<> (hoặc tương tự)?
• luôn sử dụng std::map<> (hoặc tương tự)?
• có cảm giác đường ruột cho vị trí trong phạm vi số mục thích hợp hơn đối tượng khác?
• điều gì đó hoàn toàn khác?

Cảm ơn!

Answer 1

Tôi hiếm khi sử dụng std::vector với tìm kiếm tuyến tính (ngoại trừ kết hợp với tìm kiếm nhị phân như được mô tả bên dưới). Tôi cho rằng lượng dữ liệu đủ nhỏ sẽ tốt hơn, nhưng với ít dữ liệu đó thì không có gì là sẽ mang lại lợi thế lớn.

Tùy thuộc vào mẫu sử dụng, tìm kiếm nhị phân trên std::vector có thể có ý nghĩa. A std::map hoạt động tốt khi bạn cần cập nhật dữ liệu thường xuyên trong quá trình sử dụng.Tuy nhiên, trong một vài trường hợp, bạn tải lên một số dữ liệu và sau đó bạn sử dụng dữ liệu - nhưng sau khi bạn đã tải dữ liệu, nó hầu như vẫn tĩnh (tức là nó thay đổi rất ít, nếu có).

Trong trường hợp này, có thể có nhiều ý nghĩa khi tải dữ liệu vào vectơ, sắp xếp dữ liệu nếu cần và sau đó thực hiện tìm kiếm nhị phân trên dữ liệu (ví dụ: std::lower_bound, std::equal_range). Điều này mang lại hiệu quả tốt nhất cho cả hai thế giới - tìm kiếm nhị phân độ phức tạp thấp và sử dụng bộ nhớ cache tốt từ địa phương cao tham chiếu (ví dụ: vectơ liền kề với cấu trúc liên kết của std::map). Điều thiếu sót, tất nhiên, là chèn và xóa chậm - nhưng đây là một lần tôi đã sử dụng ý tưởng ban đầu của bạn - lưu trữ dữ liệu mới được chèn riêng cho đến khi nó đạt đến giới hạn, và chỉ sau đó sắp xếp nó với phần còn lại của dữ liệu, do đó, một tìm kiếm duy nhất bao gồm tìm kiếm nhị phân của phần chính của dữ liệu, theo sau là tìm kiếm tuyến tính (số lượng nhỏ) dữ liệu mới được chèn vào.

Answer 2

Tôi sẽ không bao giờ lựa chọn duy nhất trên (có thể không có thật) "hiệu quả" căn cứ, nhưng luôn luôn trên những gì tôi thực sự sẽ làm gì với container. Tôi có muốn lưu trữ các bản sao không? Thứ tự chèn có quan trọng không? Thỉnh thoảng tôi có muốn tìm kiếm giá trị không phải là chìa khóa không? Những thứ đó.

Answer 3

Tôi hầu như luôn thích sử dụng bản đồ (hoặc unordered_map, khi một thùng chứa có ý nghĩa hơn) so với một véc-tơ.

Điều đó đang được nói, tôi nghĩ lý do của bạn là ngược. Tôi sẽ có xu hướng sử dụng một véc tơ chỉ khi có lượng dữ liệu khổng lồ, vì vectơ sẽ là dấu chân bộ nhớ nhỏ hơn.

Với đúng loại bộ dữ liệu, bạn có thể tải một véc tơ rồi sắp xếp nó và binary_search bằng dấu chân nhỏ hơn và các đặc tính hiệu suất tương tự cho bản đồ, đặc biệt nếu tập dữ liệu ổn định sau khi tải.

Answer 4

Bạn đã cân nhắc sử dụng cấu trúc dữ liệu đã sắp xếp chưa? Họ có xu hướng cung cấp các tìm kiếm logarit và chèn - một sự cân bằng hợp lý. Cá nhân tôi không có bất kỳ quy tắc cứng và nhanh nào khác ngoài việc thích các bản đồ cho khả năng quan trọng trên giá trị dễ đọc/dễ đọc của con người.

Tất nhiên có rất nhiều cuộc thảo luận về hiệu quả của bản đồ so với danh sách/vectơ (sắp xếp và chưa phân loại) - nếu khóa của bạn là chuỗi có 10.000 ký tự, có thể mất nhiều thời gian hơn để so sánh chuỗi so với tìm kiếm thông qua danh sách chỉ một vài mục, vì vậy bạn muốn đảm bảo rằng bạn cũng có thể so sánh các khóa một cách hiệu quả.

Answer 5

Tại sao bạn không dùng unordered_map vào tài khoản?