бет 2/2 Дата 05.09.2020 өлшемі 0,69 Mb. #77415
Строки В языке C строки было принято представлять в виде массива символов: В языке C++ для представления строки используется класс string Обе структуры линейны, но вторую принято считать более удобной, безопасной и простой в использовании Класс String #include Поддерживает операции: Удаления посл-ти символов (erase) Поиска подстроки (find) Возврата подстроки (substr) Замены подстроки (replace ) Вставки подстроки (insert ) Стандартная библиотека шаблонов STL Контейнеры STL Контейнеры в STL – обобщенный классы, моделирующие различные структуры данных Например: #include #include #include Контейнеры STL #include // строки #include // динамический массив #include // двусвязный список
#include // дек #include // очередь #include // стэк #include // множество #include // ассоциативный список Итераторы Итераторы – интерфейс между контейнерами и алгоритмами. Итератор - это универсальный способ доступа к элементам контейнера. Ведет себя как указатель. Пример: string A = "This is a string"; string::iterator it; // создание итератора for (it = A.begin(); it != A.end(); ++it) { cout << *it << endl; } Алгоритмы Реализованы как свободные функции, а не члены-функции Использование - #include Все алгоритмы работают с итераторами на контейнерах Для корректной работы – использование пространства имен std Использование Vector Vector – динамически расширяемый массив Объявление – vector v(); Доступ к элементам – так же как в массиве, сложность O(1) Добавление элемента – O(1) в конец, O(n) в других случаях Поиск O(n) Дек С точки зрения программиста – использование схоже с Vector Отличие в реализации – Vector – это массив , когда как для удобство добавления элемента Deque реализован как множество массивов Использование Дека // Предикат bool is_odd(int i) { } int main(int argc, char* argv[]) { deque numbers; for (int i = 0; i < 20; i++) { } cout << count(numbers.begin(), numbers.end(), 10) << endl; cout << count_if(numbers.begin(), numbers.end(), is_odd) << endl; return EXIT_SUCCESS; } Связные списки Связный список - это разновидность линейных структур данных, представляющая собой последовательность элементов, обычно отсортированную в соответствии с заданным правилом. Последовательность может содержать любое количество элементов , поскольку при создании списка используется динамическое распределение памяти. Каждый элемент связного списка представляет собой отдельный объект, содержащий поле для хранения информации и указатель на следующий элемент списка (а в случае двусвязного списка в объекте хранится также указатель на предыдущий элемент). Использование list Объявление - list l1; Добавление элемента – O(n) в худшем случае // Добавить элемент после 1ого list l(10); list::iterator it = l.begin(); it++; l.insert(it, 5); Удаление элемента – O(n) в худшем случае // Удаление второго элемента list l(10); list::iterator second = l.begin(); second++; l.erase(second); Очередь queue q; // добавить и удалить q.push(1); q.pop(); // доступ к первому и последнему q.push(1); q.push(2); cout << q.front() << endl; cout << q.back() << endl; // размер cout << q.size() << endl; cout << q.empty() << endl; Стек Очередь – линейная структура данных, удовлетворяющая принципу FILO(первый пришел – последний ушел) Поддерживает добавление элемента в конец, доступ к первому и последнему, удаление последнего элемента Стек-Пример stack s; // Добавление и удаление элемента из вершины стека s.push(1); s.pop(); // Доступ к вершине стека s.push(10); s.push(11); cout << s.top() << endl; // Размер cout << s.size() << endl; cout << s.empty() << endl; Достарыңызбен бөлісу:
