Invalid <aserción del operador en el género

Question

Estoy tratando de implementar un comparador simple para ordenar los índices basado en los valores de una matriz "_vec". Recibo un mensaje de error de "operador < sin validez". No entiendo lo que está mal con el siguiente código:

class Compare{ 
vector<int>& _vec; 
public: 
    Compare(vector<int>& vec) : _vec(vec) {} 
    bool operator()(size_t i, size_t j){ 
     if(_vec[i] != _vec[j]) 
     return _vec[i] < _vec[j]; 
     else 
     return (double)rand()/RAND_MAX < 0.5; 
    } 
}; 

estoy usando la siguiente función llamada:

sort(inds.begin(),inds.end(),Compare(vals)); 

donde inds es sólo una matriz que contiene los índices de 1 a 15 (por ejemplo) y vals es la matriz de longitud 15 con algunos valores cuyos índices ordenados quiero calcular. El objetivo general es aleatorizar el orden de clasificación cuando dos (o más) entradas en vals son iguales. ¿Alguna ayuda?

Answer 1

std::sort() espera que la operación de comparación sea estable: si se devuelve un resultado particular cuando se comparan dos elementos, la comparación debe devolver el mismo resultado si se vuelven a comparar. Cuando devuelves un valor aleatorio, obviamente no necesariamente se mantendrá.

C++ 03 25.3/4 "Ordenar y las operaciones conexas", dice:

Si definimos equiv (a, b) como un borrador (a, b) & & borrador (b, a!), entonces las requisitos son que los y equiv ser ambos relaciones transitivos:

• COMP (a, b) & & comp (b, c) implica comp (a, c)
• equiv (a, b) & & equiv (b, c) implica equiv (a, c)

[Nota: En estas condiciones, se puede demostrar que

• equiv es una relación de equivalencia
• los induce un pozo -relación definida en las clases de equivalencia determinadas por el equivalente
• La relación inducida es un ordenamiento total estricto.

nota -end]

Y de aclaración, la Tabla 28 define una relación de equivalencia:

== es una relación de equivalencia, es decir, satisface las siguientes propiedades:

• Para todos a, a == a.
• Si a == b, entonces b == a.

Por lo que su operación Compare() no producirá una relación de equivalencia.

Es agradable obtener una afirmación en lugar de perder datos aleatoriamente.

Una forma de resolver el problema de aleatorizar el orden cuando dos (o más) entradas en _vec son iguales es crear un valor aleatorio para esos índices y realizar un seguimiento de esos valores aleatorios en un mapa de índice => valor aleatorio o algo así. Solo asegúrese de hacer un seguimiento y usar esos valores aleatorios de tal forma que se mantengan las propiedades de transitiva y equivalencia de Compare().

Answer 2

std::sort espera que el operador menor que para el suministro de un relación transitiva, es decir, cuando el género ve A < B es verdadera y B < C es cierto, implica que A < C es cierto también.

En su implementación, la regla de transitividad no se cumple: cuando dos elementos son iguales, usted indica aleatoriamente el orden en que uno de ellos es mayor que el otro. Esto desencadena la afirmación de depuración.

Devuelve falso para valores iguales para solucionar esto.