C++ std :: vector hoạt động như thế nào?

Question

Làm cách nào để thêm và xóa các phần tử "rescale" dữ liệu? Làm thế nào là kích thước của vector tính toán (Tôi tin rằng nó được theo dõi)? Bất kỳ tài nguyên bổ sung nào khác để tìm hiểu về vectơ sẽ được đánh giá cao.

Answer 1

Xét về kích thước, có hai giá trị của sự quan tâm cho một std::vector: size, và capacity (truy cập thông qua .size() và .capacity()).

.size() là số phần tử được chứa trong vectơ, trong khi .capacity() là số phần tử có thể được thêm vào vectơ, trước khi bộ nhớ được phân bổ lại.

Nếu bạn .push_back() một phần tử, kích thước sẽ tăng một, cho đến khi bạn đạt được dung lượng. Sau khi đạt được dung lượng, phần lớn (tất cả?) Triển khai, cấp phát lại bộ nhớ, tăng gấp đôi dung lượng.

Bạn có thể đặt trước dung lượng sử dụng .reserve. Ví dụ:

std::vector<int> A; 
A.reserve(1);  // A: size:0, capacity:1 {[],x} 
A.push_back(0);  // A: size:1, capacity:1 {[0]} 
A.push_back(1);  // A: size:2, capacity:2 {[0,1]} 
A.push_back(2);  // A: size:3, capacity:4 {[0,1,2],x} 
A.push_back(3);  // A: size:4, capacity:4 {[0,1,2,3]} 
A.push_back(4);  // A: size:5, capacity:8 {[0,1,2,3,4],x,x,x} 

Việc tái phân bổ bộ nhớ có thể xảy ra ở dòng 4, 5, và 7.

Answer 2

Tôi đã viết một véc tơ trong C++ một năm hoặc lâu hơn trước đây. Nó là một mảng có kích thước thiết lập (ví dụ 16 ký tự) được mở rộng bởi số lượng đó khi cần thiết. Tức là, nếu kích thước mặc định là 16 ký tự và bạn cần lưu trữ Hi my name is Bobby, thì nó sẽ tăng gấp đôi kích thước của mảng thành 32 ký tự rồi lưu trữ mảng char tại đó.

Answer 3

Các vector thường có ba con trỏ. Nếu vectơ chưa bao giờ được sử dụng thì tất cả chúng đều là 0 hoặc NULL.

• Một thành phần đầu tiên của vectơ. (Đây là bắt đầu() iterator)
• Một đến yếu tố cuối cùng của vector + 1. (đây là kết thúc() iterator)
• Và một hơn để cuối cùng phân bổ nhưng yếu tố không sử dụng + 1. (trừ này bắt đầu() là công suất)

Khi một phần tử được chèn vào, vectơ phân bổ một số bộ nhớ và đặt con trỏ của nó. Nó có thể phân bổ 1 phần tử, hoặc nó có thể phân bổ 4 phần tử. Hoặc 50.

Sau đó, nó chèn phần tử và tăng con trỏ phần tử cuối cùng.

Khi bạn chèn nhiều phần tử hơn phân bổ véc-tơ phải có nhiều bộ nhớ hơn. Nó đi ra ngoài và nhận được một số. Nếu vị trí bộ nhớ thay đổi thì nó phải sao chép tất cả các phần tử vào không gian mới và giải phóng không gian cũ.

Một lựa chọn phổ biến để thay đổi kích thước là tăng gấp đôi phân bổ mỗi khi cần nhiều bộ nhớ hơn.

Answer 4

Việc triển khai std::vector thay đổi đôi chút với C++ 0x trở lên với phần giới thiệu ngữ nghĩa di chuyển (xem What are move semantics? để được giới thiệu).

Khi thêm một yếu tố để một std::vector đó là đã đầy đủ thì vector được thay đổi kích cỡ trong đó bao gồm một thủ tục phân bổ một khu vực bộ nhớ mới, lớn hơn, di chuyển dữ liệu hiện có để mới vector, xóa vector không gian cũ, và sau đó thêm phần tử mới.

std::vector là một lớp thu thập trong Thư viện mẫu chuẩn. Đặt đối tượng vào một vector, lấy chúng ra, hoặc vector thực hiện thay đổi kích cỡ khi một mục được thêm vào một đầy đủ vector tất cả yêu cầu lớp của đối tượng hỗ trợ toán tử gán, một hàm tạo bản sao và di chuyển ngữ nghĩa. (Xem type requirements for std::vector cũng như std::vector works with classes that are not default constructible? để biết chi tiết.)

Một cách để nghĩ về std::vector là như một phong cách C array của các yếu tố tiếp giáp của các loại quy định khi vector được định nghĩa rằng có một số chức năng bổ sung để tích hợp nó vào các tiêu chuẩn Thư viện mẫu. Điều gì ngăn cách một vector từ một tiêu chuẩn array là một vector sẽ tự động phát triển khi các mục được thêm vào. (Xem std::vector and c-style arrays cũng như When would you use an array rather than a vector/string? đối với một số cuộc thảo luận về sự khác biệt.)

Sử dụng std::vector cho phép việc sử dụng các linh kiện Standard Template Library khác như thuật toán để sử dụng std::vector đi kèm với một vài lợi thế khá hơn một C phong cách array như bạn có thể sử dụng chức năng đã tồn tại.

Bạn có thể chỉ định kích thước ban đầu nếu tối đa được biết trước thời hạn. (Xem Set both elements and initial capacity of std::vector cũng như Choice between vector::resize() and vector::reserve())

Thông tin cơ bản về bộ con trỏ sử dụng bộ nhớ được cấp phát từ bộ nhớ. Những con trỏ này cho phép các hoạt động thực tế truy cập vào các phần tử được lưu trữ trong vector, xóa các phần tử từ vector, lặp lại trên vector, xác định số phần tử, xác định kích thước của nó, v.v. , việc xóa các mục có thể dẫn đến việc di chuyển các mục còn lại để đóng bất kỳ lỗ nào được tạo bởi thao tác xóa.

Với ngữ nghĩa di chuyển C++ hiện đại, chi phí trên std::vector đã bị giảm xuống, thường là vùng chứa mặc định sẽ được sử dụng cho hầu hết các ứng dụng theo khuyến cáo của Bjarne Stroustrup trong cuốn sách. +11.