Веревки STL в C ++

Опубликовано: 21 Января, 2022

Веревки представляют собой масштабируемую строковую реализацию. Они предназначены для эффективной работы всей струны в целом. Такие операции, как присваивание, конкатенация и подстрока, занимают время, которое почти не зависит от длины строки.

Веревка - это двоичное дерево, в котором каждый лист (конечный узел) содержит строку и длину (также известную как « вес »), а каждый узел дальше вверх по дереву содержит сумму длин всех листьев в своем левом поддереве. . Таким образом, узел с двумя дочерними элементами делит всю строку на две части: левое поддерево хранит первую часть строки, правое поддерево хранит вторую часть строки, а вес узла - это длина первой части.

Для операций с веревкой предполагается, что строки, хранящиеся в узлах, являются постоянными неизменяемыми объектами в типичном неразрушающем случае, что допускает некоторое поведение копирования при записи. Конечные узлы обычно реализуются как базовые строки фиксированной длины с прикрепленным счетчиком ссылок для освобождения, когда они больше не нужны, хотя могут использоваться и другие методы сборки мусора.

Примечание. Класс каната и заголовок каната являются расширениями SGI ; они не входят в стандартную библиотеку C ++.

Декларация:
Веревки определяются так же, как векторы, как «vector <int>» . Но для веревок персонажей мы можем использовать crope как «rope <char>» .

Ниже представлена программа для того же:

Program 1:

C++

// 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 << "
";
  
    return 0;
}

Output:

abcdef

На веревке разрешены операции :

push_back (): эта функция используется для ввода символа на конце веревки. Сложность времени: O (log N).
pop_back (): введенная в C ++ 11 (для строк), эта функция используется для удаления последнего символа из веревки. Сложность времени: O (log N).
вставка (целое х, crope г1): Вставки содержимого r1 до Й - ^го элемента. Сложность времени: в лучшем случае: O (log N) и в худшем случае: O (N).
erase (int x, int l): удаляет l элементов, начиная с x- ^го элемента. Сложность времени: O (log N).
substr (int x, int l): возвращает новую веревку, элементами которой являются l символов, начиная с позиции x . Сложность времени: O (log N).
replace (int x, int l, crope r1): заменяет l элементов, начинающихся с x- ^го элемента, элементами в r1 . Сложность времени: O (log N).
concatenate (+): соединить две веревки с помощью символа «+». Сложность времени: O (1).

Ниже представлена программа для того же:

Program 2:

C++

// 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 positon 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;
}

Output:

Initial rope: geeksforgeeks
Rope after pushing f: geeksforgeeksgfg
Rope after inserting gfg at positon 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

Функции емкости :

size (): возвращает длину веревки.
max_size (): размер самой длинной веревки, которую можно представить.

Ниже представлена программа для того же:

Program 3:

C++

// 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;
}

Output:

6
1836311902

Итераторы :

mutable_begin (): возвращает итератор, указывающий на начало веревки.
mutable_end (): возвращает итератор, указывающий на конец веревки.

Ниже представлена программа для того же:

Program 4:

C++

// 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;
}

Output:

cdefgh

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

Веревки STL в C ++

C++

C++

C++

C++

РЕКОМЕНДУЕМЫЕ СТАТЬИ