Tôi đang học STL ngay bây giờ. Tôi đọc khoảng set vùng chứa. Tôi có câu hỏi khi bạn muốn sử dụng set? Sau khi đọc description of set, có vẻ như nó vô dụng vì chúng ta có thể thay thế nó bằng vector. Bạn có thể nói ưu và cos cho vector so với set vùng chứa. Cảm ơnSự khác nhau giữa std :: set và std :: vector là gì?
A set được đặt hàng. Đó là đảm bảo để duy trì theo thứ tự cụ thể, theo một functor mà bạn cung cấp. Không có vấn đề gì bạn thêm hoặc loại bỏ các yếu tố (trừ khi bạn thêm một bản sao, mà không được phép trong một set), nó sẽ luôn luôn được đặt hàng.
A vector có chính xác và chỉ thứ tự bạn đã cung cấp một cách rõ ràng. Các mục trong một vector là nơi bạn đặt chúng. Nếu bạn đặt chúng ra ngoài trật tự, chúng sẽ không còn trật tự; bây giờ bạn cần phải sort vùng chứa để đặt chúng trở lại theo thứ tự.
Phải thừa nhận rằng, set có mức sử dụng tương đối hạn chế. Với kỷ luật thích hợp, người ta có thể chèn các vật phẩm vào một vector và giữ nó theo thứ tự. Tuy nhiên, nếu bạn liên tục chèn và xóa các mục khỏi vùng chứa, vector sẽ gặp nhiều sự cố. Nó sẽ làm rất nhiều việc sao chép/di chuyển các phần tử và vân vân, vì nó chỉ là một mảng.
Thời gian cần để chèn một mục vào vector là tỷ lệ thuận với số lượng mục đã có trong vector. Thời gian cần để chèn một mục vào một số set tỷ lệ thuận với số log₂ của số lượng mục. Nếu số lượng các mục lớn, đó là một sự khác biệt rất lớn. log₂ (100.000) là ~ 16; đó là một cải tiến tốc độ lớn. Cũng vậy để loại bỏ.
Tuy nhiên, nếu bạn thực hiện tất cả các lần chèn của mình cùng một lúc, lúc khởi tạo thì không có vấn đề gì. Bạn có thể chèn mọi thứ vào vector, sắp xếp nó (trả giá đó một lần), và sau đó sử dụng các thuật toán chuẩn để sắp xếp vectors để tìm các phần tử và lặp qua danh sách được sắp xếp. Và trong khi lặp lại các thành phần của một số set không chính xác là chậm, việc lặp lại trên vector nhanh hơn.
Vì vậy, có những trường hợp được sắp xếp vector đánh bại set. Điều đó đang được nói, bạn thực sự không nên bận tâm với chi phí của loại tối ưu hóa này trừ khi bạn biết rằng nó là cần thiết. Vì vậy, hãy sử dụng set trừ khi bạn có kinh nghiệm với loại hệ thống bạn đang viết (và do đó biết rằng bạn cần hiệu suất đó) hoặc có dữ liệu lược tả trong tay cho bạn biết rằng bạn cần vector và không phải là set.
Nhưng không phải là 'set' được đặt hàng chỉ là một chi tiết thực hiện? Về mặt toán học, một bộ không có thứ tự. –
@PaulManta: Một 'std :: set' không được định nghĩa bởi toán học; nó được định nghĩa bởi đặc tả C++. Và đặc điểm kỹ thuật nói rằng nó được đặt hàng. –
@NicolBolas: Tại sao "Thời gian cần để chèn một mục vào vectơ là tỷ lệ thuận với số lượng các mục đã có trong vectơ". ? - Bạn có nghĩa là sử dụng insert() luôn luôn và chèn không ở cuối? Bạn không thể sử dụng push_back() và thêm nó vào O (1)? đặc biệt là kể từ khi người dùng kiểm soát thứ tự. –
Chúng là những thứ khác nhau: bạn quyết định cách các véc tơ được sắp xếp, và bạn cũng có thể đặt nhiều thứ bằng nhau vào một véc tơ như bạn muốn. Bộ được sắp xếp theo quy tắc nội bộ của bộ đó (bạn có thể đặt các quy tắc, nhưng bộ sẽ xử lý thứ tự) và bạn không thể đặt nhiều mục bằng nhau vào một bộ.
Tất nhiên bạn có thể duy trì một vectơ các mục duy nhất, nhưng hiệu suất của bạn sẽ bị ảnh hưởng rất nhiều khi bạn thực hiện các hoạt động định hướng. Ví dụ, giả sử rằng bạn có một tập hợp 10000 mục và một vectơ của 10000 mục không theo thứ tự riêng biệt. Bây giờ giả sử rằng bạn cần kiểm tra xem một giá trị X có nằm trong số các giá trị trong tập hợp (hoặc trong số các giá trị trong vectơ) hay không. Khi X không nằm trong số các mục, việc tìm kiếm véc tơ sẽ chậm hơn 100 lần. Bạn sẽ thấy sự khác biệt về hiệu suất tương tự khi tính toán công đoàn và giao lộ.
Để tóm tắt, các bộ và vectơ có các mục đích khác nhau. Bạn có thể sử dụng một véc tơ thay vì một bộ, nhưng nó sẽ đòi hỏi nhiều công việc hơn, và có khả năng sẽ làm tổn thương hiệu suất khá nghiêm trọng.
+1 cho tính độc đáo. tôi không thể tin rằng không ai khác bận tâm để chỉ ra điều này. vì xấu hổ! tính duy nhất là lợi ích chính. và không làm giảm giá trị đó, nhưng ngay cả sự dễ dàng của 'erase' /' emplace'.often cũng khiến tôi sử dụng '[unordered_] set', ngay cả khi nó có thể về lý thuyết chậm hơn - mặc dù thường ở các phần thiết lập mà tốc độ không mối quan tâm và tôi chỉ lo lắng về việc hầu như không thể đọc được mã sau! ví dụ.tôi muốn đảm bảo một mục được đặt trong container, nhưng chỉ một lần; nó có vẻ đẹp hơn rất nhiều khi viết 'set.emplace (it)' hơn 'if (vec.find (it)! = vec.end()) {vec.emplace (it)}' (và còn nhiều hơn nữa cho 'erase'!) –
tìm kiếm một mục nhanh hơn một tập hợp so với một véc tơ (O (log (n)) so với O (n)). Để tìm kiếm một mục chống lại một vectơ, bạn cần phải lặp lại tất cả các mục trong vectơ, nhưng tập hợp sử dụng cây đỏ-đen để tối ưu hóa tìm kiếm, chỉ một vài mục sẽ được tìm để tìm một kết quả phù hợp.
Bộ này được đặt hàng, điều đó có nghĩa là bạn chỉ có thể lặp lại từ bộ nhỏ nhất đến lớn nhất theo thứ tự hoặc thứ tự được đảo ngược.
Nhưng véc tơ không có thứ tự, bạn có thể di chuyển nó theo thứ tự chèn.
dạng cpluplus.com thiết lập:
Sets là container lưu trữ các yếu tố độc đáo sau một thứ tự cụ thể.
nên tập được ra lệnh VÀ mục được biểu diễn duy nhất
khi vect:
Vectors là container chuỗi đại diện cho mảng có thể thay đổi kích thước .
nên vector là theo thứ tự bạn điền vào nó và có thể chứa nhiều mục giống hệt nhau
thích thiết lập:
thích vector:
Vì bạn đọc về bộ, cũng đọc bản đồ. Sau đó thử so sánh lại! –
[Chọn vùng chứa của bạn cẩn thận] (https://docs.google.com/open?id=0B_ZAqgwpqtF4MjQ5NmNlM2ItNTQxNS00MmEyLWFiODctNDk4YTY5MDRlYzQz) –
@NicolBolas Tôi đã chỉnh sửa liên kết. bạn đã làm cho tôi làm một số công việc phụ mặc dù: D –