473,735 Members | 8,833 Online

# Vector question

Hi, everyone.

Given a vector<int>, what is the fastest way to find out whether there is a
repeated element in it? The result is just "true" or "false". Thanks.

Kitty
Jul 22 '05 #1
16 2732
In article <41**********@r ain.i-cable.com>, Kitty <No spam> wrote:

Given a vector<int>, what is the fastest way to find out whether there is a
repeated element in it? The result is just "true" or "false". Thanks.

I'd construct an empty set<int>, then walk through the vector, processing
each element in turn. If the element is in the set already, stop and
return 'true'; otherwise insert the element into the set and continue.
If you reach the end of the vector without finding any duplicates, return
'false'.

--
Jon Bell <jt*******@pres by.edu> Presbyterian College
Dept. of Physics and Computer Science Clinton, South Carolina USA
Jul 22 '05 #2
"Kitty" <No spam> wrote in message news:41******** **@rain.i-cable.com...
Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks.

Sounds like an interview question. There are many answers, each with
tradeoffs. Jon's method uses additional memory, but is fast time wise (time
is N*O(lg(N), space is O(N)), and easy to write too -- that's important too
because software that is easier to write and maintain pays off long term,
though this rarely comes up in interviews (though it should). You can also
not use additional memory, but sacrifice time (time would be O(N^2), space
is O(1)). And each method has its own varations, such as set or hashtable,
type of hash function if a hash, set or sorted vector, vector or list, etc,
etc.
Jul 22 '05 #3
In a similar problem, I use a different approach due to the fact that
jon's solution is not an option as it consumes too much memmory.

I use a modified qsort and in the comparation part if two sucessive
elements are the same, I return true. This is slow with small lists but
fast with huge datasets (30.000+ as in my application takes about 100ms)

/Casper

Kitty wrote:
Hi, everyone.

Given a vector<int>, what is the fastest way to find out whether there is a
repeated element in it? The result is just "true" or "false". Thanks.

Kitty

Jul 22 '05 #4
"Casper" <ca****@jbr.d k> wrote in message news:GFeYc.7339 6
In a similar problem, I use a different approach due to the fact that
jon's solution is not an option as it consumes too much memmory.

I use a modified qsort and in the comparation part if two sucessive
elements are the same, I return true. This is slow with small lists but
fast with huge datasets (30.000+ as in my application takes about 100ms)

A good solution, I think the fastest possible without using extra space.
But it changes the original vector. Can you think of a way to do it without
changing the original?
Jul 22 '05 #5
"Kitty" <No spam> wrote:
Hi, everyone.

Given a vector<int>, what is the fastest way to find out whether there is
a repeated element in it? The result is just "true" or "false". Thanks.

Kitty

Here are three obvious ways of using standard algorithms. These solutions
have the advantage that they are easy to understand. The second one could
avoid copying if it was allowed to modify the sequence in the first place.

#include <vector>
#include <set>
#include <iostream>

template < typename ConstIter >
bool has_dublicates_ a ( ConstIter from, ConstIter to ) {
typedef typename std::iterator_t raits< ConstIter >::value_type value_type;
typedef typename std::set< value_type > set_type;
typedef typename set_type::size_ type size_type;

size_type i = 0;
set_type s;
for ( ConstIter iter = from; iter != to; ++iter ) {
++ i;
s.insert( *iter );
// this test could also be done after the loop:
if ( s.size() != i ) {
return( true );
}
}
return( false );
}

template < typename ConstIter >
bool has_dublicates_ b ( ConstIter from, ConstIter to ) {
typedef typename std::iterator_t raits< ConstIter >::value_type value_type;
typedef typename std::vector< value_type > vector_type;

vector_type v ( from, to );
std::sort( v.begin(), v.end() );
return( std::adjacent_f ind( v.begin(), v.end() ) != v.end() );
}

int main( int argn, char ** args ){
std::vector< int > a;
std::vector< int > b;
for ( int i = 0; i < 10; ++i ) {
a.push_back( i );
b.push_back( i ); b.push_back( i );
}

std::cout << has_dublicates_ a( a.begin(), a.end() )
<< " "
<< has_dublicates_ a( b.begin(), b.end() ) << "\n";
std::cout << has_dublicates_ b( a.begin(), a.end() )
<< " "
<< has_dublicates_ b( b.begin(), b.end() ) << "\n";
}

