How to change what value begin() iterator points to?

Question

In C++ using the STL, I have a std::forward_list<int> whose iterators I want to modify, but I'm not sure how to/if it is even possible.

Say I have a forward list of the following elements:

std::forward_list<int> list {1,2,3,4,5};

Here, list.begin() returns 1. How can I move list.begin()? Say I want to set the beginning iterator to index 3 instead. Then the the list would look like so:

{4,5,1,2,3} // includes adjusting list.end() the same amount of begin()

Is this possible? Or is this a way to do this via pointers?

I do not think is ti possible it is always pointing to the first element in array. — , Aug 21 '21 at 00:12
`std::next(list.begin(), index)` - it's pretty expensive though — Ted Lyngmo, Aug 21 '21 at 00:17
`begin` always refers to the first element and the `end` iterator always referes to one past the last element. You can rearrange the elements in the list. If thats what you want: `std::rotate` — 463035818_is_not_an_ai, Aug 21 '21 at 00:25
I think there is no solution you want. the iterator is just a pointer and the container for main data is allocated privatly. Like other stl containers, `std::forward_list` hasn't got _shift rotation_ operation with its own member function. Alternativly, you can iterate from `begin()+n` to `!=begin()+n` by `iterator++`. — coding monster, Aug 21 '21 at 00:26

eerorika · Answer 1 · 2021-08-21T01:31:33.417

It seems that you're asking how to rearrange elements of a list by rotating them. There is a standard algorithm called std::rotate (and its ranges counterpart) which does just that with linear complexity. It works by swapping elements.

However, linked lists - unlike most other sequence data structures - have another tool that allows you to rotate them with constant complexity: Splicing. Splicing is a bit trickier with singly linked lists than doubly linked ones, but it's still possible. Here is an example:

int size = 5;
int new_first_index = 3;
auto new_first = std::next(list.begin(), new_first_index);
auto inclusive_last = std::next(new_first, size - new_first_index - 1);

// the rotation:
list.splice_after(inclusive_last, list, list.before_begin(), new_first);

It's important to understand that although the splicing has constant complexity and is very fast, the calls to std::next have linear complexity and is thus asymptotically the same as std::rotate. Thus, in order to be able to take full advantage of this, it's best used in cases where you already have the relevant iterators available without searching. _{This condition generally applies to nearly all list operations. If you don't have iterators stored, then either you're probably using the list wrong, or you probably should be using another data structure.}

Even if you do need to search for the iterators, this can be much faster (not asymptotically, but by a constant factor) than std::rotate if the elements are expensive to swap (does not apply to int) which is what std::rotate will do a lot.

ChrisB · Answer 2 · 2023-04-06T10:50:15.130

3

This rotates the list forwards by 3 elements (needs #include <algorithm>):

std::rotate(list.begin(), std::next(list.begin(), 3), list.end());

This will have O(n) complexity, since it will have to step through the complete list (cannot reach the last element through list.end(), since that is a forward iterator).

If that is not acceptable, consider using a different datastructure

For better asymtotic runtime: (O(1) if you rotate by a constant number): std::list
For potentially much better constant factors: std::vector

edited Apr 06 '23 at 10:50

answered Aug 21 '21 at 00:28

ChrisB

1,540
6
20

`std::rotate` itself is also O(n). Rotating `std::vector` is not asymptotically faster even if you count the cost of `std::next`. – eerorika Aug 21 '21 at 01:29
@eerorika, yes, but the constant factors dominate vector is faster by 10x in my caveman perf test: for - filling (push, no reserver) a list of 50 million elements, - rotating them by 25 million, - and summing up the result to make sure the optimizer doesn't get trigger happy are as follows: std::vector: 0.214 s std::vector, without the rotate: 0.199 s std::deque: 0.159 std::deque without the rotate: 0.131 s std::forward: 1.947 s std::forward: without the rotate 1.751 s --> just the rotates: forward: 196 ms vector: 15 ms – ChrisB Aug 21 '21 at 01:38
Yes I was trying to do this without using a built in function. I ended up just creating my own data structure of a circular linked list essentially, which works fine, and is O(1). – James Newman Aug 21 '21 at 01:43
@JamesNewman aggreed, if you really want a list some form of crazy skiplist is probably best. But as my test neatly demonstrates, contiguous data structures are usually much faster than linked lists due to the better cache usage. If performance was actually a concern I would just store a start index along with the vector and then add to that index and do modulus vector.size(). O(1). done. If you really want then write a fancy wrapper around that so you can keep using std algs. – ChrisB Aug 21 '21 at 01:55

score 2 · Accepted Answer · answered Aug 21 '21 at 01:18

Let's look at a picture. You have a singly-linked list with five elements.

  1 --> 2 --> 3 --> 4 --> 5 --> null
  ^                               ^
  |                               |
begin                            end

Now you want to make the beginning of the list point to the node with 4.

  1 --> 2 --> 3 --> 4 --> 5 --> null
                    ^             ^
                    |             |
                  begin          end

Notice how in this picture, there is no longer anything pointing to the node with 1. Even if you adjusted the end iterator, there would be no way to follow the arrows to get to 1. Nodes 1, 2, and 3 are left dangling, never to be found again. This is one reason why std::forward_list will not let you do this.

There is simply no path from 5 to 1 unless you make one. You could make one, though. One approach requires calculating an iterator pointing to the node with 5 and one pointing to the node with 4.

auto slice_begin = list.before_begin();       // For consistent naming
auto slice_end = std::next(list.begin(), 3);  // Calculate iterator to 4
auto destination = std::next(slice_end);      // Calculate iterator to 5

This gives you the following picture.

           1 --> 2 --> 3 --> 4 --> 5 --> null
     ^                       ^     ^
     |                       |     |
slice_begin              slice_end |
                                   |
                               destination

Now the goal is to move the nodes strictly between slice_begin and slice_end so that they come after destination. Fortunately, forward_list has a method for doing this.

list.splice_after(destination, list, slice_begin, slice_end);

Now you have your desired 4 -> 5 -> 1 -> 2 -> 3.

How to change what value begin() iterator points to?

3 Answers3