How can I define operator< for bidirectional iterator?

How can I define operator< for bidirectional iterator? ( list::iterator )

(I would like 开发者_JAVA技巧to use list and not vector.)

You can't do it directly, but you can compute std::distance(x.begin(), it1) and std::distance(x.begin(), it2) and compare those. Given that lists don't have random access, you expect to have to pay the price for such a query by having to traverse the entire list.

Edit: This will perform poorly if both iterators are near the end of the list. If you want to get more fancy, you could write some exploring algorithm that moves outwards from both iterators:

[ .... <-- it1 --> .... <-- it2 --> .... ]

You would basically keep two copies for each, fwd1/rev1 and fwd2/rev2, and you decrement the rev* iterators until you hit x.begin() and advance the fwd* iterators until you hit x.end(). If your iterator pairs are uniformly distributed, this probably has better expected runtime.

Impossible. You might need to walk until end, and for that you need to know the list of origin, which is not encoded in a list::iterator.

(You can make a function object for this purpose, though, which takes the list or origin as a constructor argument. Mind you, finding out whether one iterator is less-than another would take O(n) time.)

You can't do this because you'd have to know the start and/or end of the list in order to make such a comparison. Only random access iterators define operator<.

Supposing ++(list.end()) is not undefined behaviour and equals list.end(), there is a way. But i am not sure of this hypothesis.

If it is valid, you can define a simple algorithm to obtain the result you want.