Remove elements pairwise from vector

[koperenkogel]

Dear cpp-ians,

I am working with a vector of structures.
vector <meta_segment> meta_segm (2421500);

and the structure look like:
struct meta_segment
{
float id;
float num;
float mean;
float sum;
float sumofsquares;
float std;
struct pixel * head;
struct pixel * tail;
struct pixel * edge_head;
struct pixel * edge_tail;
struct segment * segment;
bool full;
};

I run a procedure that:
1. takes a random element of the vector
2. runs a function on the element
3. removes the element from the list with the 'meta_segm.erase'.
and repeats this procedure untill the vector is empty

The problem I have is in the function of step 2. This function uses the
random element (A) (out of step 1) and searches for a second element
(B) based on different criteria. So my function runs actually for two
elements (A and B), instead of only one (A).
Now, I want to translate this in step 3 and remove A and B from the
vector.

I know how to remove A, but I have no idea how to remove B. B is not
necessarly A's neighbour. I thought of searching for it (based on the
same criteria I use to detect it), but I that takes to much time since
I will have to do it for every element then.

Any advice on how to program this kind of problem is welcome.

Thanks in advance and kind regards,
Stef

[msalters]

koperenkogel wrote:

Dear cpp-ians,

I am working with a vector of structures.
vector <meta_segment> meta_segm (2421500);

I run a procedure that:
1. takes a random element of the vector
2. runs a function on the element
3. removes the element from the list with the 'meta_segm.erase'.
and repeats this procedure untill the vector is empty

The problem I have is in the function of step 2. This function uses the random element (A) (out of step 1) and searches for a second element
(B) based on different criteria. So my function runs actually for two
elements (A and B), instead of only one (A).
Now, I want to translate this in step 3 and remove A and B from the
vector.

I know how to remove A, but I have no idea how to remove B. B is not
necessarly A's neighbour. I thought of searching for it (based on the
same criteria I use to detect it), but I that takes to much time since I will have to do it for every element then.

Searching for an element in a vector is O(N), because there is no
natural ordering. Usually, the order is determined by the insertions,
or the last call to std::sort, or another algorithm that changes the
order of elements. That might not be the order in which you would want
them. Worse, removing a random element from a vector is expensive.

You would be better off using a std::set. However, this will work only
if you can determine a single order which allows you to find every
element 'B'.

To really give you a good answer, we'd need to know how you find a B
for a given A.

HTH
Michiel Salters

[koperenkogel]

Thanks for anwser. I will try to sketch the problem:

I am writing an image segmentation program based on a multi-resolution
technique. Multi-resolution segmentation is a bottom up region-merging
technique starting with one-pixel objects. In numerous subsequent
steps, smaller image objects are merged into bigger ones. In each step,
that pair of adjacent image objects is merged which stands for the
smallest growth of the defined heterogeneity.
So what happens. I first merge single pixels into couples. Afterwards I
start merging the couples into groups of four and so on. Once a defined
heterogeneity is reached for an object (=full), it does not participate
any longer in the process till all objects are full.

How does this look like in C++: I have a vector X (nrow x ncol) and the
elements are structures :
struct meta_segment
{ ...
struct segment * group;
// Group is a pointer to an array Y[nrow][ncol]
...};
and array Y[nrow][ncol] is an image and the pixels are structures:
struct segment
{ ...
struct meta_segment * meta_segm;
// Meta-segm is a pointer to the vector
...};

So X and Y both point to eachother.

Now I want the program to work as follows:
1. Pick a random A out of vector X
2. A->group in X points to pixels a in Y
3. Search the pixels b in Y that are the closest to a. I have written
this, and get the coordinates of b in Y as result.
4. b->meta-segm points to B in X
5. Merge A and B (+ a and b) by:
* removing A and B out of X and putting them in another vector C
in X2(using push_back)
* replacing the pointers:
- C->group points to a and b
- a->meta-segm and b->meta-segm point to C

This is done till X is empty, and then the process is repeated for X2
and so on.

Now my questions are:
Can I remove B out of X, since I only have a pointer to it?
Are the other pointers to elements in X then constant when I remove A
out of X? Or do they change also?

Kind regards,
Stef

[Karl Heinz Buchegger]

