Se permite volver a equilibrar std :: map después de operaciones de solo lectura (como un árbol Splay)

Question

Algunas estructuras de datos de árbol binario (como Splay árboles) volverán a equilibrarse en lecturas para mover elementos recientemente accedidos hacia la raíz, de modo que el tiempo de búsqueda posterior puede reducirse.

¿Los contenedores estándar (std::map, std::set) tienen permitido hacer esto?

Al menos una de las preocupaciones es la seguridad de los hilos. Anteriormente, pensé que siempre y cuando solo estuvieras haciendo operaciones de solo lectura en contenedores estándar, era seguro hacerlo desde múltiples hilos sin introducir mutexes/bloqueos, etc. ¿Quizás necesito volver a pensar esto?

Sé que normalmente árboles rojo-negro se utilizan para los contenedores de árbol estándar, y que estas estructuras de datos no suelen modificarse en las lecturas. Pero, ¿se conformaría una implementación hipotética que sí se modificó?

Mi C++ - standards-foo necesita mejoras, pero no estoy seguro de si el estándar actual aborda la seguridad de subprocesos para contenedores. ¿Es esto diferente en c++0x?

Answer 1

Desde el proyecto de c++0x:

§23.2.2/1:

A los efectos de evitar carreras de datos (17.6.5.9), las implementaciones se consideran las siguientes funciones como constante: iniciar, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at y, excepto en los contenedores asociativos o no asociativos, operator [].

Tenga en cuenta que c++03 no dice nada acerca de múltiples hilos, pero como usted dice, la mayoría de las implementaciones de usar RB-árboles, que no serán reequilibrar en una operación de lectura.

Answer 2

Las funciones de lectura en mapas, etc. requieren una función const definida. Por lo tanto, obtiene la garantía de que el objeto no ha cambiado.

Esto es cierto tanto para C++ 11 (23.4.4.1) como para C++ 03 (23.3.1).

23.2.2 del nuevo estándar de C++ 11 pueden ser de especial interés aquí:

1. A los efectos de evitar carreras de datos (17.6.5.9), las implementaciones deberán considerar la las siguientes funciones son const: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at y, excepto en contenedores asociativos o no asociativos, operador [].

2. No obstante (17.6.5.9), las implementaciones se requiere para evitar razas de datos cuando el contenido del objeto contenido en elementos diferentes en la misma secuencia, excepto vector<bool>, son modificarse simultáneamente.