If vector contains only different elements

[Alex Vinokur]

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) >= 1) return false;
}
return true;
}


Is there more simple way to do the same thing?

 

[John Harrison]

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) >= 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 == 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

 

[John Harrison]

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

 

[Alex Vinokur]

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) >= 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());
}

 

[John Harrison]

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) >= 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).second)
return false;
}
return true;
}

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

john

 

[Alex Vinokur]

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).second)
return false;
}
return true;
}

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

john

OK.

 

[Siemel Naran]

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 == 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.

 

[Siemel Naran]

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) >= 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();

 

[Alf P. Steinbach]

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) >= 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.

 

[John Harrison]

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

 

[Siemel Naran]

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.

 

[Alf P. Steinbach]

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.

 

[Alf P. Steinbach]

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. ;-)

 

[Alf P. Steinbach]

* (e-mail address removed) (Alf P. Steinbach) schriebt:

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.

 

[John Harrison]

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