koperenkogel wrote:

Dear cpp-ians,

I am working with a vector of structures.
vector <meta_segment> meta_segm (2421500);

and the structure look like:
struct meta_segment
{
float id;
float num;
float mean;
float sum;
float sumofsquares;
float std;
struct pixel * head;
struct pixel * tail;
struct pixel * edge_head;
struct pixel * edge_tail;
struct segment * segment;
bool full;
};

I run a procedure that:
1. takes a random element of the vector
2. runs a function on the element
3. removes the element from the list with the 'meta_segm.erase'.
and repeats this procedure untill the vector is empty

The problem I have is in the function of step 2. This function uses the
random element (A) (out of step 1) and searches for a second element
(B) based on different criteria. So my function runs actually for two
elements (A and B), instead of only one (A).
Now, I want to translate this in step 3 and remove A and B from the
vector.

I know how to remove A, but I have no idea how to remove B. B is not
necessarly A's neighbour. I thought of searching for it (based on the
same criteria I use to detect it), but I that takes to much time since
I will have to do it for every element then.

Can't you modify your detect procedure, such that it not only figures
out the element in question but also tells you where it was found?

Or you could modify the detect function, such that it doesn't return
the element, but tells you where the element can be found (it returns
the iterator, or end() if not found). The caller of that detect function
would then be in need to lookup the element itself, but this is no
problem since it has an iterator to it.

--
Karl Heinz Buchegger
kb******@gascad.at

[koperenkogel]

Thanks for the advice!

I changed my program. The elements of my array Y do not point anymore
to the vector X, but now have the value of the iterator of X.

Thus:
array Y[nrow][ncol] is an image and the pixels are structures:
struct segment
{ ...
vector <meta_segment>::iterator it_meta_segment;
// It_meta-segm is an iterator of the vector X
...};

My question now is:
Do my iterators stay constant when I remove an element out of the
vector?
e.g.:
If b is an iterator of element B of vector X and I remove another
element A of vector X. Is b than still the iterator for the element B
of vector X or is it an iterator to another element C of vector X?

It might sound a stupid question, but I'm not an experienced C++
programmer.

Thanks again,
Stef

[Howard]

"koperenkogel" <st***************@agr.kuleuven.ac.be> wrote in message
news:11**********************@g14g2000cwa.googlegr oups.com...

Thanks for the advice!

I changed my program. The elements of my array Y do not point anymore
to the vector X, but now have the value of the iterator of X.

Thus:
array Y[nrow][ncol] is an image and the pixels are structures:
struct segment
{ ...
vector <meta_segment>::iterator it_meta_segment;
// It_meta-segm is an iterator of the vector X
...};

My question now is:
Do my iterators stay constant when I remove an element out of the
vector?
e.g.:
If b is an iterator of element B of vector X and I remove another
element A of vector X. Is b than still the iterator for the element B
of vector X or is it an iterator to another element C of vector X?

It might sound a stupid question, but I'm not an experienced C++
programmer.

Thanks again,
Stef

When calling erase for a vector, all iterators referring to items *after*
the one erased will be invalid. If you need to erase two items, you could
erase the one that's later in the vector first, so that then the other
iterator is not invalidated by that erase. If you can arrange things so
that you have both the iterator and its position, that method should work
for you.

-Howard

[koperenkogel]

Ok, thanks.

If I understand it correctly, I can solve the problem if I need to
erase two items. The problem is that I want to do this in an iterative
process. So if I do this the items after the one erased will be
invalid.

What I thus need is a reference, pointer, iterator (I have no idea on
how to call it in this case, but lets say A) that refers to a fixed
element (= that does not change if I erase an element) in my vector. Is
there anything like that, so I can afterwards run something like:

my_vector.erase(A)

Thank you all for your help! It makes a lot clear for me!

Kind regards,
Stef

[Howard]

"koperenkogel" <st***************@agr.kuleuven.ac.be> wrote in message
news:11**********************@o13g2000cwo.googlegr oups.com...

Ok, thanks.

If I understand it correctly, I can solve the problem if I need to
erase two items. The problem is that I want to do this in an iterative
process. So if I do this the items after the one erased will be
invalid.

