443,889 Members | 1,358 Online Need help? Post your question and get tips & solutions from a community of 443,889 IT Pros & Developers. It's quick & easy.

# Remove elements pairwise from vector

 P: n/a Dear cpp-ians, I am working with a vector of structures. vector 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 Jul 23 '05 #1
11 Replies

 P: n/a koperenkogel wrote: Dear cpp-ians, I am working with a vector of structures. vector 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 Jul 23 '05 #2

 P: n/a 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 Jul 23 '05 #3

 P: n/a koperenkogel wrote: Dear cpp-ians, I am working with a vector of structures. vector 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 Jul 23 '05 #4

 P: n/a 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 ::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 Jul 23 '05 #5

 P: n/a "koperenkogel" 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 ::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 Jul 23 '05 #6

 P: n/a 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 Jul 23 '05 #7

 P: n/a "koperenkogel" 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 Jul 23 '05 #8

 P: n/a 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.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 Jul 23 '05 #9

 P: n/a Howard wrote: "koperenkogel" 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 Jul 23 '05 #10

 P: n/a 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.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 Z; vector ::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 ::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 Jul 23 '05 #11

 P: n/a 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 ::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 Z; vector ::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 Jul 23 '05 #12

### This discussion thread is closed

Replies have been disabled for this discussion. 