español - vector c++ find
¿Están std:: fill, std:: copy especializados para std:: vector<bool>? (3)
Al pensar en esta pregunta , empiezo a preguntarme si std::copy() y / o std::fill están especializados (realmente quiero decir optimizados) para std::vector<bool> .
¿Esto es requerido por el estándar de C ++ o, quizás, es un enfoque común para los proveedores de la biblioteca estándar de C ++?
En pocas palabras, me pregunto si el siguiente código:
std::vector<bool> v(10, false);
std::fill(v.begin(), v.end(), true);
es de alguna manera mejor / diferente que eso:
std::vector<bool> v(10, false);
for (auto it = v.begin(); it != v.end(); ++it) *it = true;
Para ser muy estricto, puede decir: std::fill<std::vector<bool>::iterator>() entra en la representación interna de std::vector<bool> y establece sus bytes completos en lugar de bits individuales? ¿Asumo que hacer std::fill friend de std::vector<bool> no es un gran problema para el proveedor de la biblioteca?
[ACTUALIZAR]
Siguiente pregunta relacionada: ¿puedo (o alguien más :) especializar tales algoritmos para dejar decir std::vector<bool> , si no ya está especializado? ¿Esto está permitido por C ++ estándar? Sé que esto no será portátil, ¿pero solo para una biblioteca std C ++ seleccionada? Asumiendo que yo (o cualquier otra persona) encuentre una manera de llegar a las partes privadas de std::vector<bool> .
23.2.5 El vector de clase de C ++ International Standard llega a decirnos
Para optimizar la asignación de espacio, se proporciona una especialización de vector para elementos bool:
después de lo cual se proporciona la especialización bitset. Hasta donde llega el estándar con respecto a vector<bool> , los proveedores deben implementarlo usando un conjunto de bits para optimizar el espacio. La optimización del espacio tiene un costo aquí, ya que no optimiza la velocidad.
Es más fácil obtener un libro de la biblioteca que encontrar un libro si estuviera entre todos los libros de la biblioteca grapados en contenedores ...
Tome su ejemplo, está tratando de hacer un std::fill o std::copy de principio a fin. Pero ese no es siempre el caso, a veces simplemente no se asigna a un byte completo. Entonces, eso es un problema en términos de optimización de velocidad. Es fácil para el caso que tenga que cambiar cada bit a uno, eso es simplemente cambiar los bytes a 0xF, pero ese no es el caso aquí; se vuelve mucho más difícil si solo cambiara ciertos bits de un byte. Entonces necesitarás calcular realmente qué será el byte; eso no es algo trivial * , o al menos no como una operación atómica en el hardware actual.
Es la historia de optimización prematura, es agradable en términos de espacio pero horrible en términos de rendimiento.
¿Tener un cheque "is a multiple of 8 bits" vale la pena? Lo dudo.
* Estamos hablando de múltiples bits aquí, para el caso es solo un bit por el que puedes hacer un poco de operación.
Las optimizaciones no están especificadas en el estándar. Se supone que es una cuestión de "calidad de implementación" si se aplicara una optimización. La complejidad asintótica de la mayoría de los algoritmos es, sin embargo, restringida.
Las optimizaciones están permitidas siempre que un programa correcto se comporte de acuerdo con lo que exige el estándar. Los ejemplos sobre los que pregunta, es decir, las optimizaciones que involucran algoritmos estándar que usan iteradores en std::vector<bool> , pueden lograr su objetivo de la manera que la implementación lo considere adecuado, ya que no hay forma de monitorear cómo se implementan. Dicho esto, dudo mucho de que exista una implementación de biblioteca estándar que optimice las operaciones en std::vector<bool> . La mayoría de la gente parece pensar que esta especialización es una abominación en primer lugar y que debería desaparecer.
Un usuario solo puede crear especializaciones de tipos de biblioteca si la especialización implica al menos un tipo definido por el usuario. No creo que un usuario tenga permiso para proporcionar ninguna función en el espacio de nombres std en absoluto: no hay ninguna necesidad porque todas esas funciones implicarían un tipo definido por el usuario y, por lo tanto, se encontrarían en el espacio de nombres del usuario. Formulado de manera diferente: creo que no tiene suerte con respecto a la optimización de los algoritmos para std::vector<bool> por el momento. Sin embargo, es posible que considere contribuir con versiones optimizadas para las implementaciones de código abierto (por ejemplo, libstdc++ y libc++ ).
STD solo encabeza la biblioteca y se envía con su compilador. Puedes mirar esos encabezados tú mismo. Para el vector<bool> de GCC, el vector<bool> impelemtation está en stl_bvector.h . Probablemente será el mismo archivo para otros compiladores también. Y sí, hay un fill especializado (mira cerca de __fill_bvector ).