446,418 Members | 1,094 Online 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& 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
14 Replies

 P: n/a "Alex Vinokur" 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& 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& v) { vector 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" wrote in message news:2g************@uni-berlin.de... "Alex Vinokur" 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& 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& v) { return ( set(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" wrote in message news:2g************@uni-berlin.de... "John Harrison" wrote in message news:2g************@uni-berlin.de... "Alex Vinokur" 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& 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& v) { return ( set(v.begin(), v.end()).size() == v.size()); } How about bool vector_contains_only_different_elements (const vector& v) { set 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" wrote in message news:2g************@uni-berlin.de... "Alex Vinokur" wrote in message news:2g************@uni-berlin.de... [snip] Using set: bool vector_contains_only_different_elements (const vector& v) { return ( set(v.begin(), v.end()).size() == v.size()); } How about bool vector_contains_only_different_elements (const vector& v) { set 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" wrote in message news:2ggenoF2e8huU1@uni- bool vector_contains_only_different_elements (const vector& v) { vector 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" wrote in message news:c7uvp4 bool vector_contains_only_different_elements (const vector& 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" schriebt: Here is some function that detects if a vector contains only different elements bool vector_contains_only_different_elements (const vector& 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" 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: 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" 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" 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" wrote in message news:40*****************@news.individual.net... * "John Harrison" 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: 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. 