As for speed, I would suggest a method based on the "partition by exchange"
idea underlying quicksort, possibly modified like introsort to avoid O(N^2)
worst case runtime. But that idea has been mentioned in another posting
Best

Kai-Uwe Bux
Jul 22 '05 #6

"Kitty" <No spam> wrote in message news:41******** **@rain.i-cable.com...
Hi, everyone.

Given a vector<int>, what is the fastest way to find out whether there is a
repeated element in it? The result is just "true" or "false". Thanks.

Kitty

See the thread titled "If vector contains only different elements" at
--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn
Jul 22 '05 #7
Siemel Naran wrote:
"Casper" <ca****@jbr.d k> wrote in message news:GFeYc.7339 6
In a similar problem, I use a different approach due to the fact that
jon's solution is not an option as it consumes too much memmory.

I use a modified qsort and in the comparation part if two sucessive
elements are the same, I return true. This is slow with small lists but
fast with huge datasets (30.000+ as in my application takes about 100ms)
A good solution, I think the fastest possible without using extra space.

I agree that this is probably the fastest solution using comparisons. Given
that the question was for vector<int>, there could be a linear time
solution. Here is a (messy) draft of something like that. The idea is to do
partition by exchange based on the even/odd distinction (note that
dublicates have the same parity). So in one pass, we put all the even
elements to the left of all the odd elements. During the same pass, shift
down by one bit. Now, we return true if there is a dublicate in the left
segment or in the right segment. Farther down in the recursion, we can
sometimes return true just based on the length of the segment: if we have
shifted so many times that all values are in [0..15], then any segment of
length 17 is bound to contain dublicates. The run time for the worst case
should be O( N * bit_length<int> ).
#include <vector>
#include <iostream>
#include <kubux/sequenceio>

typedef std::vector< unsigned int > Uvector;

void print_range ( u_int* from, u_int* to ) {
std::cerr << "[ ";
while ( from <= to ) {
std::cerr << *from << " ";
++from;
}
std::cerr << "]";
}

bool has_dublicates_ helper ( u_int* from, u_int* to, u_int max ) {
// WARNING, range is closed: [from,to]
print_range( from, to );
if ( to <= from ) {
return( false );
}
if ( max < to - from ) {
return( true );
}
u_int* low = from;
u_int* high = to;
while ( true ) {
while ( ( low < high ) && ( *low % 2 == 0 ) ) {
*low >>= 1;
++low;
}
while ( ( low < high ) && ( *high % 2 != 0 ) ) {
*high >>= 1;
--high;
}
// either ( low == high ) or ( *high is even )
if ( low < high ) {
// *low is odd and *high is even
std::swap( *low, *high );
} else {
break;
}
}
std::cerr << std::endl;
print_range( from, to );
std::cerr << std::endl;
// low == high;
if ( *low % 2 == 0 ) {
*low >>= 1;
return( has_dublicates_ helper( from, low, max >> 1 )
||
has_dublicates_ helper( high+1, to, max >>1 ) );
} else {

*low >>= 1;
return( has_dublicates_ helper( from, low-1, max >> 1 )
||
has_dublicates_ helper( high, to, max >>1 ) );
}
}

bool has_dublicates ( Uvector u_vect ) {
// this makes a copy
return( has_dublicates_ helper( &u_vect[0], &u_vect[ u_vect.size()-1 ],
std::numeric_li mits< unsigned int >::max() ) );
}

int main( int argn, char ** args ){
Uvector a;
Uvector b;
for ( int i = 0; i < 10; ++i ) {
a.push_back( i );
b.push_back( i ); b.push_back( i );
}

std::cout << has_dublicates( a )
<< " "
<< has_dublicates( b )
<< "\n";
}

But it changes the original vector. Can you think of a way to do it
without changing the original?

Same here, I do not see how to avoid that.
Best

Kai-Uwe Bux
Jul 22 '05 #8

"Siemel Naran" <Si*********@RE MOVE.att.net> wrote in message
news:GS******** *************@b gtnsc05-news.ops.worldn et.att.net...
"Casper" <ca****@jbr.d k> wrote in message news:GFeYc.7339 6
In a similar problem, I use a different approach due to the fact that
jon's solution is not an option as it consumes too much memmory.

