Checking if all elements of a vector are equal in C++
Solution 1
You need not to use std::sort
. It can be done in a simpler way:
if ( std::adjacent_find( myvector.begin(), myvector.end(), std::not_equal_to<>() ) == myvector.end() )
{
std::cout << "All elements are equal each other" << std::endl;
}
Solution 2
you can use std::equal
version 1:
//assuming v has at least 1 element
if ( std::equal(v.begin() + 1, v.end(), v.begin()) )
{
//all equal
}
This will compare each element with the previous one.
version 2:
//assuming v has at least 1 element
int e = v[0]; //preferably "const auto& e" instead
bool all_equal = true;
for(std::size_t i = 1,s = v.size();i<s && all_equal;i++)
all_equal = e == v[i];
Edit:
Regarding performance, after testing with 100m elements i found out that in Visual Studio 2015 version 1
is about twice as fast as version 2
. This is because the latest compiler for vs2015 uses sse instructions in c++ std implementations when you use ints, float , etc..
if you use _mm_testc_si128 you will get a similar performance to std::equal
Solution 3
Given no constraints on the vector, you have to iterate through the vector at least once, no matter the approach. So just pick the first element and check that all others are equal to it.
Solution 4
using std::all_of and C++11 lambda
if (all_of(values.begin(), values.end(), [&] (int i) {return i == values[0];})){
//all are the same
}
Solution 5
While the asymptotic complexity of std::unique
is linear, the actual cost of the operation is probably much larger than you need, and it is an inplace algorithm (it will modify the data as it goes).
The fastest approach is to assume that if the vector contains a single element, it is unique by definition. If the vector contains more elements, then you just need to check whether all of them are exactly equal to the first. For that you only need to find the first element that differs from the first, starting the search from the second. If there is such an element, the elements are not unique.
if (v.size() < 2) return true;
auto different = std::find_if(v.begin()+1, v.end(),
[&v](auto const &x) { x != v[0]; });
return different == v.end();
That is using C++14 syntax, in an C++11 toolchain you can use the correct type in the lambda. In C++03 you could use a combination of std::not
, std::bind1st/std::bind2nd
and std::equal
in place of the lambda.
The cost of this approach is distance(start,different element)
comparisons and no copies. Expected and worst case linear cost in the number of comparisons (and no copies!)
Related videos on Youtube
SJWard
Updated on July 09, 2022Comments
-
SJWard almost 2 years
If I have a vector of values and want to check that they are all the same, what is the best way to do this in C++ efficiently? If I were programming in some other language like R one way my minds jumps to is to return only the unique elements of the container and then if the length of the unique elements is more than 1, I know all the elements cannot be the same. In C++ this can be done like this:
//build an int vector std::sort(myvector.begin(), myvector.end()); std::vector<int>::iterator it; //Use unique algorithm to get the unique values. it = std::unique(myvector.begin(), myvector.end()); positions.resize(std::distance(myvector.begin(),it)); if (myvector.size() > 1) { std::cout << "All elements are not the same!" << std::endl; }
However reading on the internet and SO, I see other answers such using a
set
or thefind_if
algorithm. So what is the most efficient way of doing this and why? I imagine mine is not the best way since it involves sorting every element and then a resizing of the vector - but maybe I'm wrong.-
jogojapan over 10 yearsThis has been asked before: stackoverflow.com/questions/15531258/… The answers there point out, importantly, that efficiency in the O(n) compare-all-to-the-first method can be gained by making sure you break off the loop once you find the first element that is not equal.
-
Ciro Santilli OurBigBook.com about 8 yearsArray version: stackoverflow.com/questions/14120346/… is a subset via
data()
. -
Andreas almost 4 yearsWhat is the preferred behavior on empty vector? The std::equal and std::adjacent_find answers return false, std::find_if and std::all_of return true.
-
-
Luchian Grigore over 10 yearsWhy is that more efficient than just iterating through the vector?
-
Luchian Grigore over 10 yearsLess efficient than just iterating through the array as you're incrementing 2 iterators internally.
-
Raxvan over 10 years@Luchian Grigore yes , but it's shorter to write :)
-
Luchian Grigore over 10 yearsTrue, but "So what is the most efficient way of doing this and why?"
-
Raxvan over 10 years@Luchian Grigore ok , i'll edit to add something that's efficient.
-
RichardPlunkett over 10 yearsit isnt, and in general is as bad as sorting.
-
RichardPlunkett over 10 yearsnote that while down the bottom he asks for "most efficen"t, up the top he asks for the "best way", subject to being c++ and efficient. The "best way" allows one to consider style, readability and such, while while balancing against a possible factor of 2 slow down.
-
Julien B. over 10 yearsIt is not, I did not have the time to elaborate my answer yet. However, I think it is usefull for Ward9250 to know that building a set would be a possibility if he was looking for more than an unique value.
-
ComicSansMS over 10 yearsI was close to posting a solution using
adjacent_find
, but mine would have featured a lambda predicate, which is why I did not post it in the end.not_equal_to
was the missing piece that makes it a beautiful solution. -
RichardPlunkett over 10 yearsOpening statement is misleading. Yes Unique is linear, but it followed on a sort, which is definitely not linear.
-
Vlad from Moscow over 10 yearsIt is strange that nobody mentioned std::all_of.:)
-
David Rodríguez - dribeas over 10 years@RichardPlunkett: If your only expectation is to detect whether there is a unique value or not, you don't need to sort. Note that this is not attempting to solve the generic problem of removing duplicates or finding how many unique values there are, but rather finding whether there is at least one non-duplicate value. Maybe I should make that more explicit in the answer... although it is just a comment on the question's approach, rather than my own approach.
-
DarioP over 10 yearsRemember to short-circuit after you find a value unequal to the first!
-
Larry Engholm over 6 yearsYour comment suggests there's a better solution using all_of. If so, could you (or somebody) edit your answer to show it?
-
underscore_d over 5 yearsIt's also a waste of time because
count
has to keep going even after it finds the 1st differing element, but you only need to know if there was one, so those are wasted cycles. I don't see why we needed an inefficient alternative 4 years later. -
underscore_d over 5 yearsI don't see how this is any 'simpler' than all the other ways posted 4 years earlier. In fact, it's a waste of time because
count
has to keep going even after it finds the 1st differing element, but you only need to know if there was one, so those are purely wasted cycles. -
Tas over 5 yearsYou raise a good point, at the time I hadn't considered that it would iterate over all elements; however, many of the other solutions do the same, and I don't claim this is the best method of doing it, but I ran into this issue and found this to be the most readable solution. If a
vector
is very large then it would definitely be worth using a solution that wouldn't iterate over all elements. -
Mikhail about 3 yearsmaybe also do begin()+1?
-
RyanCu about 2 years@Mikhail, if you can guarantee that
values
is non-empty,begin()+1
will indeed skip one unnecessary evaluation. But if emptiness is a possibility, the above answer provides safety as it simply returns true in this case.