Cách hiệu quả để lấy trung bình (trung bình) của một tiêu chuẩn :: set?

Question

std::set là một cây được sắp xếp. Nó cung cấp các phương thức begin và end để tôi có thể tối thiểu và tối đa và lower_bound và upper_bound để tìm kiếm nhị phân. Nhưng điều gì sẽ xảy ra nếu tôi muốn đưa trình vòng lặp trỏ đến phần tử ở giữa (hoặc một trong số chúng nếu có cả số phần tử ở đó)?

Có cách nào hiệu quả (O(log(size)) không O(size)) để làm điều đó không?

{1} => 1 
{1,2} => 1 or 2 
{1,2,3} => 2 
{1,2,3,4} => 2 or 3 (but in the same direction from middle as for {1,2}) 
{1,312,10000,14000,152333} => 10000 

PS: Same question in Russian.

Answer 1

Tùy thuộc vào mức độ thường xuyên bạn chèn/xoá các mục so với nhìn lên giữa/trung bình, một giải pháp có thể hiệu quả hơn so với cái rõ ràng là để giữ một iterator dai dẳng đến phần tử ở giữa và cập nhật nó bất cứ khi nào bạn chèn/xóa các mục khỏi tập hợp. Có một loạt các trường hợp cạnh sẽ cần xử lý (số lẻ so với số mục, loại bỏ mục giữa, bộ trống, v.v.), nhưng ý tưởng cơ bản sẽ là khi bạn chèn một mục nhỏ hơn mục giữa hiện tại , trình vòng lặp giữa của bạn có thể cần giảm dần, trong khi nếu bạn chèn một cái lớn hơn, bạn cần tăng thêm. Đó là cách khác để loại bỏ.

Tại thời điểm tra cứu, tất nhiên là O (1), nhưng cũng có chi phí O (1) tại mỗi lần chèn/xóa, tức là O (N) sau N chèn, cần được phân bổ trên một đủ số lượng tra cứu để làm cho nó hiệu quả hơn việc ép buộc.

Answer 2

Nó sẽ là O (size) để có được giữa một cây tìm kiếm nhị phân. Bạn có thể lấy nó với std::advance() như sau:

std::set<int>::iterator it = s.begin(); 
std::advance(it, s.size()/2); 

Answer 3

Nếu dữ liệu của bạn là tĩnh, những người bạn có thể precalcate nó và không chèn các yếu tố mới - đó là đơn giản hơn để sử dụng vector, sắp xếp nó, và trung bình truy cập chỉ bằng cách chỉ số trong thời gian O (1)

vector<int> data; 
// fill data 
std::sort(data.begin(), data.end()); 
auto median = data[data.size()/2];