2014-04-04 26 views
10

Thường được hiểu rằng cách tốt nhất để xóa hoàn toàn các mục mong muốn từ một số std::vectorerase-remove idiom.STL "xóa-loại bỏ" thành ngữ: Tại sao không "thay đổi kích thước-loại bỏ"?

Như đã nêu trong các liên kết ở trên (kể từ ngày niêm yết này), trong mã erase-loại bỏ ngữ trông như thế này:

int main() 
{ 
    // initialises a vector that holds the numbers from 0-9. 
    std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 

    // erase-remove idiom to completely eliminate the desired items from the vector 
    v.erase(std::remove(std::begin(v), std::end(v), 5), std::end(v)); 
} 

Tôi muốn biết liệu một thành ngữ resize-remove là tương đương về chức năng và hiệu suất cho thành ngữ erase-remove. Hoặc, có lẽ tôi đang thiếu một cái gì đó hiển nhiên?

Sau đây là resize-remove thành ngữ tương đương với thành phần trên erase-remove?

int main() 
{ 
    std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 

    // Is this "resize-remove" approach equivalent to the "erase-remove" idiom? 
    v.resize(std::remove(std::begin(v), std::end(v), 5) - v.begin()); 
} 
+5

"thay đổi kích thước" là - theo định nghĩa - không phải là "thành ngữ" vì cụm từ không được người khác sử dụng ... –

+0

@TonyD Đó là một lý do rất mạnh để thích thành phần xóa-xóa . –

Trả lời

10

Theo tôi, có hai lý do:

  1. std::remove thuật toán đòi hỏi chỉ Forward Iterator, nhưng - op yêu cầu Iterator truy cập ngẫu nhiên.

  2. Kết quả của std::remove có nghĩa là "đầu mới của vùng chứa". Về mặt logic, chúng ta nên xóa ["đầu cuối của vùng chứa", "đầu cuối của vùng chứa").

+3

Đầu tiên là một điểm rất tốt (mặc dù nó không ảnh hưởng đến 'std :: vector'). –

1

Tôi nghĩ erase trong erase(first,last) đảm bảo rằng không có yếu tố trước khi first được truy cập hoặc sửa đổi, trong khi resize chỉ đảm bảo này khi không có phân bổ lại xảy ra vì sự thay đổi kích thước.

Chỉnh sửa: như chỉ ra bởi những người khác, việc phân bổ lại như vậy sẽ không bao giờ xảy ra, vì vậy không có sự khác biệt

+1

Đảm bảo rằng việc thay đổi kích thước thành kích thước nhỏ hơn không phân bổ lại. –

+1

Rõ ràng hơn: 'thay đổi kích cỡ' được định nghĩa theo thuật ngữ' xóa' và 'chèn'.Vì vậy, khi nó xóa, nó có cùng sự bảo đảm như 'xóa '. –

5

Tương đương với std :: vector, nhưng không tương ứng với std :: list hoặc các vùng chứa khác. Không chắc chắn nếu trừ các iterator thậm chí có thể cho std :: list, và thậm chí nếu nó là, nó là một hoạt động O (N).

+1

Không thể. Bạn sẽ phải sử dụng 'std :: distance', là O (N). –

+0

Sau đó, một lần nữa, nó là O (N) trong các yếu tố để loại bỏ, cộng với nó sẽ mang lại những yếu tố vào bộ nhớ cache. Vì vậy, thực tế nó không phải là khủng khiếp. – MSalters

+0

@MSalters: Đó là cách khác. Nó là O (N) trong các phần tử KHÔNG được loại bỏ. Sự phức tạp tổng thể của thành ngữ sẽ không thay đổi, bởi vì 'std :: remove()' đã là O (N), nhưng trong thực tế các hằng số cũng quan trọng. –

2

Nó không tạo nên sự khác biệt nào; resize được xác định theo điều khoản của inserterase. Nhưng thường là thích hợp hơn khi sử dụng thành ngữ tiêu chuẩn để có thể dễ dàng nhận ra nó. Và của khóa học , thành phần xóa-xóa sẽ hoạt động với bất kỳ chuỗi nào vùng chứa và không chỉ những gói hỗ trợ resize. (Tất cả các các container tiêu chuẩn dường như để hỗ trợ resize, nhưng nó dường như không có một yêu cầu. Vì vậy, nó có thể không có sẵn trên người dùng định nghĩa container, mặc dù họ hỗ trợ tất cả hoạt động cần thiết.)

Xét về hiệu suất: resize phải thực hiện thêm kiểm tra, để xác định xem nó đang xóa hoặc chèn, nhưng Tôi không thể tưởng tượng điều này tạo ra tác động đáng kể.

+0

'resize' trên danh sách' std ::' có thêm hạn chế là nó phải tìm đầu mới của danh sách, bằng cách lặp O (n), trong khi đó trình kết thúc chính xác được trả về bởi 'remove' đã bị vứt bỏ sau tính toán 'X-begin(), một lần nữa là O (n). –

+0

@ArneMertz: 'std :: list' là hai chiều (liên kết kép). Nó khá rẻ để tìm ra kết thúc mới: bạn chỉ cần bật kết thúc hiện tại cho đến khi kích thước phù hợp. Đầu mới là tiền thân của phần tử xuất hiện cuối cùng. – MSalters

+0

@ArneMertz Tôi đã tự hỏi về điều đó. Tôi đã không mong đợi để thậm chí tìm thấy nó, bởi vì nó không thể được thực hiện hiệu quả. (Và tất nhiên, bạn không thể thực hiện khác nhau của các trình vòng lặp trực tiếp nếu chúng không phải là truy cập ngẫu nhiên.) –

Các vấn đề liên quan