Tại sao tôi không thể xóa chuỗi khỏi std :: set with std :: remove_if?

Question

Possible Duplicate:
remove_if equivalent for std::map

Tôi có một tập hợp các chuỗi:

set <wstring> strings; 
// ... 

tôi muốn loại bỏ chuỗi theo một vị ngữ, ví dụ:

std::remove_if (strings.begin(), strings.end(), [](const wstring &s) -> bool { return s == L"matching"; }); 

Khi tôi cố gắng này, tôi nhận được biên dịch sau lỗi:

c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\algorithm(1840): error C2678: binary '=' : no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>' 

e rror dường như gợi ý rằng std::string không có một hàm tạo bản sao giá trị (sẽ là bất hợp pháp). Có phải bằng cách nào đó không tốt khi sử dụng std::remove_if với std::set? Tôi có nên làm điều gì khác thay vì một số lần lặp lại của set::find() theo sau là set::erase() không?

Answer 1

std::remove_if (hoặc std::erase) hoạt động bằng cách gán lại giá trị của các thành viên trong phạm vi. Nó không hiểu cách std::set tổ chức dữ liệu hoặc cách xóa nút khỏi cấu trúc dữ liệu cây bên trong của nó. Thật vậy, nó không thể làm như vậy bằng cách sử dụng chỉ tham chiếu đến các nút, mà không cần phải có đối tượng set.

Thuật toán chuẩn được thiết kế để có các phức tạp tính toán minh bạch (hoặc ít nhất là dễ nhớ). Một chức năng để chọn lọc loại bỏ các yếu tố từ một set sẽ là O (N log N), do sự cần thiết phải cân bằng lại cây, mà là không tốt hơn so với một vòng lặp gọi my_set.remove(). Vì vậy, tiêu chuẩn không cung cấp cho nó, và đó là những gì bạn cần phải viết.

Mặt khác, vòng lặp được mã hóa bằng tay để xóa các mục khỏi vector từng cái một sẽ là O (N^2), trong khi std::remove_if là O (N). Vì vậy, thư viện cung cấp một lợi ích hữu hình trong trường hợp đó.

Một vòng lặp điển hình (C++ 03 phong cách):

for (set_t::iterator i = my_set.begin(); i != my_set.end();) { 
    if (condition) { 
     my_set.erase(i ++); // strict C++03 
     // i = my_set.erase(i); // more modern, typically accepted as C++03 
    } else { 
     ++ i; // do not include ++ i inside for () 
    } 
} 

Chỉnh sửa (4 năm sau!): i ++ trông đáng ngờ đó. Điều gì sẽ xảy ra nếu erase vô hiệu hóa i trước khi toán tử tăng sau có thể cập nhật? Điều này là tốt, mặc dù, bởi vì nó là một quá tải operator++ chứ không phải là nhà điều hành được xây dựng trong. Hàm này cập nhật an toàn i tại chỗ và sau đó trả về bản sao giá trị ban đầu của nó.

Answer 2

Các thông báo lỗi nói

no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>'

Note const. Trình biên dịch là chính xác rằng std::wstring không có một operator= có thể được gọi trên một đối tượng const.

Tại sao chuỗi const? Câu trả lời là các giá trị trong một std::set là bất biến, bởi vì các giá trị trong một tập hợp được sắp xếp, và thay đổi một giá trị có thể thay đổi thứ tự của nó trong tập hợp, làm mất hiệu lực tập hợp.

Tại sao trình biên dịch cố gắng sao chép giá trị của tập hợp?

std::remove_if (và std::remove) không thực sự xóa bất kỳ thứ gì (cũng không phải chúng, vì chúng không có vùng chứa, chỉ có trình vòng lặp). Những gì họ làm là sao chép tất cả các giá trị trong phạm vi mà không phù hợp với tiêu chí đến đầu của dãy núi này, và trả về một iterator tới phần tử tiếp theo sau khi các yếu tố phù hợp. Sau đó, bạn được yêu cầu xóa thủ công khỏi trình lặp được trả về đến cuối phạm vi. Vì một tập hợp giữ nguyên tố của nó theo thứ tự, sẽ sai khi di chuyển bất kỳ phần tử nào xung quanh, vì vậy không thể sử dụng remove_if trên một tập hợp (hoặc bất kỳ vùng chứa liên kết nào khác).

Nói tóm lại, bạn phải sử dụng một vòng lặp của std::find_if và set::erase, như vậy:

template<class V, class P> 
void erase_if(std::set<V>& s, P p) 
{ 
    std::set<V>::iterator e = s.begin(); 
    for (;;) 
    { 
    e = std::find_if(e, s.end(), p); 
    if (e == s.end()) 
     break; 
    e = s.erase(e); 
    } 
}