C++ cách nhanh nhất để xóa hoặc xóa một vector

Question

Tôi có một mã nơi tôi thường điền vào một vectơ có từ 0 đến 5000 phần tử. Tôi biết tối đa không vượt quá 5000. Thay vì khởi tạo vector nhiều lần, tôi muốn làm chỉ một lần

vector<struct> myvector; 
myvector.reserve(5000); 

Tuy nhiên, để lấp đầy vector một lần nữa, tôi phải rõ ràng vector đầu tiên mà không thay đổi công suất của nó. Vì vậy, thông thường tôi gọi myvector.clear();

Đây là một hoạt động O (n). Có một cái gì đó đơn giản tôi có thể làm để tăng hiệu suất của điều này hoặc là điều này về tốt nhất mà nó sẽ nhận được?

Answer 1

Nếu cấu trúc của bạn có một destructor không tầm thường, sau đó cần phải được gọi cho tất cả các phần tử của véc-tơ bất kể nó được làm trống như thế nào. Nếu cấu trúc của bạn chỉ có một destructor tầm thường, trình biên dịch hoặc thực hiện thư viện chuẩn được phép tối ưu hóa quá trình hủy diệt và cung cấp cho bạn một hoạt động O (1).

Answer 2

Bất cứ điều gì bạn làm để xóa các mục hiện có khỏi vectơ cần phải (có khả năng) gọi hàm hủy của mỗi mục bị hủy. Do đó, từ quan điểm của container, điều tốt nhất bạn có thể hy vọng là độ phức tạp tuyến tính.

Điều đó chỉ để lại câu hỏi về loại mặt hàng bạn lưu trữ trong vectơ. Nếu bạn lưu trữ một cái gì đó như int rằng trình biên dịch có thể/sẽ biết trước thời hạn không có destructor để gọi, rất có thể là ít nhất khá tốt mà loại bỏ sẽ kết thúc với sự phức tạp liên tục.

Tôi nghi ngờ, tuy nhiên, việc thay đổi cú pháp (ví dụ: clear() và resize() so với erase(begin(), end())) sẽ tạo ra bất kỳ sự khác biệt đáng kể nào. Cú pháp không thay đổi thực tế rằng (trong trường hợp không có luồng) gọi N destructors là một hoạt động O (N).

Answer 3

Chi phí của clear() phụ thuộc rất lớn vào những gì các đối tượng được lưu trữ, và đặc biệt là liệu chúng có một destructor tầm thường. Nếu loại không có một destruct nhỏ, sau đó cuộc gọi phải tiêu diệt tất cả các đối tượng được lưu trữ và nó là trong thực tế một O (n) hoạt động, nhưng bạn không thể thực sự làm bất cứ điều gì tốt hơn. Bây giờ, nếu các phần tử được lưu trữ có các destructors tầm thường thì việc thực hiện có thể tối ưu hóa chi phí và clear() trở thành một hoạt động O (1) giá rẻ (chỉ cần đặt lại kích thước - end con trỏ).

Hãy nhớ rằng để hiểu được sự phức tạp tiệm cận, bạn cần phải biết những gì nó nói về. Trong trường hợp của clear() nó đại diện cho số lượng destructors được gọi là, nhưng nếu chi phí (ẩn) là 0, sau đó hoạt động là một no-op.