pairs - vector c++ geeksforgeeks

¿Qué es el STL? (6)

No soy un programador de C ++ y tengo dificultades para entender las explicaciones dadas en los sitios web. No entiendo contenedores o iteradores y no tengo planes para aprender C ++ en el futuro cercano. Entonces, en términos simples: ¿Qué es el STL y qué puede hacer por mí? ¿Cómo se compara con algo como la biblioteca de Python Standard o glibc?

El STL es la biblioteca de plantillas estándar. Es un subconjunto de la biblioteca estándar de C ++.

El STL proporciona implementaciones genéricas de algoritmos y contenedores útiles.

Los contenedores proporcionan cualquier método fácil de almacenar datos en el programa y luego encontrar, ordenar y realizar otros cálculos sobre esos datos.

Es una biblioteca para facilitar ciertas cosas, como la manipulación de cadenas, vectores, listas enlazadas, etc. STL le evitará tener que escribir parte del código de nivel inferior y le permitirá enfocarse más en el código de su aplicación.

Las implementaciones de la Biblioteca de plantillas estándar son inútiles para usted si no es un programador de C ++. Sin embargo, las ideas trascienden cualquier lenguaje de programación.

Es una biblioteca de estructuras de datos (por ejemplo, mapas, listas, vectores, etc.). Incluye iteradores para abstraer el recorrido de esas estructuras de datos y algoritmos para operar en ellas. Otros idiomas también usan estas ideas, por lo que si los aprende en un idioma, serán familiares en otros.

STL es la biblioteca de plantillas estándar. Es una biblioteca de funciones y clases que puedes usar. Tiene muchos de los algoritmos básicos y estructuras de datos de informática básica. Si planea permanecer en C ++, debe planear aprender esta u otra biblioteca de recursos.

El código es utilizado por muchas personas en todo el mundo, por lo que puede sentirse cómodo de que el código esté bien probado y sea bien conocido.

Para entender el STL, vas a tener que entender algunos aspectos de C ++ al menos. Haré todo lo posible para explicarlo. La estructura es engañosamente simple. Donde brilla la biblioteca está en cómo su uso puede simplificar muchas tareas complejas. Sin embargo, voy a apegarme a algunos ejemplos muy simples, ya que cualquier otra cosa probablemente confundirá a alguien que no conozca C ++, y porque no quiero escribir una novela. ;)

Primero, algo de historia. El STL (Standard Template Library) se desarrolló por separado y luego se sometió al comité estándar de C ++ para su consideración, dándoles la opción de adoptarlo en el idioma. Pero no fue desarrollado como parte del estándar C ++, y por esta razón, está diseñado en un estilo que es muy diferente del resto de la biblioteca estándar de C ++. Si recuerdo mi historia antigua, al comité estándar también le llevó un buen rato entender el STL y acostumbrarse a él. Cuando inicialmente lo vieron, no estaban muy interesados en él, pero después de un tiempo, se dieron cuenta de lo poderoso y bien diseñado que era. Entonces fue adoptado en el lenguaje. Todo esto sucedió a fines de la década de 1990, cuando el lenguaje se acercaba a la estandarización ISO.

En esencia, el STL proporciona la funcionalidad más fundamental que espera de una biblioteca estándar: la capacidad de almacenar secuencias de datos y la capacidad de procesar estas secuencias.

