¿Qué se utiliza para implementar el vector stl internamente?
He estado tan ocupado últimamente que todavía quiero escribir algo propio. No sabía qué escribir, así que finalmente decidí intentar implementar varias colecciones STL de uso común, en primer lugar para profundizar mi comprensión de STL y, en segundo lugar, para ver si tengo la capacidad de implementar esto. Nuestro objetivo es 1 ser compatible con STL; 2 maximizar la implementación de la interfaz en STL y mantener la coherencia. En otras palabras, las colecciones en STL funcionarán incluso si las escribo. Este blog presentará el principio y la implementación de los vectores.
Primero se presentará la implementación general de los vectores y más adelante se proporcionará el código fuente completo.
Nuevo elemento: El vector pasa por una matriz de elementos continuos. Si la colección está llena, al agregar nuevos datos, debemos asignar una memoria mayor, copiar los datos originales, liberar la memoria anterior e insertar la. nuevo elemento. Inserte nuevos datos en el último push_back insertado y en cualquier posición insertada a través del iterador. Aquí estamos hablando de insertar a través del iterador. La posición a insertar se conoce a través de la distancia entre el iterador y el primer elemento, es decir, int index =. iter-comienzo (). Todos los elementos posteriores a este elemento retrocederán una posición y los elementos agregados se almacenarán en la posición vacía.
void insert(const_iterator iter, const Tamp; t)
{
int index=iter-begin()
if (indexlt;tamaño_)
{
if ( tamaño_==capacidad_)
{
int capa=calcularCapacidad();
newCapacity(capa);
}
memmove(buf index 1, buf index.(size_-index)*sizeof(T)); >
buf[index]=t;
size_ ;
}
}
Eliminar elementos: eliminar y agregar De manera similar , Hay dos formas de eliminar, una es eliminar el último elemento pop_back y la otra es eliminar cualquier elemento mediante el borrado del elemento iterador (iter). Para eliminar a través de un iterador, primero debe encontrar la posición del elemento que se eliminará, es decir, int index = iter-begin(); cada elemento después de esta posición debe avanzar un elemento. También sabemos que borrar no libera memoria, solo la inicializa con los valores predeterminados.
Borrar todos los elementos: esto es solo una llamada de bucle para borrar, por lo que no se liberará memoria cuando se eliminen todos los elementos. La memoria se libera en el destructor.
borrar iterador(const_iterator iter)
{
int index=iter-begin()
if (indexlt; size_ amp ;amp; size_gt;0)
{
memmove(buf index,buf index 1,(size_-index)*sizeof(T)); buf[--size_]=T();
}
Devolver iterador(iter);
}
Iterador iteraotr Sí Los iteradores, una parte importante de STL, facilitan el almacenamiento de elementos en una colección.
STL escribirá un iterador para cada colección. El iterador es en realidad un contenedor de un puntero. Implementa algunos métodos comunes, como --, ! =, ==, *, -gt. las colecciones especiales en STL Debido a que cada elemento en el vector es continuo, puede usar punteros cuando implemente el vector usted mismo, como typedef T * iterator; typedef const T * const_iterator. Si la función STL puede operar la colección de manera conveniente. escribir, la implementación del iterador se hereda mejor de std::iteratorlt; std::forward_iterator_tag, Tgt;. Mi implementación del iterador vectorial es más o menos así:
templatelt; typename Tgt;
class viterator: public std::iteratorlt; >
El código completo se proporcionará más adelante. El código fuente de std::iteratorlt; std::forward_iterator_tag, Tgt; es el siguiente:
templatelt; > clase _Ty,
clase _Diff = ptrdiff_t,
clase _Pointer = _Ty *,
clase _Reference = _Ty>
iterador de estructura
{ //Tipo básico para todas las clases de iterador
typedef _Category iterator_category;
typedef _Ty value_type
typedef _Diff Difference_type; /p>
typedef _Diff Distance_type; // reservado
typedef _Pointer puntero;
typedef _Referencia de referencia
}; >El iterador no contiene ningún miembro, solo define un conjunto de tipos, por lo que heredarlo no hará que su estructura sea más grande. Este conjunto de tipos es un contrato interno de STL. Las funciones en STL asumen que cada iterador está definido. Estos tipos están definidos. , siempre que su iterador defina estos tipos, puede usarlos en la colección de funciones STL.
El código fuente para mi implementación vectorial es el siguiente:
Ver el código
El nivel del código de muestra se ejecuta de la siguiente manera:
struct Punto
{
Punto(int x_=0, int y_=0): x(x_), y(y_){}
int x, y;
};
bool operatorlt; (const Puntoamp; p1, const Puntoamp; p2)
{
if(p1.xlt; p2.x)
{
Devuelve verdadero;
}si no (p1.xgt; p2.x)
{
Devuelve falso;
}
Devuelve p1.ylt; p2.y
}
void cvectorTest; ()
{
cvectorlt; vect;
for (int i=0; ilt; 10; i)
{
Punto p(i, i);
vect.push_back(p);
}
cvectorlt;: iterador iter=vect .begin();
while (iter!=vect.end())
{
coutlt;lt "[" lt; ;lt; iter -gt;x lt;lt; " " lt;lt; iter-gt;y lt;lt;"], " p> iter=vect.begin()
vect .insert(iter, Point(55))begin();
while (iter!=vect.end() )
{
coutlt; ; "[" lt; iter-gt;"], ";
iter;
}
std::sort(vect.begin(), vect.end()
p>
coutlt;lt;endllt;lt;endllt); ;lt; "Después de ordenar:"lt;lt;endl;
iter=vect.begin()
while (iter!=vect.end())
{
coutlt;lt; "[" lt;lt; iter-gt;x lt;lt; " " lt.iter-gt;y lt;lt;"], ";
iter;
}
vect.begin();
while (iter!erase(vect.begin() 10);
vect.erase(vect.begin() 10);
coutlt; endllt; lt;endllt;lt; ;lt;endl;
sitio
r=vect.begin();
while (iter!=vect.end())
{
cout lt "[" lt; ; iter-gt; x lt; " " lt; iter-gt; "], " /p>
vect.clear(); coutlt;lt; endllt;lt;endllt;lt; "Después de ejecutar clear"lt;lt;endl;
coutlt ;lt; "size="lt;lt;vect.size()lt;lt ;",capacity="lt;lt;vect.capacity();
cvectorlt;Pointgt; vect1;
p>
for (int i=10; ilt; 20; i)
{
Punto p(i, i);
vect1. /p>
coutlt;lt;endllt;lt;lt;endllt;lt; "Copiar datos de otro cvector:"lt;lt;lt;endl ;
cvectorlt; .begin())begin(), vect1.end());
vect2.pop_back()
vect2.pop_back();
para (int i=0; ilt; vect2.size(); i )
{
coutlt;lt; "[ "lt;lt;vect2[i].xlt;lt ;", "lt;lt;vect2[i].ylt;lt;"], ";
}
coutlt;lt;endl
}
Habrá implementaciones de listas, conjuntos, mapas, etc. más adelante. Por favor estad atentos...