sorting iterators with std::sort

Question

I want to sort a vector vec containing int iterators pointing to elements in another vector int_vec. I want to use the following compare function: it1 < it2 if and only if

index[it1 - int_vec.begin()] < index[it2 - int_vec.begin()].

Where index is a third vector specifying the key of an iterator. Now the vector index is an internal array of the constructor of A and int_vec is a member variable of a class A. I tried to just pass an anonymous function like this:

std::sort(vec.begin(),flow.end(), [&index,&edges](const int_iter it1 ,const int_iter it2) -> bool
{ 
    index[it1 - int_vec.begin()] < index[it2 - int_vec.begin()]; 
})

but I get an error telling me that member objects cannot be captured. Exact error message is:

'this' cannot be implicitly captured in this context
        index[it1 - int_vec.begin()] < index[it2 - int_vec.begin()];.

I also tried to just declare an external compare function but it is not clear to me how I can bind two fixed values to it(I read about boost::bind which looks like solving exactly this but I would prefer to not download additional libraries).

*I want to sort a vector vec containing int iterators pointing to elements in another vector int_vec* -- Just this alone is a bad idea, as vector iterators are invalidated if the vector is resized. — PaulMcKenzie, Dec 31 '16 at 20:43
'member objects cannot be captured', sounds like you need to capture this, just `[this]` — Oleg Bogdanov, Dec 31 '16 at 20:45
Don't store iterators if you're just going to convert them to indices later, save yourself the trouble and store them as indices first. (Whenever you want to save an index use: `std::distance(vec.begin(), iter)`) — Brian Rodriguez, Dec 31 '16 at 20:48
@user3726947 *when initializing I heavily use .push_back()* -- If you're storing iterators while you're issuing these push_back calls, those iterators are not guaranteed to be valid after you've set up the vector. If they are, you are just lucky that a reallocation hasn't occurred. Also, resizing means anything that would affect the vector size, not just the `vector::resize()` call. See [iterator invalidation rules](http://stackoverflow.com/questions/6438086/iterator-invalidation-rules) — PaulMcKenzie, Dec 31 '16 at 20:56

user3684240 · Accepted Answer · 2016-12-31T21:23:20.953

4

You have many problems there.

The most obvious one is that your code lacks [this].
vec.begin(),flow.end()

You can't take the beginning of one and the end of another vector.

This is the corrected code:

std::sort(vec.begin(),vec.end(), [this,&index,&edges](const int_iter it1 ,const int_iter it2) -> bool
{ 
    index[it1 - int_vec.begin()] < index[it2 - int_vec.begin()]; 
})

However, you should tell us what you are trying to achieve and I'm sure we can find a better solution. Using vectors of iterators of other vectors is already very dangerous, doing subtractions on them without checking is just careless.

Less dangerous solution:

std::vector<int> int_vec;
std::vector<size_t> int_vec_order(int_vec.size());
std::iota(int_vec_order.begin(), int_vec_order.end(), size_t(0));

std::sort(int_vec_order.begin(), int_vec_order.end(), [&int_vec](const size_t a, const size_t b) {
  // apply your order to int_vec.at(a) and int_vec.at(b)
});

// output them
for(const size_t i : int_vec_order) {
  // output int_vec.at(i)
}

edited Dec 31 '16 at 21:23

answered Dec 31 '16 at 20:55

user3684240

1,420
2
12
18

oh the flow thing was a typo. So this is kinda made up. In reality int_vec doesn't stores int but structs that are quiet big and I don't want to copy them around, so thats why I am using iterators. Maybe it would have been better to say this. I want to do the following: I store some objects which I get in a predefined order in int_vec then store some additional objects in there. Then i sort int_vec(by some order which is not important). Now I want to print the objects in the predefined order(but not the additional objects that are in int_vec). – user3726947 Dec 31 '16 at 21:15
Edited the answer. You can always use indexes which are less dangerous. – user3684240 Dec 31 '16 at 21:23
@user3726947 The solution is to use indices, not iterators. [See this answer](http://stackoverflow.com/questions/40405266/having-trouble-creating-an-array-that-shows-how-the-indices-were-moved-in-anothe/40405691#40405691) – PaulMcKenzie Dec 31 '16 at 21:41
Isn't that exactly what I wrote? – user3684240 Dec 31 '16 at 21:44
Your edit didn't show exactly how to write the lambda portion of the sort. – PaulMcKenzie Dec 31 '16 at 21:46

sorting iterators with std::sort

1 Answers1