Cada otro idioma tiene una parte de Colecciones / Contenedores de su biblioteca estándar, que contiene implementaciones de matrices dinámicas (conocidas como listas de arreglos en Java, listas en C # y vectores en C ++), listas enlazadas, diccionarios y otras estructuras de datos comunes.

También suelen proporcionar algunos mecanismos para atravesar estas estructuras. (Enumeradores o iteradores, por ejemplo)

El STL proporciona la misma funcionalidad en C ++, pero lo hace de una manera inusualmente elegante y con algunas abstracciones interesantes.

El STL se divide limpiamente en tres componentes separados:

Los contenedores (como se describió anteriormente, cada lenguaje tiene estos: matrices, ArrayList, Dictionary, Set, LinkedList, etc.) Cualquier estructura de datos que pueda almacenar una colección de objetos es un contenedor en C ++)
Los algoritmos (Todos los idiomas también los tienen en alguna forma. Los algoritmos son funciones para procesar secuencias de elementos.) Por ahora, supongamos que una secuencia es un contenedor. Eso es un poco simplificador, pero llegaremos a eso. Los algoritmos cumplen una amplia gama de propósitos, desde una función for_each() que le permite aplicar una función a cada elemento de una secuencia, o la transform() relacionada transform() que aplica una función a cada elemento, y almacena el resultado en una secuencia separada (muy parecido al funcionamiento del mapa en lenguajes funcionales), o acumular (similar a plegar en lenguajes funcionales), pero también funciones de clasificación o búsqueda, y funciones que le permiten copiar secuencias enteras.
Y, por último, el pegamento que une contenedores y algoritmos: Iteradores. Como dije antes, las secuencias (que son en lo que trabajan los algoritmos) no son lo mismo que los contenedores. Los elementos en un contenedor ciertamente constituyen una secuencia, pero los primeros cinco elementos en un contenedor también son una secuencia. O cualquier otro elemento en un contenedor es una secuencia. Los datos leídos directamente de una secuencia de archivos también pueden tratarse como una secuencia. Incluso los datos que se generan sobre la marcha (por ejemplo, la secuencia de fibonacci) se pueden tratar como una secuencia de valores. Las secuencias no tienen que asignarse a un contenedor, o incluso a datos que existen en la memoria, aunque ese es el uso más común.

Tenga en cuenta que esto no es una superposición entre estas tres áreas. Un contenedor almacena (y posee) datos, y produce iteradores. Los iteradores le permiten inspeccionar, modificar y recorrer los datos. Y los algoritmos operan en rangos de iteradores

Conceptualmente hablando, un iterador tiene dos funciones. Señala algunos datos, y se puede mover en la secuencia (dependiendo del tipo de iterador, diferentes operaciones de movimiento pueden estar disponibles. Casi todos los iteradores pueden moverse al siguiente elemento. Algunos también pueden moverse al anterior, y algunos pueden saltar distancias arbitrarias hacia atrás y hacia adelante). Si estás familiarizado con C, esto va a sonar muy parecido a los indicadores, y eso no es una coincidencia. Los iteradores se modelan como una generalización de punteros, y de hecho, los punteros también son iteradores válidos. Todos los algoritmos STL funcionan tanto en punteros como en iteradores "reales".

Lo que esto significa es que cualquier secuencia de datos puede ser representada por un par de iteradores: el primer iterador apunta al primer elemento en la secuencia, y el segundo señala uno pasado el final de la secuencia.

Eso permite una sintaxis bastante simple para atravesar secuencias en un bucle:

