C++ STL - Tại sao phương thức forward_list no size()?

Question

Tôi đã sử dụng forward_list của C++ 11 làm vùng chứa để chèn nhanh, không cần nhiều bộ nhớ, vì đây là danh sách liên kết đơn lẻ.

Sau khi nhận ra rằng forward_list không có phương pháp size(), tôi hơi bối rối về lý do đằng sau điều đó. Nó có thể không chỉ duy trì một lĩnh vực tư nhân theo dõi các nút chèn và gỡ bỏ, do đó, thực hiện một O (1) kích thước() hoạt động?

Answer 1

N2543 là đề xuất và thảo luận chi tiết về size().

Lựa chọn giữa tùy chọn 3 [không cung cấp size()] và tùy chọn 2 [cung cấp O (1) size()] là một vấn đề về bản án. Tôi đã chọn Tùy chọn 3 vì lý do tương tự mà tôi đã chọn chèn sau thay vì chèn trước: Tùy chọn 3 phù hợp hơn với mục tiêu trên không so với danh sách được liên kết kiểu C viết tay. Duy trì số tăng gấp đôi kích thước của đối tượng forward_list (một từ cho đầu danh sách và một cho số đếm), và nó làm chậm hoạt động làm thay đổi số lượng nút. Trong hầu hết các trường hợp, đây không phải là sự thay đổi về độ phức tạp tiệm cận (sự thay đổi về độ phức tạp tiệm cận ở một trong các hình thức splice), nhưng không phải là trên không trên không. Đó là chi phí mà tất cả người dùng sẽ phải trả tiền, cho dù là họ có cần tính năng này hay không và đối với những người dùng quan tâm đến việc duy trì số lượng, nó cũng dễ dàng duy trì nó bên ngoài danh sách , bằng cách tăng số lượng mỗi lần chèn và giảm nó với mọi lần xóa, vì nó là để duy trì số đếm trong danh sách.

Answer 2

Các thùng chứa STL đã loại bỏ các đặc tính của cấu trúc dữ liệu theo cách truyền thống không thực hiện tốt về mặt thời gian và không gian.

Thêm Trích từ "C++ tiêu chuẩn thư viện - một hướng dẫn và tài liệu tham khảo"

Một std::forward_list không cung cấp một chức năng size() thành viên. Đây là hậu quả của việc bỏ qua các tính năng tạo chi phí thời gian hoặc không gian so với danh sách liên kết đơn lẻ được viết tay.

Answer 3

tôi tự hỏi liệu ủy ban chuẩn có được coi là kết hợp làm tham số mẫu có thể thêm bảo trì thành viên kích thước tùy chọn vào các lớp danh sách không? Điều này sẽ cho phép lớp có số phần tử tùy chọn, mà không làm mất tính tổng quát.

như thế này

class HasSize 
{ 
public: 
    HasSize() : size_(0) { } 

    void addSize(size_t add) { size_ += add; } 

    bool has_size() { return true; } 

    size_t size() { return size_; } 

    size_t size_; 
}; 

class NoSize 
{ 
public: 
    void addSize(size_t add) { } 

    bool has_size() { return false; } 

    size_t size() { return 0; } 
}; 

template<type T, type Allocator, type Sz = HasSize> 
class forward_list 
{ 

    void push_back(T &arg) 
    { 
     ... 
     opt_.addSize(1); 
    } 

    size_t size() 
    { 
     if (opt_.has_size()) 
      return opt_.size(); 
     else 
      return std::distance(begin(), end()); 
    } 

    Sz opt_; 
}; 

/câu hỏi này đã được đánh dấu là nhân đôi, vì vậy thêm nó ở đây/