What I thus need is a reference, pointer, iterator (I have no idea on
how to call it in this case, but lets say A) that refers to a fixed
element (= that does not change if I erase an element) in my vector. Is
there anything like that, so I can afterwards run something like:

my_vector.erase(A)

Thank you all for your help! It makes a lot clear for me!

Kind regards,
Stef

You could try something lke this:

1) First erase the item that's "later" in the list.
2) Then erase the item that's "earlier" in the list. The erase fuction
returns an iterator to the next valid item.
3) Now continue iterating from that point. The index of that next valid
item should be the same as this "earlier" item, since the next valid item
will have moved into its place (at least conceptually).

-Howard

[msalters]

koperenkogel wrote:

Thanks for anwser. I will try to sketch the problem:

I am writing an image segmentation program based on a multi-resolution technique.

How does this look like in C++: I have a vector X (nrow x ncol) and the elements are structures :
struct meta_segment
{ ...
struct segment * group;
// Group is a pointer to an array Y[nrow][ncol]
...};
and array Y[nrow][ncol] is an image and the pixels are structures:
struct segment
{ ...
struct meta_segment * meta_segm;
// Meta-segm is a pointer to the vector
...};

So X and Y both point to eachother.
It's C++, you don't have to repeat the struct before segment when
using the type.
But to be clear, the /types/ segment and meta_segment point to each
other, the two /objects/ X and Y point also point to each other, and
the objects X and Y do /not/ point to other objects of these types
outside of the corresponding arrays? So x[0][0].group points to
/the/ array Y, not /an/ array Y?
Now I want the program to work as follows:
1. Pick a random A out of vector X
2. A->group in X points to pixels a in Y
3. Search the pixels b in Y that are the closest to a. I have written
this, and get the coordinates of b in Y as result.
This is the point where things will get slow. In general, without
supporting datastructures, this is a lineair serach. There are
optimized algorithms for this, but these are pretty specific and
not in standard C++
Now my questions are:
Can I remove B out of X, since I only have a pointer to it? Yes. A vector is contiguous, so you can get the index of an
element by calculating pointer-&*X.begin().
Are the other pointers to elements in X then constant when I remove A
out of X? Or do they change also?

When you remove the Nth element, all elements after it are shifted
by one position. This is a rather expensive copy. vector isn't
designed for this, clearing a vector in this way is O(N*N). OTOH,
your search currently also is O(N*N) so unless you fix both, your
total time will remain O(N*N). This shift will of course cause all
pointers to point to other elements, and the pointer to what used
to be the last element will end up pointing /after/ the elements
of X. You'd have to adjust every pointer in Y. Again, that's O(N)
per removal and O(N*N) in total.

It looks like your datastructure is just not optimal for this.
I think there is no technical reason to remove elements from X.
One esay fix: just keep a vector of pointers into X instead.
Whenever you pick an element, find a pair and "remove" them by
removing these two pointers from the vector of pointers. This
will still be O(N*N) but it's a lot cheaper since X and Y are
not changed, you'll just be shrinking a small vector of pointers.
A list of pointers would have O(1) removal but O(n) random pick
and O(n) finding of the paired pointer, which is just as bad.

Regards,
Michiel Salters

[msalters]

Howard wrote:

"koperenkogel" <st***************@agr.kuleuven.ac.be> wrote in message news:11**********************@g14g2000cwa.googlegr oups.com...

Thanks for the advice!

I changed my program. The elements of my array Y do not point anymore to the vector X, but now have the value of the iterator of X.

.... When calling erase for a vector, all iterators referring to items *after* the one erased will be invalid. If you need to erase two items, you could erase the one that's later in the vector first, so that then the other iterator is not invalidated by that erase. If you can arrange things so that you have both the iterator and its position, that method should work for you.

True. That means that each and every iterator in Y will be invalidated
if you erase the first element of X. It's not just the pair ot
iterators
you're erasing, the iterators you want to keep are also invalidated.

Regards,
Michiel Salters

[koperenkogel]

Ok, thank you very much again. I am learning a lot.

the /types/ segment and meta_segment point to each
other, the two /objects/ X and Y point also point to each other, and
the objects X and Y do /not/ point to other objects of these types
outside of the corresponding arrays? So x[0][0].group points to
/the/ array Y, not /an/ array Y? Indeed the objects segment (X is of this type) and meta_segment (Y is
of this type) point to each other. X points as such to Y and not to any
other object of these types.

