C++ - mảng Thông tư có giới hạn dưới/trên?

Question

Tôi muốn tạo một cái gì đó tương tự như một danh sách liên kết đôi (nhưng với mảng) mà làm việc với giới hạn dưới/trên.

Một mảng tròn điển hình có lẽ sẽ giống như sau:

next = (current + 1) % count; 
previous = (current - 1) % count; 

Nhưng số học toán học để kết hợp thấp/cận trên đúng vào này là gì?

• 0 (thấp hơn mục bound 1)
• 2 (trên ràng buộc mục 1)
• 3 (thấp hơn mục bound 2)
• 4 (giới hạn trên mục 2)

Vì vậy:

-> tiếp theo trên chỉ mục 2 cho mục 1 trả về 0

-> trước đây về chỉ số 0 cho mục 1 lợi nhuận 2

-> tiếp theo trên chỉ số 4 cho mục 2 lợi nhuận 3

-> trước đây về chỉ số 3 cho mục 2 lợi nhuận 4

Cảm ơn bạn !

LƯU Ý: Không thể sử dụng thư viện bên ngoài.

Answer 1

Trong thuật ngữ toán học tổng quát:

next === current + 1 (mod count) 
prev === current - 1 (mod count) 

trong đó === là toán tử 'đồng dư'. Chuyển đổi này để các nhà điều hành mô đun, nó sẽ là:

count = upper - lower 
next = ((current + 1 - (lower%count) + count) % count) + lower 
prev = ((current - 1 - (lower%count) + count) % count) + lower 

Nó sẽ là tùy thuộc vào bạn để tìm hiểu phía trên & cận dưới cho mỗi mục. Bạn có thể lưu trữ điều này trong một cây nhị phân để thu hồi nhanh. Có lẽ tôi không hiểu câu hỏi của bạn.

(lưu ý rằng điều này giả định thấp hơn < trên, và thấp hơn> 0)

Answer 2

Tăng cường có số Circular container mà tôi tin rằng bạn cũng có thể đặt giới hạn.

Thực tế, ví dụ trên trang đó trông rất giống với những gì bạn đang nói ở đây.

Nhưng dù sao, bạn có thể hoàn thành phần toán học của nó dễ dàng sử dụng một mô đun:

Vì vậy, nói tối đa của bạn là 3:

int MAX = 3; 
someArray[ 0 % MAX ]; // This would return element 0 
someArray[ 1 % MAX ]; // This would return element 1 
someArray[ 3 % MAX ]; // This would return element 0 
someArray[ 4 % MAX ]; // This would return element 1 

Answer 3

  +=======+  +=======+  +=======+ 
      | Obj | ---> | Obj | ---> | Obj | 
buffer | 1 | <--- | 2 | <--- | 3 | 
      +=======+  +=======+  +=======+ 

index  0     1    2  /* our first run */ 

index  3     4    5  /* second run */ 

and so on ... 

Vì vậy, bạn sẽ thấy một danh sách 3 thành viên, mục 1 được lập chỉ mục bởi 0, 3, 6,, vvTương tự như vậy, mục thứ hai được lập chỉ mục bởi 1, 4 (1 + 3), 7 (4 + 3), ...

Nguyên tắc chung là: next <- (next + 1) % size, nơi size = upper - lower + 1

Sử dụng công thức này, chúng tôi nhận được:

curr |  next 
-------+----------------- 
    0 | (0 + 1) % 3 = 1 
-------+----------------- 
    1 | (1 + 1) % 3 = 2 
-------+----------------- 
    2 | (2 + 1) % 3 = 0 
-------+----------------- 

Hy vọng rằng sẽ giúp

Answer 4

tôi đã viết bài viết này một vài năm trở lại về một vòng lặp STL vòng lặp.

http://noveltheory.com/Iterators/Iterator_N0.htm

Nó sẽ làm việc trên bất kỳ bộ sưu tập STL (vectơ & tăng: mảng, vv)