{"id":105908,"date":"2021-11-12T07:00:00","date_gmt":"2021-11-12T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=105908"},"modified":"2025-03-24T16:58:09","modified_gmt":"2025-03-24T23:58:09","slug":"20211112-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20211112-00\/?p=105908","title":{"rendered":"Another way of looking at C++ reverse iterators"},"content":{"rendered":"

C++ has this thing called a reverse_iterator<\/code> that takes a regular iterator and goes in the opposite direction. You might think that an iterator and its reverse point to the same thing, and it’s just the increment and decrement operators that are reversed, but that’s not true. An iterator and its reverse point to different things<\/i>.<\/p>\n

This reason for this comes down to a quirk of the C++ language: You are allowed to have a pointer “one past the end” of a collection, but you are not allowed to have a pointer “one before the beginning” of a collection.<\/p>\n

When moving forward through a collection, you can use the “one past the end” pointer as the sentinel that means “you’re done.”<\/p>\n\n\n\n\n
\u00a0<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n\n
\u2191
\nbegin<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nend<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

But you don’t have such a luxury when going backward:<\/p>\n\n\n\n\n
\u00a0<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u00a0<\/td>\n<\/tr>\n
\n
\u2191
\noops<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nbegin<\/div>\n<\/td>\n
 <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

You want to create an end<\/i> sentinel value immediately before the first element, but you can’t because the C++ language forbids it.<\/p>\n

The standard library finesses the problem by making the reverse iterator “off by one”: The element referenced by the iterator is the one before<\/i> the one it nominally points to.<\/p>\n\n\n\n\n
\u00a0<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n\n
\u2191
\nend<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nok<\/div>\n<\/td>\n
\n
\u2191
\nbegin<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

This off-by-one behavior is a bit tricky to wrap your brain around, but here’s a way of looking at it that’s a bit less wacky: View the pointer as pointing, not at the center of an element, but at its start. When iterating forward, you look to the element in front<\/i> of the pointer, and when iterating backward, you look to the element in back<\/i> of the pointer. In both cases, you look in the direction of motion.<\/p>\n\n\n\n\n
\u00a0<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n\n
\u2191begin<\/span><\/div>\n<\/td>\n
\n
\u2191ok<\/span><\/div>\n<\/td>\n
\n
\u2191ok<\/span><\/div>\n<\/td>\n
\n
\u2191ok<\/span><\/div>\n<\/td>\n
\n
\u2191ok<\/span><\/div>\n<\/td>\n
\n
\u2191ok<\/span><\/div>\n<\/td>\n
\n
\u2191end<\/span><\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n
\u00a0<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u00a0<\/td>\n<\/tr>\n
\n
end\u2191<\/span><\/div>\n<\/td>\n
\n
ok\u2191<\/span><\/div>\n<\/td>\n
\n
ok\u2191<\/span><\/div>\n<\/td>\n
\n
ok\u2191<\/span><\/div>\n<\/td>\n
\n
ok\u2191<\/span><\/div>\n<\/td>\n
\n
ok\u2191<\/span><\/div>\n<\/td>\n
\n
begin\u2191<\/span><\/span><\/div>\n<\/td>\n
 <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Now the off-by-one behavior is easier to see. A pointer when interpreted as a forward iterator looks forward one element, but when interpreted as a reverse iterator looks backward one element.<\/p>\n\n\n\n\n\n\n\n\n\n\n
\u00a0<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u2022<\/td>\n\u00a0<\/td>\n<\/tr>\n
\n
rev
\nend<\/div>\n
\u2191<\/p>\n<\/div>\n<\/td>\n
\n
fwd
\nbegin<\/div>\n<\/td>\n
 <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
 <\/td>\n\n
rev
\nok<\/div>\n
\u2191<\/p>\n<\/div>\n<\/td>\n
\n
fwd
\nok<\/div>\n<\/td>\n
 <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n\n
rev
\nok<\/div>\n
\u2191<\/p>\n<\/div>\n<\/td>\n
\n
fwd
\nok<\/div>\n<\/td>\n
 <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n <\/td>\n\n
rev
\nok<\/div>\n
\u2191<\/p>\n<\/div>\n<\/td>\n
\n
fwd
\nok<\/div>\n<\/td>\n
 <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n <\/td>\n <\/td>\n\n
rev
\nok<\/div>\n
\u2191<\/p>\n<\/div>\n<\/td>\n
\n
fwd
\nok<\/div>\n<\/td>\n
 <\/td>\n <\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n\n
rev
\nok<\/div>\n
\u2191<\/p>\n<\/div>\n<\/td>\n
\n
fwd
\nok<\/div>\n<\/td>\n
 <\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n\n
rev
\nbegin<\/div>\n
\u2191<\/p>\n<\/div>\n<\/td>\n
\n
fwd
\nend<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\n