Ở đây http://www.cplusplus.com/reference/stl/set/ Tôi đọc rằng std :: đặt trong C++ là "thường" được triển khai dưới dạng cây (màu đỏ-đen?) Và nó được sắp xếp.Lệnh std :: set iteration có luôn tăng dần theo đặc tả C++ không?
Tôi không thể hiểu, có nghĩa là theo đặc điểm kỹ thuật thứ tự lặp lại của bộ luôn tăng dần? Hay nó chỉ là "chi tiết thực hiện thông thường" và đôi khi, một số thư viện/trình biên dịch có thể vi phạm quy ước này?
Theo tiêu chuẩn C++, phép lặp qua các phần tử trong một khoản tiền std::set được tiến hành theo thứ tự sắp xếp được xác định bởi std::less hoặc theo đối số mẫu biến vị ngữ so sánh tùy chọn.
(Cũng theo chuẩn C++, chèn, tra cứu và xóa mất ít nhất O (lg n) thời gian, cây tìm kiếm để cân bằng hiện nay là sự lựa chọn thực hiện duy nhất khả thi cho std::set, mặc dù việc sử dụng các màu đỏ-đen cây không được bắt buộc theo tiêu chuẩn.)
bởi đặc điểm kỹ thuật lặp thứ tự của bộ luôn ascending
Vâng, các giá trị của bộ luôn tăng dần nếu bạn in chúng ra theo thứ tự. Như mô tả cho biết, nó thường được thực hiện bằng cách sử dụng Red-Black Tree (RBT), nhưng các nhà văn biên dịch có tùy chọn để vi phạm điều này, nhưng thường sẽ dính vào Chủ đề của RBT vì bất kỳ triển khai nào khác sẽ không được tài nguyên hiệu quả để đạt được nhiệm vụ của set.
Trình so sánh mặc định ít hơn, do đó, tập hợp sẽ được sắp xếp theo thứ tự tăng dần. Để thay đổi điều này, bạn có thể chỉ định một trình so sánh hiện tại hoặc tùy chỉnh khác làm đối số mẫu.
Điều này có nghĩa là nội bộ std::set sẽ lưu trữ các phần tử của nó dưới dạng cây được sắp xếp. Tuy nhiên, đặc điểm kỹ thuật không nói gì về thứ tự sắp xếp. Theo mặc định, std::set sử dụng std::less và do đó sẽ đặt hàng từ thấp đến cao. Tuy nhiên, bạn có thể làm cho chức năng phân loại được bất cứ điều gì bạn muốn, sử dụng constructor này:
std::set<valueType, comparissonStruct> myCustomOrderedSet;
Vì vậy, ví dụ:
std::set<int, std::greater<int> > myInverseSortedSet;
hoặc
struct cmpStruct {
bool operator() (int const & lhs, int const & rhs) const
{
return lhs > rhs;
}
};
std::set<int, cmpStruct > myInverseSortedSet;
Trong thực tế, những ví dụ này cũng là được cung cấp trên trang web bạn đã liên kết. Cụ thể hơn ở đây: set constructor.
C++ 11 N3337 dự thảo tiêu chuẩnhttp://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf
23.2.4 "container Associative" nói:
1 container Associative cung cấp thu hồi nhanh chóng các dữ liệu dựa trên các phím. Thư viện cung cấp bốn loại cơ bản của các vùng chứa liên kết: thiết lập, nhiều bộ, ánh xạ và đa chiều.
và:
10 Thuộc tính cơ bản của vòng lặp của container kết hợp là họ lặp qua các container theo thứ tự không giảm dần các phím mà không giảm dần được xác định bởi sự so sánh đó là được sử dụng để xây dựng chúng.
nên có, trật tự được bảo đảm bằng C++ chuẩn, mà như https://stackoverflow.com/a/11812871/895245 đề cập về cơ bản đòi hỏi một cân bằng thực hiện cây tìm kiếm.
Tương phản với C++ 11 unordered_set, có thể mang lại hiệu suất tốt hơn vì nó có ít hạn chế hơn: Why on earth would anyone use set instead of unordered_set? ví dụ: sử dụng bộ băm.