Если у меня есть вектор значений и вы хотите проверить, что они все одинаковые, что лучший способ сделать это на С++ эффективно? Если бы я программировал на каком-то другом языке, например, R, один мой ум перескакивает - это возвращать только уникальные элементы контейнера, а если длина уникальных элементов больше 1, я знаю, что элементы не могут быть одинаковыми. В С++ это можно сделать следующим образом:
//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;
}
Однако, прочитав об Интернете и SO, я вижу другие ответы, например, с помощью набора или алгоритма find_if. Итак, каков наиболее эффективный способ сделать это и почему? Я считаю, что мой не лучший способ, поскольку он включает в себя сортировку каждого элемента, а затем изменение размера вектора - но, возможно, я ошибаюсь.
Спасибо, Бен.
Вам не нужно использовать 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;
}
Вы можете использовать std::equal
версия 1:
//assuming v has at least 1 element
if ( std::equal(v.begin() + 1, v.end(), v.begin()) )
{
//all equal
}
Это позволит сравнить каждый элемент с предыдущим.
версия 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];
Редактировать:
Что касается производительности, то после тестирования с 100-метровыми элементами я обнаружил, что в Visual Studio 2015 version 1 примерно в два раза быстрее, чем version 2. Это связано с тем, что последний компилятор для vs2015 использует инструкции sse в реализациях c++ std, когда вы используете int, float и т.д.
если вы используете _mm_testc_si128, вы получите производительность, аналогичную std::equal
Без каких-либо ограничений для вектора вы должны проходить через вектор хотя бы один раз, независимо от подхода. Поэтому просто выберите первый элемент и убедитесь, что все остальные равны ему.
Хотя асимптотическая сложность std::unique является линейной, фактическая стоимость операции, вероятно, намного больше, чем вам нужно, и это алгоритм inplace (он будет изменять данные по мере их появления).
Самый быстрый подход - предположить, что если вектор содержит один элемент, он по определению уникален. Если вектор содержит больше элементов, вам просто нужно проверить, все ли они в точности равны первому. Для этого вам нужно всего лишь найти первый элемент, который отличается от первого, начиная поиск со второго. Если есть такой элемент, элементы не уникальны.
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();
Используя синтаксис С++ 14, в инструментальной цепочке С++ 11 вы можете использовать правильный тип в лямбда. В С++ 03 вместо лямбда вы можете использовать комбинацию std::not, std::bind1st/std::bind2nd и std::equal.
Стоимость этого подхода - distance(start,different 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
}
Сортировка - это задача O (NlogN).
Это легко разрешимо в O (N), поэтому ваш текущий метод неудовлетворительный.
Простой O (N) будет таким, какой предлагает Лучиан Григоре, итерации по вектору только один раз, сравнивая каждый элемент с первым элементом.
В вашем конкретном случае достаточно повторить итерацию над векторным элементом и найти другой элемент из первого. Возможно, вам даже повезет остановиться, прежде чем оценивать все элементы вашего вектора. (Можно использовать цикл 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;
}
}
Если вы хотите узнать, сколько разных значений содержит ваш вектор, вы можете создать набор и проверить его размер, чтобы увидеть, сколько разных значений внутри:
std::set mySet;
std::copy(mySet.begin(), myvector.begin(), myvector.end());
Вы можете использовать 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;
Может быть как то так Он пересекает вектор только один раз и не связывается с векторным содержимым.
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();
Если значения в векторе отличаются от базового типа, вы должны реализовать оператор равенства.
После учета замечаний 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]; });
для полноты, поскольку он по-прежнему не самый эффективный, вы можете использовать std:: unique более эффективным способом решить, все ли члены одинаковы, но будьте осторожны, после использования std:: unique this путь контейнер бесполезен:
#include <algorithm>
#include <iterator>
if (std::distance(cntnr.begin(), std::unique(cntnr.begin(), cntnr.end()) == 1)
{
// all members were the same, but
}
Вы можете просто использовать std::count, чтобы подсчитать все элементы, соответствующие исходному элементу:
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;
}
Другой подход с использованием C++ 14:
bool allEqual = accumulate(v.begin(), v.end(), true, [first = v[0]](bool acc, int b) {
return acc && (b == first);
});
который также порядок N.
используя std::all_of и С++ 11 lambda
if (all_of(values.begin(), values.end(), [&] (int i) {return i == values[0];}){
//all are the same
}