Container STL nào để sử dụng?

Question

Tôi nên sử dụng loại vật chứa STL nào nếu:

1. Dữ liệu được chèn và tháo thường xuyên.
2. Dữ liệu được truy cập thường xuyên một cách ngẫu nhiên.

ví dụ: tập dữ liệu (4,10,15) nếu tôi muốn tìm số gần nhất với 9, sau đó nó phải trả lại cho tôi 10.

1. tôi chỉ lưu trữ một số nguyên.
2. Nó cần phải được sắp xếp
3. có thể đi đến 100k bộ dữ liệu

Tôi nghĩ của việc sử dụng vector, nhưng chèn vector và loại bỏ là tốn kém.

vector<int> 

Nếu tôi sử dụng danh sách, tôi sẽ phải truy cập vào phần tử O (n) trước khi tiếp cận dữ liệu.

list<int> 

Tôi đã nghĩ đến việc bằng cách sử dụng thiết vì nó sẽ là tốt nếu nó được sắp xếp, nhưng im không phải là rất chắc chắn về hiệu quả sử dụng SET

Vì vậy, tôi hy vọng ai đó có thể đưa ra một giải pháp tốt!

Answer 1

Tôi nghĩ bạn nên kiểm tra này SO bài: In which scenario do I use a particular STL container? Đối với kích thước nhỏ vector sẽ phù hợp với hầu hết các kịch bản không phụ thuộc vào những gì bạn định làm.

Biểu đồ là hướng dẫn, thực tế là thùng chứa được truy cập thường xuyên không ảnh hưởng đến lựa chọn vùng chứa, thực tế là bạn đang lưu trữ int không quan trọng trừ khi bạn quan tâm đến kích thước của vùng chứa. của các con trỏ trong một thùng chứa danh sách hoặc bản đồ quan trọng với bạn?

Việc sắp xếp được thực hiện tự động theo bản đồ nhưng việc sắp xếp một vectơ và danh sách có thể rất nhanh nếu kích thước vùng chứa đủ nhỏ để vừa với bộ nhớ.

Chèn dữ liệu được tối ưu hóa cho danh sách và bản đồ ở bất kỳ đâu trong vùng chứa, vì bản đồ bạn sẽ có được lợi ích mà nó sẽ tự sắp xếp nhưng nếu kích thước đủ nhỏ thì việc tạo một vectơ mới với mục mới có thể vẫn rất nhanh . Bạn cũng có thể muốn xem xét các bản đồ băm, bạn vẫn sẽ là tốt nhất để cấu hình mã của bạn, cố gắng để đoán thứ hai những gì là tối ưu phụ thuộc vào cách sử dụng của bạn và bạn thực sự cần phải đo lường và hồ sơ.

Bạn cũng có thể quyết định rằng số dư STL <map> là số dư đủ hoặc <set> và sử dụng các vùng chứa đó khi chúng tự động sắp xếp và xóa và tra cứu nhanh chóng nhưng có chi phí duy trì con trỏ trong mỗi mục nhập làm tăng kích thước của bộ nhớ được sử dụng so với vectơ, nếu bạn không quan tâm đến điều này thì bạn có thể xem xét các thùng chứa này.

Vẫn còn nếu nó quan trọng sau đó kiểm tra và hồ sơ và so sánh hiệu suất của mỗi container, bạn sẽ ngạc nhiên bởi cách mã sẽ thực hiện chống lại giả định của bạn.

Answer 2

Câu trả lời cho câu hỏi của bạn hoàn toàn phụ thuộc vào kích thước tập dữ liệu của bạn, khi danh sách phát triển đến kích thước lớn, thời gian cần thực hiện để chuyển đến phần tử bạn cần xóa/chèn ở mức vượt xa thời gian cần cho một vector để thực hiện xóa/chèn. Vì vậy, nếu tập dữ liệu của bạn nhỏ, hãy đi kèm với danh sách, nếu nó lớn, hãy đi kèm với vectơ.

Answer 3

Nếu nó cần phải được sắp xếp, sử dụng một cây tìm kiếm nhị phân

Answer 4

Một tập hợp đủ hiệu quả để chèn/xóa/truy cập và nó luôn được sắp xếp. Điều duy nhất cần xem xét là các mục nhập trong tập hợp là const (vì vậy thứ tự không bị hỏng), do đó, để thay đổi, bạn nên xóa, cập nhật và chèn

Answer 5

Nếu yêu cầu chỉ là hiệu suất, lựa chọn về cơ bản luôn là std::vector.

Nó tránh được nhiều phân bổ bộ nhớ của cấu trúc dữ liệu dựa trên nút (cây và danh sách), và nó khai thác địa phương không gian để truyền tải hiệu quả hơn nhiều.

Tất nhiên, chèn/xóa ở giữa vectơ yêu cầu phải di chuyển các phần tử, nhưng thậm chí hiếm khi đủ để làm cho véc tơ chậm hơn các cấu trúc dữ liệu khác.

Những lý do thực duy nhất tôi thấy việc sử dụng cấu trúc dữ liệu khác là những:

• std::map/std::set: những là tuyệt vời cho thuận tiện. Đẹp và dễ sử dụng, do đó, nếu hiệu quả tối ưu là không cần thiết, tôi sử dụng chúng khi tôi cần một container được sắp xếp, hoặc một bản đồ khóa/giá trị. (để có hiệu suất tốt nhất, một véc tơ được sắp xếp có thể thích hợp hơn)
• tất cả các vùng chứa khác: có thể hữu ích cho tính chính xác đảm bảo phiếu mua hàng khi sửa đổi: vectơ thường xuyên phân bổ lại và di chuyển nội dung của nó, làm mất hiệu lực cả hai con trỏ và iterators vào vector. Các cấu trúc dữ liệu khác cung cấp đảm bảo mạnh mẽ hơn (đối với một deque, con trỏ được đảm bảo giữ nguyên hợp lệ sau khi sau khi chèn/gỡ bỏ ở cuối, nhưng các trình vòng lặp có thể vẫn không hợp lệ. hợp lệ khi chèn/xóa)

Tất nhiên, đây chỉ là quy tắc chung.

Quy tắc chung duy nhất đúng khi hiệu suất có liên quan là "tự đánh giá chính nó". Tôi có thể cho bạn biết cách vector thường hoạt động trong nhiều trường hợp phổ biến, nhưng tôi không thể cho bạn biết cách hoạt động của nó trong mã của bạn, với trình biên dịch và thư viện chuẩn của bạn. Vì vậy, nếu bạn lo lắng về hiệu suất, hãy đo lường nó. Hãy thử các lựa chọn thay thế khác nhau và xem phương án nào nhanh hơn.