std::vector<int> container; for (iter it = container.begin(); it != container.end(); ++it) { // perform some operations on the iterator (it) or the element it points to (*it) ++(*it); // increment the value the iterator points to }

O podemos aplicar un algoritmo a la secuencia:

std::sort(container.begin(), container.end());

Tenga en cuenta que la función de ordenación no sabe o no le preocupa que esté trabajando en un vector. Se pasan dos iteradores, y estos podrían ser de cualquier tipo. Pueden ser simples punteros en una matriz, iteradores de listas enlazadas o cualquier otro tipo de iterador válido.

Podemos generalizar un poco la función de clasificación suministrando nuestra propia función comparador (cualquier función que tome dos valores y devuelva verdadero si la primera es estrictamente menos que la otra)

// sort in descending order, by passing in a custom comparer which uses greater than instead of less than bool greater(int lhs, int rhs) { return lhs > rhs; } std::sort(container.begin(), container.end(), greater);

Por supuesto, también podríamos ordenar los primeros cinco elementos del vector:

std::sort(container.begin(), container.begin()+5);

Las funciones begin () y end () son solo funciones de conveniencia para obtener iteradores de un contenedor. No tenemos que usarlos directamente.

Otro buen truco es que las transmisiones también se pueden generalizar en iteradores. Así que vamos a leer todos los enteros de un archivo y copiarlos en una matriz (las matrices son tipos simples de C, por supuesto, por lo que no son contenedores adecuados y no tienen iteradores. Pero los punteros funcionan bien)

int arr[1024]; std::ifstream file("something.txt"); // (note, this assumes <= 1024 integers are read) std::copy(std::istream_iterator<int>(file) // create an iterator pointing to the current position in the file stream , std::istream_iterator<int>() // and our "end" iterator. When we reach the end of the stream, testing the two iterators for equality will yield true, and so the operation will halt , arr);

Lo único del STL es lo flexible y extensible que es. Interopera limpiamente con el código C (los punteros son iteradores legales), se puede extender de manera sencilla y fácil (puede escribir sus propios tipos de iteradores si lo desea. La mayoría de los algoritmos toman predicados personalizados de los comparadores, como el que mostré arriba, y puede definir sus propios contenedores. Es decir, cada uno de los tres pilares del STL puede anularse o ampliarse, por lo que podría decirse que STL es más una estrategia de diseño que cualquier cosa. Puede escribir el código STL aunque esté utilizando sus propios contenedores, iteradores y algoritmos. Y debido a que cada uno de estos tres pilares está claramente separado de los demás, se pueden intercambiar de forma mucho más fácil que en la mayoría de los otros idiomas donde estas tres responsabilidades se mezclan y comparten las mismas clases. Algoritmo no sabe en qué contenedor se almacena la secuencia en la que está operando. Solo sabe que los iteradores que se han pasado se pueden desreferenciar para obtener acceso a los datos. Un contenedor no tiene que admitir todo los algoritmos estándar. Simplemente tiene que ser capaz de producir un par de iteradores, y luego toda la funcionalidad es gratuita.

Compare esto con, por ejemplo, Java, donde cada clase de colección tiene que implementar su propia búsqueda, su propia clase, su propio todo. En C ++, solo necesitamos una implementación de find (). Toma dos iteradores y el valor a buscar, y recorre la secuencia buscando el valor. Y así, funciona en cualquier tipo de contenedor, incluso los que yo mismo defino.

Otra característica notable del STL es que hay literalmente cero pérdida de rendimiento al usarlo. Las plantillas de C ++ son todas sustituidas en tiempo de compilación, produciendo código que puede optimizarse tan agresivamente como si hubiera codificado manualmente todo en C. La función de ordenación anterior perdería algo de rendimiento porque le paso un puntero de función como mi comparador personalizado , que normalmente no se puede insertar, pero que se pueden corregir si lo definimos así:

struct greater { bool operator()(int lhs, int rhs) { return lhs > rhs; } }; std::sort(container.begin(), container.end(), greater());

Ahora ya no pasamos un puntero a la función, sino un objeto. Y las funciones de miembro (como operador ()) pueden estar en línea. Así que esta función de clasificación será tan eficiente como cualquier cosa que pueda codificar a mano en C.

Y nuevamente, ni siquiera tiene que agregar complejidad a la función de clasificación. De hecho, el género tiene precisamente dos sobrecargas. Uno que toma una función de comparación, y otra que no.

La función de ordenación no necesita saber si se pasa un puntero de función o un objeto. Siempre que la sintaxis "X (a, b)" sea válida, donde X es el valor que se aprobó como comparador, y a, b los elementos para comparar, la misma implementación de la función de clasificación funcionará. Y debido a que mi objeto greater sobrecargó el operador (), esa sintaxis es válida tanto para este objeto como para el puntero de función que aprobamos anteriormente. El código STL obtiene una gran cantidad de funcionalidades de forma gratuita explotando trucos como este. La misma implementación de una función funciona con tipos de argumentos muy diferentes debido a la forma en que funcionan las plantillas de C ++.

La Biblioteca de plantillas estándar era una biblioteca escrita en C ++ antes de la estandarización de C ++. Incluía cosas geniales como algoritmos de clasificación y contenedores (e iteradores, con los cuales usar estas características).

Partes de la biblioteca estándar de C ++ , cuando se estandarizaron en 1998, se basaron en partes de la STL; es desde que evolucionó (a través del estándar de 2003, y especialmente ahora con C ++ 0x).

La Biblioteca Estándar de C ++ es implementada por varios proveedores de compiladores (y sus amigos) y se envía con su cadena de herramientas favorita.
Esto es lo que probablemente usarás: el STL ya está casi obsoleto.

_{Tenga en cuenta que muchos programadores (incluidos algunos prolíficos autores de libros) todavía usan el término "STL" por hábito para referirse a la Biblioteca estándar de C ++ (oa las partes de la misma que se basaron originalmente en el STL), aunque esto sea incorrecto.} _{Siempre que sepa la distinción técnica, debería estar bien.}

Espero que esto ayude.