* "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?