I use a modified qsort and in the comparation part if two sucessive
elements are the same, I return true. This is slow with small lists but
fast with huge datasets (30.000+ as in my application takes about 100ms)
A good solution, I think the fastest possible without using extra space.
But it changes the original vector. Can you think of a way to do it

without changing the original?
If time is not an issue, perhaps this will do?

bool has_duplicates( vector<int> const& i_Ints)
{
for (
std::vector<int >::const_iterat or cit = i_Ints.begin();
cit != i_Ints.end();
)
{
int i = *cit++;
std::vector<int >::const_iterat or jit = cit;
while (jit != i_Ints.end())
if (*jit++ == i)
return true;
}
return false;
}
cheers,

Jul 22 '05 #9
The most important thing is to keep elements in the same positions after
processing. That is sorting-like algorithm is not allowed.
"Kitty" <No spam> ¦b¶l¥ó news:41******** **@rain.i-cable.com ¤¤¼¶¼g...
Hi, everyone.

Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks.

Kitty

Jul 22 '05 #10

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

### Similar topics

 4 11431 by: Jessica | last post by: Hi, I do not have a lot of experience with STL and I hope some of you might be able to help me on this seemingly elementary question. I have a vector of doubles (v1). I am trying to copy the values to a 2D vector, of which every vector has the same length. I tried the following but I get a "System.NullReferenceException" error when I ran it. 10 7077 by: Stefan Höhne | last post by: Hi, as I recon, std::vector::clear()'s semantics changed from MS VC++ 6.0 to MS' DOT.NET - compiler. In the 6.0 version the capacity() of the vector did not change with the call to clear(), in DOT.NET the capacity() is reduced to 0. 12 3158 by: No Such Luck | last post by: Hi All: I'm not sure if this is the right place to ask this question, but I couldn't find a more appropriate group. This is more of a theory question regarding an algorithm implemented in C, not necessarily a C language question. I'm trying to break up a vector into an arbitrary number of subvectors, equal (or as near to equal) in size as possible. My problem occurs when the vector is not evenly divisible by the number of subvectors... 24 2954 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 vector{ public: void addCorres(Corres& c); //it do little more than push_back function. } 2 3321 by: danielhdez14142 | last post by: Some time ago, I had a segment of code like vector's and used push_back to get them inside example. I got a segmentation fault which I resolved by doing vector()); 9 3758 by: Jess | last post by: Hello, I tried to clear a vector "v" using "v.clear()". If "v" contains those objects that are non-built-in (e.g. string), then "clear()" can indeed remove all contents. However, if "v" contains built-in types (e.g. int), then "clear()" doesn't remove anything at all. Why does "clear()" have this behaviour? Also, when I copy one vector "v1" from another vector "v2", with "v1" longer than "v2" (e.g. "v1" has 2 elements and "v2" has... 7 3894 by: nw | last post by: Hi, We've been having a discussion at work and I'm wondering if anyone here would care to offer an opinion or alternative solution. Aparently in the C programming HPC community it is common to allocate multidimentional arrays like so: int *v_base = (int *) malloc(1000000*sizeof(int)); int **v = (int **) malloc(1000*sizeof(int *)); 6 11616 by: jmsanchezdiaz | last post by: CPP question: if i had a struct like "struct str { int a; int b };" and a vector "std::vector < str test;" and wanted to push_back a struct, would i have to define the struct, fill it, and then push_back it, or could i pushback the two ints directly somehow? Thanks for all. 13 1924 by: prasadmpatil | last post by: I am new STL programming. I have a query regarding vectors. If I am iterating over a vector using a iterator, but do some operations that modify the size of the vector. Will the iterator recognize this? I wrote the following program to test this out. #include #include #include 6 7380 by: Mr. K.V.B.L. | last post by: I want to start a map with keys but an empty vector. Not sure what the syntax is here. Something like: map)); MapVector.insert(make_pair("string2", new vector)); MapVector.insert(make_pair("string3", new vector)); 0 8962 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 9463 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... 1 9251 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 9200 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... 0 8201 by: agi2029 | last post by: Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea... 0 6049 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 4559 by: TSSRALBI | last post by: Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls... 0 4822 by: adsilva | last post by: A Windows Forms form does not have the event Unload, like VB6. What one acts like? 3 2188 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...