在 C++ 中检查向量的所有元素是否相等

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

提问by Ward9250

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:

如果我有一个值向量并想检查它们是否都相同，那么在 C++ 中有效地执行此操作的最佳方法是什么？如果我使用其他语言（如 R）进行编程，我的想法之一是只返回容器的唯一元素，然后如果唯一元素的长度大于 1，我知道所有元素不能相同。在 C++ 中，这可以像这样完成：

//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.

然而，阅读互联网和 SO，我看到了其他答案，例如使用集合或 find_if 算法。那么最有效的方法是什么，为什么？我想我的不是最好的方法，因为它涉及对每个元素进行排序，然后调整向量的大小 - 但也许我错了。

Thanks, Ben.

谢谢，本。

回答by Vlad from Moscow

You need not to use std::sort. It can be done in a simpler way:

您不需要使用std::sort. 它可以通过更简单的方式完成：

if ( std::adjacent_find( myvector.begin(), myvector.end(), std::not_equal_to<>() ) == myvector.end() )
{
    std::cout << "All elements are equal each other" << std::endl;
}

回答by Raxvan

you can use std::equal

您可以使用 std::equal

version 1:

版本 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:

版本 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 1is about twice as fast as version 2. This is because the latest compiler for vs2015 uses sse instructionsin c++ std implementations when you use ints, float , etc..

关于性能，在使用 100m 元素进行测试后，我发现在 Visual Studio 2015version 1中的速度大约是version 2. 这是因为当您使用 ints、float 等时，vs2015 的最新编译器在 c++ std 实现中使用sse 指令。

if you use _mm_testc_si128you will get a similar performance to std::equal

如果您使用_mm_testc_si128，您将获得与std::equal

回答by Luchian Grigore

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.

鉴于对向量没有限制，无论采用哪种方法，您都必须至少迭代一次向量。所以只需选择第一个元素并检查所有其他元素是否与它相同。

回答by RichardPlunkett

Sorting is an O(NlogN) task.

排序是一个 O(NlogN) 任务。

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

这很容易在 O(N) 中解决，因此您当前的方法很差。

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

一个简单的 O(N) 就像 Luchian Grigore 所建议的那样，只迭代一次向量，将每个元素与第一个元素进行比较。

回答by David Rodríguez - dribeas

While the asymptotic complexity of std::uniqueis 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).

虽然 的渐近复杂度std::unique是线性的，但操作的实际成本可能比您需要的要大得多，并且它是一种就地算法（它会随着数据进行修改）。

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::bind2ndand std::equalin place of the lambda.

那是使用 C++14 语法，在 C++11 工具链中，您可以在 lambda 中使用正确的类型。在 C++03 中，您可以使用std::not,std::bind1st/std::bind2nd和的组合来std::equal代替 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!)

这种方法的成本是distance(start,different element)比较而不是复制。比较次数的预期和最坏情况线性成本（并且没有副本！）

回答by iNFINITEi

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

回答by Alfonce Nzioka

using std::all_of and C++11 lambda

使用 std::all_of 和 C++11 lambda

if (all_of(values.begin(), values.end(), [&] (int i) {return i == values[0];}){
    //all are the same
}

回答by Jee lee

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

您可以使用 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;

回答by Rostfrei

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

考虑到 underscore_d 评论后，我正在更改可能的解决方案

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

回答by Julien B.

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)

在您的特定情况下，迭代向量元素并找到与第一个元素不同的元素就足够了。您甚至可能幸运地在评估向量中的所有元素之前停下来。（可以使用 while 循环，但出于可读性原因，我坚持使用 for 循环）

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());