Checking if all elements of a vector are equal in C++

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 al 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 about the internet and SO, I see other answers such using a set or the find_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.

Thanks, Ben.

Answers


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;
}

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


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.


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


Sorting is an O(NlogN) task.

This is easily solvable in O(N), so your current method is poor.

A simple O(N) would be as Luchian Grigore suggests, iterate over the vector, just once, comparing every element to the first element.


if(std::all_of(myvector.begin()+1, myvector.end(), std::bind(std::equal_to<int>(),
                                      std::placeholders::_1, myvector.front())) {
  // all members are equal
}

In your specific case, iterating over vector element and finding a different element from the first one would be enough. You may even be lucky enough to stop before evaluating all the elements in your vector. (A while loop could be used but I sticked with a for loop for readability reasons)

bool uniqueElt = true;
int firstItem = *myvector.begin();
for (std::vector<int>::const_iterator it = myvector.begin()+1; it != myvector.end() ; ++it) {
    if(*it != firstItem) {
        uniqueElt = false;
        break;
    }
}

In case you want to know how many different values your vector contains, you could build a set and check its size to see how many different values are inside:

std::set mySet;
std::copy(mySet.begin(), myvector.begin(), myvector.end());

You can use FunctionalPlus(https://github.com/Dobiasd/FunctionalPlus):

std::vector<std::string> things = {"same old", "same old"};
if (fplus::all_the_same(things))
    std::cout << "All things being equal." << std::endl;

Maybe something like this. It traverses vector just once and does not mess with the vector content.

std::vector<int> values { 5, 5, 5, 4 };
bool equal = std::count_if(values.begin(), values.end(), [ &values ] (auto size) { return size == values[0]; }) == values.size();

If the values in the vector are something different than basic type you have to implement equality operator.

After taking into account underscore_d remarks, I'm changing possible solution

std::vector<int> values { 5, 5, 5, 4 };
bool equal = std::all_of(values.begin(),values.end(),[ &values ] (auto item) { return item == values[0]; });

for the sake of completeness, because it still isn't the most efficient, you can use std::unique in a more efficient way to decide whether all members are the same, but beware that after using std::unique this way the container is useless:

#include <algorithm>
#include <iterator>

if (std::distance(cntnr.begin(), std::unique(cntnr.begin(), cntnr.end()) == 1)
{
  // all members were the same, but
}

You can simply use std::count to count all the elements that match the starting element:

std::vector<int> numbers = { 5, 5, 5, 5, 5, 5, 5 };
if (std::count(std::begin(numbers), std::end(numbers), numbers.front()) == numbers.size())
{
    std::cout << "Elements are all the same" << std::endl;
}

Another approach using C++ 14:

bool allEqual = accumulate(v.begin(), v.end(), true, [first = v[0]](bool acc, int b) {
    return acc && (b == first);
  });

which is also order N.


Need Your Help

javafx GridPane retrieve specific Cell content

javafx cell gridpanel

I want to retrieve the content of one specific cell in a Gridpane. I have put buttons in the cells with the

How does Stack Overflow generate its SEO-friendly URLs?

regex language-agnostic seo friendly-url slug

What is a good complete regular expression or some other process that would take the title: