tối ưu hóa chuỗi nhỏ cho vector?

Question

Tôi biết một vài (tất cả?) STL triển khai thực hiện tối ưu "chuỗi nhỏ", thay vì lưu trữ 3 con trỏ thông thường để bắt đầu, kết thúc và dung lượng chuỗi sẽ lưu trữ dữ liệu ký tự thực trong bộ nhớ được sử dụng cho con trỏ nếu sizeof (ký tự) < = sizeof (con trỏ). Tôi đang ở trong một tình huống mà tôi có rất nhiều vectơ nhỏ với kích thước phần tử < = sizeof (con trỏ). Tôi không thể sử dụng mảng kích thước cố định, vì vectơ cần có khả năng thay đổi kích thước động và có khả năng phát triển khá lớn. Tuy nhiên, kích thước trung bình (không có nghĩa là) của vectơ sẽ chỉ là 4-12 byte. Vì vậy, một "chuỗi nhỏ" tối ưu hóa thích nghi với vectơ sẽ khá hữu ích cho tôi. Có một điều như vậy tồn tại?

Tôi đang suy nghĩ về việc cuộn của riêng mình bằng cách đơn giản lực lượng vũ phu chuyển đổi vectơ thành chuỗi, tức là cung cấp giao diện vectơ cho chuỗi. Ý tưởng tốt?

Answer 1

Bạn có thể mượn triển khai SmallVector từ LLVM. (chỉ tiêu đề, nằm trong LLVM \ include \ llvm \ ADT)

Answer 2

Đó là discussed năm trước (và một vài tên trong chuỗi đó có thể trông hơi quen thuộc :-)), nhưng tôi không biết triển khai hiện có. Tôi không nghĩ rằng tôi muốn cố gắng để thích nghi std :: string cho nhiệm vụ. Các yêu cầu chính xác về loại mà trên đó std :: basic_string không được nêu rõ, nhưng tiêu chuẩn là khá rõ ràng rằng nó chỉ dành cho một cái gì đó hoạt động rất giống như char. Đối với các loại khác nhau đáng kể, nó có thể vẫn hoạt động, nhưng thật khó để nói điều gì sẽ xảy ra - nó không bao giờ được dự định, và có lẽ chưa được thử nghiệm với nhiều loại khác với số nguyên nhỏ.

Khi bạn bắt đầu, thực hiện std::vector từ đầu (thậm chí bao gồm tối ưu hóa véc tơ nhỏ) sẽ không quá khó khăn.

Answer 3

Nếu T là loại POD tại sao không basic_string thay vì vector ??

Answer 4

Tăng 1.58 vừa được phát hành và thư viện Container có lớp học small_vector dựa trên LLVM SmallVector.

Ngoài ra còn có static_vector không thể phát triển vượt quá kích thước ban đầu đã cho. Cả hai vùng chứa đều chỉ có tiêu đề.

thư viện folly của facebook cũng có một số vùng chứa tuyệt vời.

Nó có một small_vector có thể được định cấu hình với thông số mẫu để hoạt động như các vectơ static hoặc small của boost. Nó cũng có thể được cấu hình để sử dụng các loại số nguyên nhỏ cho sổ sách kế toán nội bộ của nó mà cho rằng chúng là facebook không có gì ngạc nhiên :)

Có công việc đang tiến hành để làm nền tảng thư viện hỗ trợ Windows/MSVC ...