| Topic: |
DEVELOP > c-Plus-Plus |
| User: |
"David Jones" |
| Date: |
17 Jul 2003 06:48:18 AM |
| Object: |
Q: STL vector |
Hi
I have a list of values stored in a vector e.g.
std::vector<int> x;
x[0] = 1;
x[1] = 4;
x[2] = 2;
x[3] = 4;
x[4] = 6;
x[5] = 1;
x[6] = 4;
Can anybody suggest an efficient way to iterate through the vector so that
the vector only contains unique values e.g. only one instance of 4 occurs in
the vector. That is, the new vector, once processed, would be:
{1,4,2,6}
Thanks in advance
David
.
|
|
| User: "Paul Thompson" |
|
| Title: Re: STL vector |
17 Jul 2003 06:51:08 AM |
|
|
"David Jones" <dave@ymchwil.NODAMNSPAM.com> wrote in message
news:3f168cf3$0$961$cc9e4d1f@news.dial.pipex.com...
Hi
I have a list of values stored in a vector e.g.
std::vector<int> x;
x[0] = 1;
x[1] = 4;
x[2] = 2;
x[3] = 4;
x[4] = 6;
x[5] = 1;
x[6] = 4;
Can anybody suggest an efficient way to iterate through the vector so that
the vector only contains unique values e.g. only one instance of 4 occurs
in
the vector. That is, the new vector, once processed, would be:
{1,4,2,6}
Look up std::sort and std::unique in an STL reference. Example:
std::sort(x.begin(), x.end());
std::unique(x.begin(), x.end());
You'll need to include <algorithm> first.
HTH,
Paul
.
|
|
|
| User: "John Harrison" |
|
| Title: Re: STL vector |
17 Jul 2003 07:14:55 AM |
|
|
"Paul Thompson" <paul@msdmagic.co.uk> wrote in message
news:bf62jb$isj$1@hercules.btinternet.com...
"David Jones" <dave@ymchwil.NODAMNSPAM.com> wrote in message
news:3f168cf3$0$961$cc9e4d1f@news.dial.pipex.com...
Hi
I have a list of values stored in a vector e.g.
std::vector<int> x;
x[0] = 1;
x[1] = 4;
x[2] = 2;
x[3] = 4;
x[4] = 6;
x[5] = 1;
x[6] = 4;
Can anybody suggest an efficient way to iterate through the vector so
that
the vector only contains unique values e.g. only one instance of 4
occurs
in
the vector. That is, the new vector, once processed, would be:
{1,4,2,6}
Look up std::sort and std::unique in an STL reference. Example:
std::sort(x.begin(), x.end());
std::unique(x.begin(), x.end());
You'll need to include <algorithm> first.
HTH,
Paul
Except of course std::unique, like any other STL algorithm, will not
actually erase the items from the vector. You need to do
ox.erase(std::unique(ox.begin(), ox.end()), ox.end());
for that.
john
.
|
|
|
| User: "Paul Thompson" |
|
| Title: Re: STL vector |
17 Jul 2003 08:03:27 AM |
|
|
"John Harrison" <john_andronicus@hotmail.com> wrote in message
news:bf63sj$bgepm$1@ID-196037.news.uni-berlin.de...
"Paul Thompson" <paul@msdmagic.co.uk> wrote in message
news:bf62jb$isj$1@hercules.btinternet.com...
"David Jones" <dave@ymchwil.NODAMNSPAM.com> wrote in message
news:3f168cf3$0$961$cc9e4d1f@news.dial.pipex.com...
Hi
I have a list of values stored in a vector e.g.
std::vector<int> x;
x[0] = 1;
x[1] = 4;
x[2] = 2;
x[3] = 4;
x[4] = 6;
x[5] = 1;
x[6] = 4;
Can anybody suggest an efficient way to iterate through the vector so
that
the vector only contains unique values e.g. only one instance of 4
occurs
in
the vector. That is, the new vector, once processed, would be:
{1,4,2,6}
Look up std::sort and std::unique in an STL reference. Example:
std::sort(x.begin(), x.end());
std::unique(x.begin(), x.end());
You'll need to include <algorithm> first.
HTH,
Paul
Except of course std::unique, like any other STL algorithm, will not
actually erase the items from the vector. You need to do
ox.erase(std::unique(ox.begin(), ox.end()), ox.end());
Absolutely right - I was just about to pop out for lunch, but thought I'd
answer David's query. As soon as I left the office, I could have kicked
myself!
Paul
.
|
|
|
|
|
| User: "David Jones" |
|
| Title: Re: STL vector |
17 Jul 2003 07:12:31 AM |
|
|
Many thanks for your prompt reply Paul. Very useful!
To simplify the problem I've specified a vector of integers. However, as
with most things in life, the true problem I'm trying to solve is a little
bit more complex. The vector I have is not a vector of integers but a vector
of objects which have a member identifying a name i.e. each object has a
char member. The elements of the vector have this member set as "A", "B"
etc. I want to remove elements from the vector which have identical "names"
i.e. only one vector will, for example, have name "C".
I guess that this is the same type of problem, hence my initial post, but a
little more complex.
Any advice will be most appreciated.
David
.
|
|
|
| User: "Paul Thompson" |
|
| Title: Re: STL vector |
17 Jul 2003 08:02:12 AM |
|
|
"David Jones" <dave@ymchwil.NODAMNSPAM.com> wrote in message
news:3f1692a1$0$962$cc9e4d1f@news.dial.pipex.com...
Many thanks for your prompt reply Paul. Very useful!
I can't actually see my reply on the news server, but I was wrong on two
counts. You need to pass the result of std::unique to erase thus:
std::sort(x.begin(), x.end());
x.erase(std::unique(x.begin(), x.end()), x.end());
That's one.
Two: Your example had the result not in ascending order; whereas if you
follow my advice, it will be.
Other than that, yes, std::unique is very useful.
To simplify the problem I've specified a vector of integers. However, as
with most things in life, the true problem I'm trying to solve is a little
bit more complex. The vector I have is not a vector of integers but a
vector
of objects which have a member identifying a name i.e. each object has a
char member. The elements of the vector have this member set as "A", "B"
etc. I want to remove elements from the vector which have identical
"names"
i.e. only one vector will, for example, have name "C".
I guess that this is the same type of problem, hence my initial post, but
a
little more complex.
Any advice will be most appreciated.
I think the other replies handle the rest quite well.
Paul
.
|
|
|
|
| User: "Karl Heinz Buchegger" |
|
| Title: Re: STL vector |
17 Jul 2003 07:27:28 AM |
|
|
David Jones wrote:
Many thanks for your prompt reply Paul. Very useful!
To simplify the problem I've specified a vector of integers. However, as
with most things in life, the true problem I'm trying to solve is a little
bit more complex. The vector I have is not a vector of integers but a vector
of objects which have a member identifying a name i.e. each object has a
char member. The elements of the vector have this member set as "A", "B"
etc. I want to remove elements from the vector which have identical "names"
i.e. only one vector will, for example, have name "C".
No problem.
All you need is a comparison function (or a functor)
which can be feed to sort() and unique(). This comparison
function determines what it means for 2 objects to be less.
Or you could add an operator< to your class which does the same.
--
Karl Heinz Buchegger
kbuchegg@gascad.at
.
|
|
|
|
| User: "Peter Gregory" |
|
| Title: Re: STL vector |
17 Jul 2003 08:28:03 AM |
|
|
David Jones wrote:
Many thanks for your prompt reply Paul. Very useful!
To simplify the problem I've specified a vector of integers. However, as
with most things in life, the true problem I'm trying to solve is a little
bit more complex. The vector I have is not a vector of integers but a
vector of objects which have a member identifying a name i.e. each object
has a char member. The elements of the vector have this member set as "A",
"B" etc. I want to remove elements from the vector which have identical
"names" i.e. only one vector will, for example, have name "C".
I guess that this is the same type of problem, hence my initial post, but
a little more complex.
Any advice will be most appreciated.
David
Overload the < operator so sort can work, and the == operator to define
equality and I think you're away.
Pete
.
|
|
|
|
| User: "dwrayment" |
|
| Title: Re: STL vector |
17 Jul 2003 09:30:49 AM |
|
|
you want to use a set or map, not a vector
"David Jones" <dave@ymchwil.NODAMNSPAM.com> wrote in message
news:3f1692a1$0$962$cc9e4d1f@news.dial.pipex.com...
Many thanks for your prompt reply Paul. Very useful!
To simplify the problem I've specified a vector of integers. However, as
with most things in life, the true problem I'm trying to solve is a little
bit more complex. The vector I have is not a vector of integers but a
vector
of objects which have a member identifying a name i.e. each object has a
char member. The elements of the vector have this member set as "A", "B"
etc. I want to remove elements from the vector which have identical
"names"
i.e. only one vector will, for example, have name "C".
I guess that this is the same type of problem, hence my initial post, but
a
little more complex.
Any advice will be most appreciated.
David
.
|
|
|
| User: "Chris Theis" |
|
| Title: Re: STL vector |
17 Jul 2003 10:21:38 AM |
|
|
"dwrayment" <dwrayment@rogers.com> wrote in message
news:tqyRa.15632$Ci2.1158@news01.bloor.is.net.cable.rogers.com...
you want to use a set or map, not a vector
Just using a set or map will not be sufficient. The OP still has to overload
operator < for sorting objects rather than integers like in his first simple
example.
Regards
Chris
P.S.: Please don't top post.
.
|
|
|
|
|
|
|
| User: "Agent Mulder" |
|
| Title: Re: STL vector |
17 Jul 2003 06:17:35 PM |
|
|
I have a list of values stored in a vector e.g.
std::vector<int> x;
x[0] = 1;
x[1] = 4;
x[2] = 2;
x[3] = 4;
x[4] = 6;
x[5] = 1;
x[6] = 4;
Can anybody suggest an efficient way to iterate through the vector so that
the vector only contains unique values e.g. only one instance of 4 occurs in
the vector. That is, the new vector, once processed, would be:
{1,4,2,6}
DJ> However, as with most things in life, the true problem I'm trying
DJ> to solve is a little bit more complex. The vector I have is not a
DJ> vector of integers but a vector of objects which have a member
DJ> identifying a name i.e. each object has a char member. The elements
DJ> of the vector have this member set as "A", "B" etc. I want to
DJ> remove elements from the vector which have identical "names"
DJ> i.e. only one vector will, for example, have name "C".
The way you fill your vector is wrong. The vector x is
empty, so the elements you're trying to assign to don't
exist.
#include <iostream.h>
#include <list.h>
#include <set.h>
#include <vector.h>
#include <algorithm.h>
class MyObject
{
public:char name;
public:MyObject(const char&a='A'){name=a;}
};
bool operator<(const MyObject&a,const MyObject&b){return a.name<b.name;}
void show(const MyObject&a){cout<<'\t'<<a.name;}
void debug(const vector<MyObject>&a)
{
cout<<"\nVector contains "<<a.size()<<" elements: ";
for_each(a.begin(),a.end(),show);
}
int main(int argv,char**argc)
{
vector<MyObject>x;
x.push_back(MyObject('A'));
x.push_back(MyObject('D'));
x.push_back(MyObject('B'));
x.push_back(MyObject('D'));
x.push_back(MyObject('F'));
x.push_back(MyObject('A'));
x.push_back(MyObject('D'));
debug(x);
set<MyObject>s(x.begin(),x.end());
x.resize(s.size());
copy(s.begin(),s.end(),x.begin());
debug(x);
}
-X
.
|
|
|
|
| User: "John Dibling" |
|
| Title: Re: Q: STL vector |
17 Jul 2003 09:37:56 AM |
|
|
On Thu, 17 Jul 2003 12:48:18 +0100, "David Jones"
<dave@ymchwil.NODAMNSPAM.com> wrote:
Can anybody suggest an efficient way to iterate through the vector so that
the vector only contains unique values
You did not actually say that you want to retain the original order of
the elements in the vector; but I presume by your wording that you do.
That is, you don't want to sort the vector. The problem here of
course is the fact that the STL unique algorithm requires that the
collection it operates on is sorted. This is how it can guarantee a
reasonable time complexity. If you don't mind sorting the vector,
just use unique, like this:
x.erase( std::unique(x.begin(),x.end()), x.end() );
Now, if you don't want to sort the vector, or if you want to somehow
retain the original sort order, things become more complicated. You
have to make a decision: do you want to make a temporary sorted
vector, and unique it? Or do you want to walk the unsorted vector
over and over, looking for duplicate values? You can come up with all
sorts of sophisticated algorithms to accomplish your goals, but all
these algorithms rely on one of the above two possibilities as the key
to making it work. If someone can make an alternate suggestion that
doesn't use one of these two keys, I'd love to hear it.
Personally, unless I have a compelling reason not to, I choose the
logically simpler mechanism -- walking the vector over and over. It's
not blazingly efficient, but unless your requirements are extreme, it
will probably give you the best cost-reward ratio. Here is some code:
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>
int main()
{
std::vector<int> x;
x.push_back(1);
x.push_back(4);
x.push_back(2);
x.push_back(4);
x.push_back(6);
x.push_back(1);
x.push_back(4);
x.erase( std::unique(x.begin(),x.end()), x.end() );
std::vector<int>::iterator it;
for( it = x.begin(); it != x.end(); ++it )
{
x.erase( std::remove(it+1, x.end(), *it), x.end() );
}
for( it = x.begin(); it != x.end(); ++it )
std::cout << "[" << std::distance(x.begin(),it)+1 <<
"] " << *it << std::endl;
return 1;
}
</dib>
John Dibling
email: dib@substitute_my_full_last_name_here.com
Witty banter omitted for your protection
.
|
|
|
| User: "Chris \ Val " |
|
| Title: Re: Q: STL vector |
19 Jul 2003 06:09:43 AM |
|
|
"John Dibling" <dib@substitute_my_full_last_name_here.com> wrote in message
news:3m0ghv4q9lvlm59ops84rrofpvc4cndirl@4ax.com...
| On Fri, 18 Jul 2003 21:47:53 +1000, "Chris \( Val \)"
| <chrisval@bigpond.com.au> wrote:
|
| >
| >Anyway, here is a sample for you to scrutinise :-), and hopefully
| >the OP can make some use of it:
| >
| [snip]
| > while( Idx != V.end() )
| > {
| > std::vector<T>::iterator Pos( std::find( V.begin(), Idx, *Idx ) );
| > ( Pos == Idx ) ? ++Idx : Idx = V.erase( Idx );
| > }
| > }
| [snip]
|
| The code snippet above is the kay to your algorithm. This relies on
| the iterative technique I mentioned in my original reply to the OP. I
| think the method is fine; in fact, I generally use the same technique
| unless I am compelled not to for whatever reason. I cannot criticize
| the general method.
|
| On the other hand, if you would like me to constructively criticize
| the *style* (which I know is always dangerous), I would offer the
| following.
|
| <OPINION>
[snip]
Thanks for your opinion, and another point of view.
My sample wasn't meant to mimic the generic algorithms
used, however, I will study your example.
Cheers.
Chris Val
.
|
|
|
|
|
| User: "John Dibling" |
|
| Title: Re: Q: STL vector |
17 Jul 2003 05:01:47 PM |
|
|
On Thu, 17 Jul 2003 14:26:47 -0700, Andrey Tarasevich
<andreytarasevich@hotmail.com> wrote:
Firstly, this solution is not immediately implementable in iterator form.
What? Please explain this statement.
</dib>
John Dibling
email: dib@substitute_my_full_last_name_here.com
Witty banter omitted for your protection
.
|
|
|
| User: "Andrey Tarasevich" |
|
| Title: Re: Q: STL vector |
17 Jul 2003 05:35:50 PM |
|
|
John Dibling wrote:
...
Firstly, this solution is not immediately implementable in iterator form.
What? Please explain this statement.
...
The straightforward approach to implementing the
'std::sort'+'std::unique' variant in form of an iterator would be
creating and iterating a copy of the original vector, which is not
exactly the same as iterating the original vector itself. Of course,
this problem can be solved by some additional efforts. That's why I said
that it is "not _immediately_ implementable".
--
Best regards,
Andrey Tarasevich
Brainbench C and C++ Programming MVP
.
|
|
|
| User: "John Dibling" |
|
| Title: Re: Q: STL vector |
18 Jul 2003 09:24:25 AM |
|
|
On Thu, 17 Jul 2003 15:35:50 -0700, Andrey Tarasevich
<andreytarasevich@hotmail.com> wrote:
John Dibling wrote:
...
Firstly, this solution is not immediately implementable in iterator form.
What? Please explain this statement.
...
The straightforward approach to implementing the
'std::sort'+'std::unique' variant in form of an iterator would be
creating and iterating a copy of the original vector, which is not
exactly the same as iterating the original vector itself. Of course,
this problem can be solved by some additional efforts. That's why I said
that it is "not _immediately_ implementable".
Well, if you are willing to sort the original vector (which I believe
the OP is *not*, even tho this wasn't stated), then there is no need
to copy elements to a temporary vector. In fact, doing so is the
Wrong Thing.
Aside from that, in industrial code I think you would agree that
effort is required to accomplish anything in a robust manner.
</dib>
John Dibling
email: dib@substitute_my_full_last_name_here.com
Witty banter omitted for your protection
.
|
|
|
|
|
|
|
Related Articles |
|
|
