Usando el operador de módulo para mantener dentro de los índices del contenedor

Question

Supongamos que tengo un vector v con m elementos en él, y un índice de acceso aleatorio al vector llamado i.

Cuando incremento el índice, si sale de los límites, quiero indexar el primer elemento (cero). Del mismo modo, cuando decremento el índice, si el índice es < 0, quiero indexar al último elemento. Por el momento sólo me mueve a través del un elemento contenedor a la vez, por lo que se acercó con esta función:

unsigned int GetIndexModM(int index,unsigned int m) {return (index + m) % m;} 

La llamada in situ podría tener este aspecto:

std::vector<Whatever> v = ... // initialise with 5 elements 
unsigned int i = 0; 
unsigned int j = GetIndexModM(static_cast<int>(i) - 1,v.size()); // get preceeding index 

esta función fallará sin embargo, si se resta un valor> m de índice:

unsigned int j = GetIndexModM(static_cast<int>(i) - 17,v.size()); // oops: returns -2 

Mi pregunta: ¿Cuál es el más elegante puesta en práctica de una función que toma un entero y devuelve su lugar como un índice?

Answer 1

El truco para el manejo de este mod es, que trabaja con números positivos y negativos:

val = ((val % mod_val) + mod_val) % mod_val; 

Por ejemplo, supongamos que queremos mantener valor entre 0 y 359, ambos inclusive. Podríamos usar esto:

val = ((val % 360) + 360) % 360; 

Aquí hay un ejemplo simple en C++.

int getmod(int val, int mod) { 
    return ((val % mod) + mod) % mod; 
} 

int main() { 
    printf("%d\n", getmod(50,360)); // prints 50 
    printf("%d\n", getmod(-400,360)); // prints 320 
    printf("%d\n", getmod(350,360)); // prints 350 
    printf("%d\n", getmod(375,360)); // prints 15 
    printf("%d\n", getmod(-725,360)); // prints 355 


    return 0; 
} 

Answer 2

Desafortunadamente, C++ no implementa un módulo adecuado que todavía funciona correctamente para enteros negativos.

Creo que la solución más limpia es utilizar if para atender correctamente todos los casos. Esto, al menos, hace que el código obvia (porque cada caso es explícita) y los errores más fáciles de encontrar:

unsigned GetIndexModM(int index, unsigned m) { 
    if (index < 0) 
     return GetIndexModM(index + m, m); 
    if (index >= m) 
     return index % m; 
    return index; 
} 

Answer 3

El siguiente asegura que index está en [0, n) pero con sólo una operación de módulo y no hay ramas :

index = index % n + (index < 0)*n 

donde el primer término (que contiene el operador de módulo) obtiene el valor en (-n, n) y el segundo término se asegura de que el valor está en [0, n).

Tenga en cuenta que esto no es confiable cuando n es un tipo sin firmar y en versiones anteriores (antes de 11) de C++ donde el operador% depende de la implementación para argumentos negativos.