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