By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,418 Members | 1,094 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,418 IT Pros & Developers. It's quick & easy.

If vector contains only different elements

P: n/a
Here is some function that detects if a vector contains only different elements

bool vector_contains_only_different_elements (const vector<int>& v)
{
for (int i = 0; i < v.size(); i++)
{
if (count (v.begin() + i + 1, v.end(), v[i]) >= 1) return false;
}
return true;
}
Is there more simple way to do the same thing?

--
Alex Vinokur
mailto:al****@connect.to
http://mathforum.org/library/view/10978.html

Jul 22 '05 #1
Share this Question
Share on Google+
14 Replies


P: n/a

"Alex Vinokur" <al****@big.foot.com> wrote in message
news:c7*********@news.f.de.plusline.net...
Here is some function that detects if a vector contains only different elements
bool vector_contains_only_different_elements (const vector<int>& v)
{
for (int i = 0; i < v.size(); i++)
{
if (count (v.begin() + i + 1, v.end(), v[i]) >= 1) return false;
}
return true;
}
Is there more simple way to do the same thing?


That seems simple enough.

However if you want a more efficient method, either use a already sorted
data structure such as multiset, or sort your vector first and compare
adjacent elements for equality.

bool vector_contains_only_different_elements (const vector<int>& v)
{
vector<int> tmp(v);
sort(tmp.begin(), tmp.end());
for (int i = 0; i < tmp.size() - 1; i++)
{
if (tmp[i] == tmp[i + 1])
return false;
}
return true;
}

(untested code)

Your code was an example of a quadratic time algorithm. It will take time
proportional to the square of the size of the array. In many cases this is
unacceptably slow. My version is what is sometimes called a linear log time
algorithm, it will take time proportional to n * log(n), where n is the size
of the vector, that is much better than a quadratic time algorithm.

Why not try the two methods on a very large vector, see which is faster.

john
Jul 22 '05 #2

P: n/a
>
Your code was an example of a quadratic time algorithm. It will take time
proportional to the square of the size of the array. In many cases this is
unacceptably slow. My version is what is sometimes called a linear log time algorithm, it will take time proportional to n * log(n), where n is the size of the vector, that is much better than a quadratic time algorithm.

Why not try the two methods on a very large vector, see which is faster.


Thinking about it my analysis only applies to the worst case, which is when
there aren't any duplicate elements. You algorithm could be very quick (and
quicker than mine) if duplicate elements are very common.

john
Jul 22 '05 #3

P: n/a

"John Harrison" <jo*************@hotmail.com> wrote in message news:2g************@uni-berlin.de...

"Alex Vinokur" <al****@big.foot.com> wrote in message
news:c7*********@news.f.de.plusline.net...
Here is some function that detects if a vector contains only different

elements

bool vector_contains_only_different_elements (const vector<int>& v)
{
for (int i = 0; i < v.size(); i++)
{
if (count (v.begin() + i + 1, v.end(), v[i]) >= 1) return false;
}
return true;
}
Is there more simple way to do the same thing?


That seems simple enough.

However if you want a more efficient method, either use a already sorted
data structure such as multiset, or sort your vector first and compare
adjacent elements for equality.

[snip]

Using set:
bool vector_contains_only_different_elements (const vector<int>& v)
{
return ( set<int>(v.begin(), v.end()).size() == v.size());
}
--
Alex Vinokur
mailto:al****@connect.to
http://mathforum.org/library/view/10978.html


Jul 22 '05 #4

P: n/a

"Alex Vinokur" <al****@big.foot.com> wrote in message
news:2g************@uni-berlin.de...

"John Harrison" <jo*************@hotmail.com> wrote in message

news:2g************@uni-berlin.de...

"Alex Vinokur" <al****@big.foot.com> wrote in message
news:c7*********@news.f.de.plusline.net...
Here is some function that detects if a vector contains only different

elements

bool vector_contains_only_different_elements (const vector<int>& v)
{
for (int i = 0; i < v.size(); i++)
{
if (count (v.begin() + i + 1, v.end(), v[i]) >= 1) return false;
}
return true;
}
Is there more simple way to do the same thing?


That seems simple enough.

However if you want a more efficient method, either use a already sorted
data structure such as multiset, or sort your vector first and compare
adjacent elements for equality.

[snip]

Using set:
bool vector_contains_only_different_elements (const vector<int>& v)
{
return ( set<int>(v.begin(), v.end()).size() == v.size());
}


How about

bool vector_contains_only_different_elements (const vector<int>& v)
{
set<int> s;
for (int i = 0; i < v.size(); ++i)
{
if (!s.insert(v[i]).second)
return false;
}
return true;
}

