una - Comprobando si todos los elementos de un vector son iguales en C++

matriz de caracteres en c

Question

Si tengo un vector de valores y quiero comprobar que todos son iguales, ¿cuál es la mejor manera de hacer esto en C ++ de manera eficiente? Si estuviera programando en algún otro lenguaje como R, una forma en la que mi mente salta es devolver solo los elementos únicos del contenedor y luego si la longitud de los elementos únicos es mayor que 1, sé que los elementos no pueden ser iguales. En C ++ esto se puede hacer así:

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

Sin embargo, leyendo sobre Internet y SO, veo otras respuestas como el uso de un conjunto o el algoritmo find_if. Entonces, ¿cuál es la forma más eficiente de hacer esto y por qué? Imagino que la mía no es la mejor, ya que implica ordenar cada elemento y luego cambiar el tamaño del vector, pero tal vez me equivoque.

Gracias, Ben.

Answer 1

Dado que no hay restricciones en el vector, debe iterar a través del vector al menos una vez, sin importar el enfoque. Así que simplemente elige el primer elemento y verifica que todos los demás sean iguales a él.

Answer 2

En su caso específico, sería suficiente iterar sobre un elemento vectorial y encontrar un elemento diferente del primero. Incluso puede tener la suerte de detenerse antes de evaluar todos los elementos de su vector. (Se podría usar un bucle while, pero me quedé con un bucle for por razones de legibilidad)

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

En caso de que desee saber cuántos valores diferentes contiene su vector, podría crear un conjunto y verificar su tamaño para ver cuántos valores diferentes hay dentro:

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

Answer 3

La clasificación es una tarea O (NlogN).

Esto es fácilmente solucionable en O (N), por lo que su método actual es deficiente.

Una simple O (N) sería como lo sugiere Luchian Grigore, iterar sobre el vector, solo una vez, comparando cada elemento con el primer elemento.

Answer 4

No necesitas usar std::sort . Se puede hacer más simple:

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

Answer 5

Otro enfoque utilizando C++ 14 :

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

que también es orden N.

Answer 6

Puede usar 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;

Answer 7

Si bien la complejidad asintótica de std::unique es lineal, el costo real de la operación probablemente sea mucho mayor de lo que necesita, y es un algoritmo in situ (modificará los datos a medida que avanza).

El enfoque más rápido es asumir que si el vector contiene un solo elemento, es único por definición. Si el vector contiene más elementos, solo necesita verificar si todos ellos son exactamente iguales al primero. Para eso solo necesitas encontrar el primer elemento que difiere del primero, comenzando la búsqueda desde el segundo. Si existe tal elemento, los elementos no son únicos.

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

Eso es usar la sintaxis de C ++ 14, en una cadena de herramientas de C ++ 11 puede usar el tipo correcto en la lambda. En C ++ 03 puede usar una combinación de std::not , std::bind1st/std::bind2nd y std::equal en lugar de la lambda.

El costo de este enfoque son las comparaciones de distance(start,different element) y ninguna copia. Costo lineal esperado y en el peor de los casos en el número de comparaciones (¡y sin copias!)

Answer 8

Simplemente puede usar std::count para contar todos los elementos que coinciden con el elemento inicial:

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

Answer 9

Tal vez algo como esto. Atraviesa el vector solo una vez y no se mete con el contenido del vector.

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

Si los valores en el vector son algo diferente al tipo básico, debe implementar el operador de igualdad.

Después de tener en cuenta los comentarios de subrayado, estoy cambiando una posible solución

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

Answer 10

para completar, ya que todavía no es el más eficiente, puede usar std :: unique de una manera más eficiente para decidir si todos los miembros son iguales, pero tenga en cuenta que después de usar std :: unique de esta manera, el contenedor es inútil

#include <algorithm>
#include <iterator>

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

Answer 11

puedes usar std::equal

versión 1:

//assuming v has at least 1 element
if ( std::equal(v.begin() + 1, v.end(), v.begin()) )
{
    //all equal
}

Esto comparará cada elemento con el anterior.

versión 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];

Editar:

En cuanto al rendimiento, después de realizar pruebas con elementos de 100 m, descubrí que en Visual Studio 2015, la version 1 es casi el doble de rápida que la version 2 . Esto se debe a que el último compilador para vs2015 usa instrucciones sse en las implementaciones de c ++ std cuando se usan ints, float, etc.

si usa _mm_testc_si128 obtendrá un rendimiento similar a std::equal

Answer 12

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