Cuerdas STL en C++

Las cuerdas son implementaciones de cuerdas escalables. Están diseñados para una operación eficiente que involucra a la string como un todo. Las operaciones como la asignación, la concatenación y la substring toman un tiempo que es casi independiente de la longitud de la string.

Una cuerda es un árbol binario en el que cada hoja (Node final) contiene una string y una longitud (también conocida como » peso «), y cada Node más arriba en el árbol contiene la suma de las longitudes de todas las hojas en su subárbol izquierdo. . Un Node con dos hijos divide toda la string en dos partes: el subárbol izquierdo almacena la primera parte de la string, el subárbol derecho almacena la segunda parte de la string y el peso de un Node es la longitud de la primera parte.

Para las operaciones de cuerda, se supone que las strings almacenadas en los Nodes son objetos inmutables constantes en el caso típico no destructivo, lo que permite cierto comportamiento de copia en escritura. Los Nodes de hoja generalmente se implementan como strings básicas de longitud fija con un recuento de referencia adjunto para la desasignación cuando ya no se necesitan, aunque también se pueden usar otros métodos de recolección de elementos no utilizados.

Nota: La clase de cable y el encabezado de cable son extensiones SGI ; no forman parte de la biblioteca estándar de C++.

Declaración:
Las cuerdas se definen de la misma manera que los vectores como “vector<int>” . Pero para cuerdas de caracteres, podemos usar crope como “rope<char>” .

A continuación se muestra el programa para el mismo:

Programa 1:

// C++ program to illustrate the use
// of ropes using Rope header file
#include <ext/rope>
#include <iostream>
 
// SGI extension
using namespace __gnu_cxx;
 
using namespace std;
 
// Driver Code
int main()
{
    // rope<char> r = "abcdef"
    crope r = "abcdef";
 
    cout << r << "\n";
 
    return 0;
}

abcdef

Operaciones permitidas en Cuerda :

• push_back(): esta función se usa para ingresar un carácter al final de la cuerda. Complejidad temporal: O(log N).
• pop_back(): Introducida desde C++11 (para strings), esta función se usa para eliminar el último carácter de la cuerda. Complejidad temporal: O(log N).
• insert(int x, crope r1): Inserta el contenido de r1 antes del x ^-ésimo elemento. Complejidad de tiempo: Para el mejor de los casos: O(log N) y para el peor de los casos: O(N).
• erase(int x, int l): Borra l elementos, comenzando con el x ^-ésimo elemento. Complejidad temporal: O(log N).
• substr(int x, int l): Devuelve una nueva cuerda cuyos elementos son los l caracteres que comienzan en la posición x . Complejidad temporal: O(log N).
• replace(int x, int l, crope r1): Reemplaza los l elementos que comienzan con el x ^-ésimo elemento con los elementos en r1 . Complejidad temporal: O(log N).
• concatenar (+): concatenar dos cuerdas usando el símbolo ‘+’. Complejidad Temporal: O(1).

A continuación se muestra el programa para el mismo:

Programa 2:

// C++ program to illustrate the use
// of ropes using Rope header file
#include <ext/rope>
#include <iostream>
 
// SGI extension
using namespace __gnu_cxx;
using namespace std;
 
// Driver Code
int main()
{
    // rope<char> r = "abcdef"
    crope r = "geeksforgeeks";
 
    cout << "Initial rope: "
         << r << endl;
 
    // 'g' is added at the
    // end of the rope
    r.push_back('g');
    r.push_back('f');
    r.push_back('g');
 
    cout << "Rope after pushing f: "
         << r << endl;
 
    int pos = 2;
 
    // gfg will be inserted
    // before position 2
    r.insert(pos - 1, "gfg");
 
    cout << "Rope after inserting "
         << "gfg at position 2: " << r
         << endl;
 
    // gfg will be deleted
    r.erase(pos - 1, 3);
 
    cout << "Rope after removing gfg"
         << " inserted just before: "
         << r << endl;
 
    // Replace "ee" with "00"
    r.replace(pos - 1, 2, "00");
 
    cout << "Rope after replacing "
         << "characters: " << r
         << endl;
 
    // Slice the rope
    crope r1 = r.substr(pos - 1, 2);
 
    cout << "Subrope at position 2: "
         << r << endl;
 
    // Removes the last element
    r.pop_back();
    r.pop_back();
    r.pop_back();
 
    cout << "Final rope after poping"
         << " out 3 elements: " << r;
 
    return 0;
}

Initial rope: geeksforgeeks
Rope after pushing f: geeksforgeeksgfg
Rope after inserting gfg at position 2: ggfgeeksforgeeksgfg
Rope after removing gfg inserted just before: geeksforgeeksgfg
Rope after replacing characters: g00ksforgeeksgfg
Subrope at position 2: g00ksforgeeksgfg
Final rope after poping out 3 elements: g00ksforgeeks

Funciones de capacidad :

• size(): Devuelve la longitud de la cuerda.
• max_size(): Tamaño de la cuerda más larga garantizada para ser representable.

A continuación se muestra el programa para el mismo:

Programa 3:

// C++ program to illustrate the use
// of ropes using Rope header file
#include <ext/rope>
#include <iostream>
 
// SGI extension
using namespace __gnu_cxx;
using namespace std;
 
// Driver Code
int main()
{
    // rope<char> r = "abcdef"
    crope r = "abcdef";
 
    cout << r.size() << endl;
    cout << r.max_size() << endl;
    return 0;
}

6
1836311902

Iteradores :

• mutable_begin(): Devuelve un iterador que apunta al comienzo de la cuerda.
• mutable_end(): Devuelve un iterador que apunta al final de la cuerda.

A continuación se muestra el programa para el mismo:

Programa 4:

// C++ program to illustrate the use
// of ropes using Rope header file
#include <ext/rope>
#include <iostream>
 
// SGI extension
using namespace __gnu_cxx;
using namespace std;
 
// Driver Code
int main()
{
    // rope<char> r = "abcdef"
    crope r = "abcdef";
 
    rope<char>::iterator it;
    for (it = r.mutable_begin();
         it != r.mutable_end(); it++) {
 
        // Print the value
        cout << char((*it) + 2)
             << "";
    }
 
    return 0;
}

cdefgh