You get a quicker result when you do find a duplicate.

john
Jul 22 '05 #5

P: n/a

"John Harrison" <jo*************@hotmail.com> wrote in message news:2g************@uni-berlin.de...

"Alex Vinokur" <al****@big.foot.com> wrote in message
news:2g************@uni-berlin.de...

[snip]
Using set:
bool vector_contains_only_different_elements (const vector<int>& v)
{
return ( set<int>(v.begin(), v.end()).size() == v.size());
}


How about

bool vector_contains_only_different_elements (const vector<int>& v)
{
set<int> s;
for (int i = 0; i < v.size(); ++i)
{
if (!s.insert(v[i]).second)
return false;
}
return true;
}

You get a quicker result when you do find a duplicate.

john


OK.

--
Alex Vinokur
mailto:al****@connect.to
http://mathforum.org/library/view/10978.html

Jul 22 '05 #6

P: n/a
"John Harrison" <jo*************@hotmail.com> wrote in message
news:2ggenoF2e8huU1@uni-
bool vector_contains_only_different_elements (const vector<int>& v)
{
vector<int> tmp(v);
sort(tmp.begin(), tmp.end()); for (int i = 0; i < tmp.size() - 1; i++)
{
if (tmp[i] == tmp[i + 1])
return false;
}
return true;


How about std::adjacent_find (tmp.begin(), tmp.end()), which is no more
efficient, but is easier to read.
Jul 22 '05 #7

P: n/a
"Alex Vinokur" <al****@big.foot.com> wrote in message news:c7uvp4
bool vector_contains_only_different_elements (const vector<int>& v)
{
for (int i = 0; i < v.size(); i++)
{
if (count (v.begin() + i + 1, v.end(), v[i]) >= 1) return false;
}
return true;
}


Would find_first_of work? It's easier to read, though it's still worst case
O(N^2), though as John points out, it could be O(N) in certain situations.

return std::find_first_of(v.begin(), v.end(), v.begin(), v.end()) ==
v.end();
Jul 22 '05 #8

P: n/a
* "Alex Vinokur" <al****@big.foot.com> schriebt:
Here is some function that detects if a vector contains only different elements

bool vector_contains_only_different_elements (const vector<int>& v)
{
for (int i = 0; i < v.size(); i++)
{
if (count (v.begin() + i + 1, v.end(), v[i]) >= 1) return false;
}
return true;
}
Is there more simple way to do the same thing?


Simpler: that's subjective, so no real answer to that.

Faster: in general yes since the above is O(n^2).

As Alex Vinokur replied, and John Harrison then refined a bit, one generally
much faster way is to insert values in a std::set. Inserting a value is,
discounted, O( log setSize ). So in the worst case this yields
O( n log n ), which is also what you'd get by sorting the vector using
std::sort and then checking for duplicates linearly.

The problem with the std::set and the std::sort approaches, with respect to
this specific problem, is that they retain too much information, namely the
element value ordering -- which you don't need.

For a faster solution, essentially O(n), consider a data structure that
retains only the information of a mathematical set.

If the values of the vector are in a reasonable small range, or can be mapped
in constant time per value to distinct values in such a range, then simply use
a std::bitset.

If std::bitset is not applicable, then consider a hash table where each entry
is a set of pointers back to (const) vector elements. If you don't get any
hash key collision then all values are unique. If you do get a key collision,
then check whether the set contains a pointer to the element that was
attempted this time -- if so then there is a duplicate element, and if not
insert a pointer to the new element in the set at that hash table entry.

Unfortunately the standard library does not yet contain a hash table.

However, it is a common extension, and there's also one in the Boost library.

Finally, if the vectors are generally small it may be most efficient to use
the O(n^2) algorithm; faster in the specific although not in general. But to
ascertain whether or not that is the case you need to compare execution times.
If execution time is critical and you need to support different environments
(compiler, system) and/or data types, consider using the template mechanism to
choose a suitable implementation in each case.

--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jul 22 '05 #9

P: n/a
>
Unfortunately the standard library does not yet contain a hash table.

However, it is a common extension, and there's also one in the Boost library.


Where in the boost library?

john
Jul 22 '05 #10

P: n/a
* "John Harrison" <jo*************@hotmail.com> schriebt:

Unfortunately the standard library does not yet contain a hash table.

However, it is a common extension, and there's also one in the Boost
library.


Where in the boost library?


John you are the most valuable being I know of on this group, because
you always point out where I fail (if you're involved in the thread) and
so I can, in theory at least, improve!

Yes it is true: I made that comment about Boost only from my very fallible
memory, which turned out to be incorrect as a history-oriented memory in this
case.

But it further turned out that hey, I was remembering something that is
_about to happen_ (... ;-)), I just used the prescient part of my memory!

See this URL:
<url: http://lists.boost.org/MailArchives/boost/msg57603.php>

There is a detailed proposal and an implementation, it just isn't "officially"
sanctioned yet... The URL above provides links. Follow the next-pointers
for some of the discussion.

--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jul 22 '05 #11

P: n/a
"Alf P. Steinbach" <al***@start.no> wrote in message
news:40*****************@news.individual.net...
If the values of the vector are in a reasonable small range, or can be mapped in constant time per value to distinct values in such a range, then simply use a std::bitset.
This is a nice way to save memory.
If std::bitset is not applicable, then consider a hash table where each entry is a set of pointers back to (const) vector elements. If you don't get any hash key collision then all values are unique. If you do get a key collision, then check whether the set contains a pointer to the element that was
attempted this time -- if so then there is a duplicate element, and if not insert a pointer to the new element in the set at that hash table entry.

Unfortunately the standard library does not yet contain a hash table.
Also a good idea. But do the proposed hash_table interfaces expose this
information. It seems we want to get the bucket an element hashes to, and
then see if there is another element in this bucket with the same value, or
something along those lines. But these are private implementation details
that might not be exposed to the end user. So what is the boost interface,
and how to write the code.
However, it is a common extension, and there's also one in the Boost

library.
Jul 22 '05 #12

P: n/a
* "Siemel Naran" <Si*********@REMOVE.att.net> schriebt:
Also a good idea. But do the proposed hash_table interfaces expose this
information.
I don't know.

It seems we want to get the bucket an element hashes to, and
then see if there is another element in this bucket with the same value, or
something along those lines. But these are private implementation details
that might not be exposed to the end user. So what is the boost interface,
and how to write the code.


To the first, I don't know; to the second, use whatever is there, perhaps
modifying it a bit if it doesn't directly support the required functionality.

See also my reply to John Harrison in this subthread. ;-)