When you remove the Nth element, all elements after it are shifted by

one position.
This is a problem for my program. So if I understand it right, my
datastructure is not optimal for this purpose. I will think of using
another, but reorganising everything will take time. But to solve my
problems easily, I could use a new vector Z that consists of pointers
to the original vector X, and run the procedure for Z.

I tried programming that in C++:

/* Declare Z (vector of pointers to vector X) and his associated
iterator */
vector <meta_segment *> Z;
vector <meta_segment *>::iterator it_Z;

/* Assign Z with "pointers to X" */
for(it_X = X.begin(); it_X != X.end(); it_X++ )
{
Z.push_back(&(*it_X));
}

/* I have a fucntion that works with the data of X */
void f_1 (vector <meta_segment>::iterator it_X)
{
...
}

/* Now I want to work with the data of X but by using Z. How do I do
that ??? */
for(it_Z = Z.begin(); it_Z!= Z.end(); it_Z++ )
{
function f_1(*Z[it_Z]);
}

I tried this but it doesn't work. Do I misunderstand the technique or
is my script incorrect? I thought I had to provide the value of Z
(which is the location of X) to the function f_1, but apparently I do
something wrong.

Thanks again in advance!

Kind regards,
Stef

[steflhermitte]

Thank you very much for your help.

I will explain shortly what I am doing. I explained it also in previous
postst to the forum, but here is a short overview.

I am writing an image segmentation program based on a multi-resolution
technique. Multi-resolution segmentation is a bottom up region-merging
technique starting with one-pixel objects. In numerous subsequent
steps, smaller image objects are merged into bigger ones. In each step,
that pair of adjacent image objects is merged which stands for the
smallest growth of the defined heterogeneity. So what happens. I first
merge single pixels into couples. Afterwards I start merging the
couples into groups of four and so on. Once a defined heterogeneity is
reached for an object (=full), it does not participate any longer in
the process till all objects are full.

How does this look like in C++:

Is started with a vector X (nrow x ncol) and the
elements are structures :
struct meta_segment
{ ...
struct segment * group;
// Group is a pointer to an array Y[nrow][ncol]
...};
and array Y[nrow][ncol] is an image and the pixels are structures:
struct segment
{ ...
struct meta_segment * meta_segm;
// Meta-segm is a pointer to the vector X
...};

So X and Y both point to eachother.

Now I wanted the program to work as follows:
1. Pick a random A out of vector X
2. A->group in X points to pixels a in Y
3. Search the pixels b in Y that are the closest to a. I have written
this, and get the coordinates of b in Y as result.
4. b->meta-segm points to B in X
5. Merge A and B (+ a and b) by:
* removing A and B out of X and putting them in another vector C
in X2(using push_back)
* replacing the pointers:
- C->group points to a and b
- a->meta-segm and b->meta-segm point to C
This is done till X is empty, and then the process is repeated for X2
and so on.

The discussion forum proposed to change my array Y so that is does not
point anymore to the vector X, but has the value of the iterator of X.

array Y[nrow][ncol] is an image and the pixels are structures:
struct segment
{ ...
vector <meta_segment>::iterator it_meta_segment;
// It_meta-segm is an iterator of the vector X
...};

Besides, they proposed to use a 2nd vector. This vector Z consists of
pointers to the original vector X. In this way I do not need to remove
elements out of X, but I can remove them out of Z. This must allow me
to keep X constant in size and avoid that my iterators become invalid.
As such I don't get the problems that would occur if I resize my
vector.

In C++:

/* Declare Z (vector of pointers to vector X) and his associated
iterator */
vector <meta_segment *> Z;
vector <meta_segment *>::iterator it_Z;

/* Assign Z with "pointers to X" */
for(it_X = X.begin(); it_X != X.end(); it_X++ )
{
Z.push_back(&(*it_X));
}

/* I have a function that works with the data of X */
void f_1 (meta_segment * it_X)
{
...
/* In this function I wanted to do the assignment of the beginning
of this topic */
}

I hope this explains my problem a bit clearer.

Kind regards,
Stef