C++ Contiguous Sequence Concept

Question

Thư viện chuẩn C++ cung cấp nhiều "khái niệm" được sử dụng để chỉ định giao diện cho các đối tượng vùng chứa. Ví dụ: std::vector triển khai các ý tưởng Container, Sequence, RandomAccessContainer và ReversibleContainer.

Có một khái niệm, quy định hoặc trong C++ 03 hoặc C++ 11, mô tả một Sequence mà đảm bảo bộ nhớ tiếp giáp giữa các yếu tố, do đó:

static_cast<void*>(&some_sequence[N]) == static_cast<void*>(&some_sequence[0] + N)>

Đây sẽ là một hữu ích vì nó cho bạn biết liệu bạn có thể sử dụng Container với bất kỳ chức năng nào mong đợi bộ đệm bộ nhớ tiếp giáp, chẳng hạn như std::istream::read.

Tôi biết rằng, trong thực tế, chỉ std::vector (và tôi nghĩ std::string trong C++ 11 chỉ) thực sự đảm bảo một bộ đệm tiếp giáp cơ bản - nhưng là sự bảo đảm này độc đáo để std::vector hoặc là có một định nghĩa "Khái niệm" cho biết một generic Sequence lớp cung cấp bộ nhớ tiếp giáp?

Answer 1

Từ C++ 03, chỉ std::vector đảm bảo rằng (23.2.4.1):

Các yếu tố của một vector được lưu trữ liên tục kế nhau, có nghĩa là nếu v là một vector trong đó T là một số loại khác với bool, sau đó nó tuân theo danh tính & v [n] == & v [0] + n cho tất cả 0 < = n < v.size().

C++ 11 thêm std :: mảng, bao bọc quanh mảng có kích thước cố định và cũng có cùng thuộc tính. Tôi không nghĩ rằng có một cách để biết nếu bất kỳ container có tài sản như vậy.

Answer 2

Tôi thấy bản thân mình phải xác định các loại thực hiện tính năng này nhiều lần. Tôi không biết nếu phát minh ra một khái niệm "đặc biệt" là thanh lịch (tưởng tượng rằng nó là một khái niệm liên quan đến bộ nhớ, không phải là rất trừu tượng) nhưng tôi đồng ý một cái gì đó như thế này sẽ hữu ích.

Trong khi thực tế và dịch khái niệm/yêu cầu này thành yêu cầu cú pháp thuần túy, hãy quay lại. Nếu chúng ta hạn chế bản thân với tiêu chuẩn, các lớp học đảm bảo (hoặc gần như đảm bảo) là gì? theo thứ tự liên quan:

std::vector<T> 
T[N] // !! 
std::array<T, N> 
std::string 
std::initializer_list<T> 
std::valarray<T> 

Trong tất cả các, std::vector, std::array, std::string có một hàm thành viên được gọi là .data(). Vì vậy, nếu điều này là đủ cho bạn, có thể dựa vào sự hiện diện của thành viên .data() -> T* để chỉ bộ nhớ tiếp giáp.

Bạn có hai lựa chọn:

1) Tận dụng tối nỗ lực để sử dụng chức năng thành viên .data() để nâng cao một lỗi cú pháp nếu loại là không tiếp giáp. (Không khó nếu bạn thay thế ví dụ t[0] bởi *t.data())

2) Sử dụng một số loại SFINAE trên .data().

template<class ContiguousSequence, typename = decltype(std::declval<ContigiousSequence>().data())> 
void fun(ContiguousSequence&& s){...} // this function will only work with contiguous data 

Hơn nữa, C++ 17 có std::data mà khái quát nó cho tất cả các loại với .data() và quá tải bổ sung cho T[N] và std::initializer_list<T>. Vì vậy, bạn có thể thay thế ....data() theo số std::data(...) ở trên.

Kết luận, tôi nghĩ rằng đó là một quy ước tốt lành là nếu một loại có chức năng data (hoặc .data() trong C++ 11) trả về một con trỏ đến kiểu giá trị sau đó các yếu tố là tiếp giáp.

(Ok, những gì về std::valarray<T>? Nó không làm việc, trừ khi bạn quá tải std::data(std::valarray<T>&). Nhưng ai sử dụng std::valarray không? Nó là một góc khá bị bỏ rơi của C++, tôi nghĩ)

Cuối cùng, lưu ý cho ví dụ rõ ràng là std::map và ít rõ ràng là std::deque không có chức năng .data() (hoặc std::data(...)). boost::multi_array<..., N> có một thành viên .data() và trả về một con trỏ đến phần tử mảng, không rõ ràng nếu đây là chuỗi liên tiếp theo ý bạn muốn (vì thứ tự không rõ ràng) nhưng theo một nghĩa nào đó nó cũng là một bộ nhớ liên tiếp.

EDIT: Có hai đề xuất hiện giải quyết vấn đề này (nhưng ở cấp độ của các vòng lặp) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3884.pdfhttp://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4284.html

Answer 3

"Tiếp giáp container" được specifed trong C++ 17. Từ $23.2.1/13 General container requirements [container.requirements.general]:

Một container tiếp giáp là một container có hỗ trợ lặp truy cập ngẫu nhiên ([random.access.iterators]) và có thành viên loại iterator và const_iterator là lặp tiếp giáp ([iterator.requirements.general]).

Và về "vòng lặp liền kề", $24.2.1/5 In general [iterator.requirements.general]:

vòng lặp đó tiếp tục đáp ứng các yêu cầu đó, cho các giá trị không thể thiếu n và iterator dereferenceable giá trị a và (a + n), * (a + n) tương đương với * (addressof (* a) + n), được gọi là các trình lặp liên tiếp.

std::vector (trừ std::vector<bool>), std::array và std::basic_string là container tiếp giáp.