473,851 Members | 2,297 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Remove elements pairwise from vector

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.eras e'.
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 2755

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.eras e'.
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
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
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.eras e'.
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
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

Jul 23 '05 #5

"koperenkog el" <st************ ***@agr.kuleuve n.ac.be> wrote in message
news:11******** **************@ g14g2000cwa.goo glegroups.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


Jul 23 '05 #6
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

"koperenkog el" <st************ ***@agr.kuleuve n.ac.be> wrote in message
news:11******** **************@ o13g2000cwo.goo glegroups.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

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

Jul 23 '05 #9

Howard wrote:
"koperenkog el" <st************ ***@agr.kuleuve n.ac.be> wrote in message news:11******** **************@ g14g2000cwa.goo glegroups.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

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
2571
by: Yngve | last post by:
Hi! I have a (newbie) problem wich i would become glad if someone could help me with. I have a Vector of pointers to instances of another class. I would like to remove a position in the middle of the vector. I am not using iterators at the moment, but if i had i think that i could have used "erase". This is my code now:
6
4962
by: Arne Claus | last post by:
Hi If've just read, that remove() on a list does not actually remove the elements, but places them at the end of the list (according to TC++STL by Josuttis). It also says, that remove returns a new, logical end pointer, so that the following myList::iterator end = myListObj.remove(myInt); myListObj.erase(end, myListObj.end()); is possible and removes the "invalid" items at the end of the list.
7
2518
by: Alan | last post by:
Hi. I have programmed in C++ before, but I`m a couple of years out of practice. I am seeking some advice on getting started on a quickie project. . . . I have to read a 54MB text file and do a pairwise comparison among 2500 items or so in the file. Each of those items have to be compared to every other item. Many of the comparison will only require comparing one field of the items. I will probably sort on this field before I do the...
5
2656
by: Wing | last post by:
Hello, I am thinking an efficient way to remove all the elements (says they are less than 10) from a container vector<int>. Any suggestion? Thank you.
6
3409
by: happyvalley | last post by:
Hi, I want to remove some elements from a vector, the following code doesn't work, seems it doesn't allow me to remove an element when iterating the vector. (make sense), just wonder, how to do this? thank vector<intIntVec; vector<int>::iterator intIterator; for(int i=0; i<10;i++) IntVec.push_back(i);
3
2870
by: groups | last post by:
This small piece of code is troubling me.. is there anything wrong with it?? After calling this method the contents ot the input vector are completely screwed.. (CCountedCIG_CountZero() applies only to a few elements in the vector) void UElementVector::ClearZeroCountElements(vector<CCountedCIG*> &ioItemVec) { vector<CCountedCIG*>::iterator new_end = remove_if(ioItemVec.begin(),
1
2090
by: Alan | last post by:
I am wondering if anyone has any better idea of how to approach this problem than I do. . . . I have a vector of items (data). I have to do a pairwise comparison of each item to each other item and apply logic to see if one should be deleted. In the past I have done this using for statements, like: for (int i = 0; i < input_vector.size(); i++) for (int j = i; i < input_vector.size(); j++)
7
1668
by: mohammaditraders | last post by:
Write a program which overloads a binary Minus (+) operator, The program will contain a class Matrix, This class will contain a private data member Array which store int values. The class will further contain a Default constructor, get() function which takes values for array from the user and also contain a Display function witch display the array on the screen, In main function create three objects Mat1, Mat2, Mat3 of this class, first...
2
2388
by: Angus | last post by:
Hello I have a vector<int(aRemovecoll) which is a list of the indexes to be removed from another vector. The other vecotr contains an object - I will call it SomeObject. So the other vecotr is a vector<SomeObject>. I have created a function like this so far: UINT uNumElements = aRemoveColl.GetSize();
0
9895
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
11011
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10670
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10725
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10352
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
7900
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
7072
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5931
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
3
3178
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.