--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jul 22 '05 #13

P: n/a
* al***@start.no (Alf P. Steinbach) schriebt:
It seems we want to get the bucket an element hashes to, and
then see if there is another element in this bucket with the same value, or
something along those lines. But these are private implementation details
that might not be exposed to the end user. So what is the boost interface,
and how to write the code.


To the first, I don't know; to the second, use whatever is there, perhaps
modifying it a bit if it doesn't directly support the required functionality.


Just to check that I wasn't thinking unclearly (John Harrison has made me
acutely aware of my thinking processes, lately... ;-) ) I implemented this
using Visual C++ 7.1's stdext::hash_set, I think that's Dinkumware, simply by
providing a value comparision function for pointers,

template< typename T >
struct PointeeLess
{
bool operator()( T const* p1, T const* p2 )
{
return *p1 < *p2;
}
};

So at least that hash table implementation does provide the required
functionality right out of the box, so to speak.

But one interesting problem I encountered, to which I so far have just a
sketch of an answer in my head, is how to wrap such a hash table template
class so that the implementation's hash function is used by default while
providing the ability to specify a hash function and no textual dependency on
the implementation in client code.

--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jul 22 '05 #14

P: n/a

"Alf P. Steinbach" <al***@start.no> wrote in message
news:40*****************@news.individual.net...
* "John Harrison" <jo*************@hotmail.com> schriebt:

Unfortunately the standard library does not yet contain a hash table.

However, it is a common extension, and there's also one in the Boost
library.

Where in the boost library?


John you are the most valuable being I know of on this group, because
you always point out where I fail (if you're involved in the thread) and
so I can, in theory at least, improve!

Yes it is true: I made that comment about Boost only from my very fallible
memory, which turned out to be incorrect as a history-oriented memory in

this case.

But it further turned out that hey, I was remembering something that is
_about to happen_ (... ;-)), I just used the prescient part of my memory!

See this URL:
<url: http://lists.boost.org/MailArchives/boost/msg57603.php>

There is a detailed proposal and an implementation, it just isn't "officially" sanctioned yet... The URL above provides links. Follow the next-pointers
for some of the discussion.


Thanks for that link, I thought it was an interesting discussion on the
choices in implementing STL style hash tables.

The reason I queried you about boost and hash tables was that some time ago
I wrote my own STL style hash table classes, after having a good look at the
SGI and Dinkumware implementations (I decided I liked the SGI interface but
the Dinkumware implementation, particularly incremental rehashing which I
hadn't come across before). So it was a surprise to be told that boost had
an implementation as well, a quick look and I couldn't see it though.

john
Jul 22 '05 #15

This discussion thread is closed

Replies have been disabled for this discussion.