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
15  9655 
"David Jones" <da**@ymchwil.NODAMNSPAM.com> wrote in message
news:3f*********************@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
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
"Paul Thompson" <pa**@msdmagic.co.uk> wrote in message
news:bf**********@hercules.btinternet.com... "David Jones" <da**@ymchwil.NODAMNSPAM.com> wrote in message
news:3f*********************@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
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 kb******@gascad.at
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
"David Jones" <da**@ymchwil.NODAMNSPAM.com> wrote in message
news:3f*********************@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
"John Harrison" <jo*************@hotmail.com> wrote in message
news:bf************@ID-196037.news.uni-berlin.de...
"Paul Thompson" <pa**@msdmagic.co.uk> wrote in message
news:bf**********@hercules.btinternet.com... "David Jones" <da**@ymchwil.NODAMNSPAM.com> wrote in message
news:3f*********************@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
you want to use a set or map, not a vector
"David Jones" <da**@ymchwil.NODAMNSPAM.com> wrote in message
news:3f*********************@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
On Thu, 17 Jul 2003 12:48:18 +0100, "David Jones"
<da**@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
"dwrayment" <dw*******@rogers.com> wrote in message
news:tq******************@news01.bloor.is.net.cabl e.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.
On Thu, 17 Jul 2003 14:26:47 -0700, Andrey Tarasevich
<an**************@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
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
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
On Thu, 17 Jul 2003 15:35:50 -0700, Andrey Tarasevich
<an**************@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
"John Dibling" <dib@substitute_my_full_last_name_here.com> wrote in message
news:3m********************************@4ax.com...
| On Fri, 18 Jul 2003 21:47:53 +1000, "Chris \( Val \)"
| <ch******@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
This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: {AGUT2}=IWIK= |
last post by:
Hello all,
It's my fisrt post here and I am feeling a little stupid here, so go easy..
:) (Oh, and I've spent _hours_ searching...)
I am desperately trying to read in an ASCII...
|
by: luigi |
last post by:
Hi,
I am trying to speed up the perfomance of stl vector by
allocating/deallocating blocks of memory manually. one version of the
code crashes when I try to free the memory. The other version...
|
by: Forecast |
last post by:
I run the following code in UNIX compiled by g++ 3.3.2 successfully.
: // proj2.cc: returns a dynamic vector and prints out at main~~
: //
: #include <iostream>
: #include <vector>
:
: using...
|
by: Adam Hartshorne |
last post by:
Hi All,
I have the following problem, and I would be extremely grateful if
somebody would be kind enough to suggest an efficient solution to it.
I create an instance of a Class A, and...
|
by: Bob |
last post by:
Here's what I have:
void miniVector<T>::insertOrder(miniVector<T>& v,const T& item)
{
int i, j;
T target;
vSize += 1;
T newVector;
newVector=new T;
|
by: Ross A. Finlayson |
last post by:
I'm trying to write some C code, but I want to use C++'s std::vector.
Indeed, if the code is compiled as C++, I want the container to
actually be std::vector, in this case of a collection of value...
|
by: Martin Jørgensen |
last post by:
Hi,
I get this using g++:
main.cpp:9: error: new types may not be defined in a return type
main.cpp:9: note: (perhaps a semicolon is missing after the definition
of 'vector')
main.cpp:9:...
|
by: Sanjay Kumar |
last post by:
Folks,
I am getting back into C++ after a long time and I have
this simple question: How do pyou ass a STL container
like say a vector or a map (to and from a function) ?
function:
...
|
by: zl2k |
last post by:
hi, there
I am using a big, sparse binary array (size of 256^3). The size may be
changed in run time. I first thought about using the bitset but found
its size is unchangeable. If I use the...
|
by: toton |
last post by:
Hi,
I want to have a vector like class with some additional functionality
(cosmetic one). So can I inherit a vector class to add the addition
function like,
CorresVector : public...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
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,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
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,...
|
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...
|
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...
|
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...
| |
