I edited my question, the second iteration pass need both i and foo. And in my case, copying a Foo is not an option.
Currently, my solution is to copy all is in a new vector for later use, but I don't like it, since function bar's performance matters, unnecessary malloc/free should be avoided.
This can be considered as an algorithm problem, independent of the particular Rust types you may use for it. You want to write an algorithm whose input is (i32, Foo)s and which must look at the i32s then the Foos. You want its input to consist of some sort of means to obtain (i32, Foo)s one at a time (an iterator).
The conflict is that you want to be able to obtain all the i32s before all the Foos, even though you've established that they are given in pairs one at a time. But being able to use the i32s twice and the Foos later means you must do something differently:
take the input in some form other than an iterator (something with more “random access”)
allocate temporary storage
be able to iterate twice somehow
Here is a possibility for the last: take two iterators. Then, while the numbers must be iterated twice, the Foos do not need to be involved:
Of course, this only helps if the indexes type is relevantly cheap to clone (say, it is a Range<i32> or an &[i32], or some custom iterator that generates the number sequence — but not itself a vector). But you've got to make bar ask for some means of iterating twice, or allocate a copy itself — otherwise you're asking for time travel.
The definition of an (Into)Iterator says that, unless you add something else like Clone, or have some other particular knowledge about the type, you can't rewind.
May I ask what is where for<'a> &'a Iter: IntoIterator<Item = &'a (i32, Foo)> means? Does that mean "if the Iter is borrowed, then the Item is &'a (i32, Foo)"? What's the different with or without this line when compiling? (I know it's high rank trait bounds, but I never know what it is used for)
And what's more, the function seems to work with vectors, but not works with maps.
Well, all kinds of iterators would be a lot broader than you may expected. For example you can make an iterator with websocket connection which parse each received messages and yield them directly. Since intermediate messages are not stored anywhere, to iterate it twice you need to store each elements in new vector yourself.