Глава ACM-W Manipal недавно организовала семинар по основам структур данных и стандартных библиотек шаблонов C ++, который проводили Харшита Бинани и я. На семинар было зарегистрировано более 120 человек!

Стандартная библиотека шаблонов C ++ - относительно простой, но очень мощный инструмент в области конкурентного программирования, и мы хотели, чтобы каждый в нашем колледже использовал его наилучшим образом. Помня о предстоящем сезоне размещения и просто чтобы помочь студентам улучшить свои навыки кодирования для соревнований, таких как ACM ICPC, мы рассмотрели такие структуры данных, как стеки, очереди, двухсторонние очереди, очереди с приоритетом, списки, хэш-карты, наборы, кучи и векторы. Это помогло участникам лучше понять язык C ++ в целом. Их использование с C ++ STL также было продемонстрировано с помощью кода. Руководство, содержащее основы структур данных, уже было разослано зарегистрированным участникам. Вот обзор семинара и все необходимые ресурсы, чтобы начать работу со структурами данных с использованием STL, собранными в одном месте!

Что такое C ++ STL?

Стандартная библиотека шаблонов C ++ (STL) - это набор классов, реализующих множество популярных и часто используемых алгоритмов и структур данных. Эти функции помогут вам создать более эффективный, производительный и повторно используемый код. Шаблон используется для определения функций и классов для общих типов данных, т. Е. Общий план функции / класса, который будет работать для любого тип данных и объекты класса.

Компоненты C ++ STL

  1. Контейнеры: как следует из названия, это определенные структуры данных, которые содержат или содержат данные. Пример: стеки, векторы, массивы, очереди.
  2. Итераторы: объекты, похожие на указатели, для обхода контейнеров.
  3. Алгоритмы: используйте файл заголовка algorithm.h - он содержит набор реализаций алгоритмов, таких как сортировка. В качестве альтернативы проверьте новый файл заголовка: bits / stdc ++. H. ( Убедитесь, что вы знаете, когда это полезно, а когда нет!)
  4. Функторы: (не требуется для нашего использования) объекты функций, которые можно параметризовать в их конструкторах - function.h

Типы контейнеров

  1. Последовательность: хранит элементы данных в последовательности. Пример: векторы, списки, деки, стеки, очереди.
  2. Ассоциативный: хранит связанные пары. Пример: наборы, карты, мультимножества, мультимножества. Они внутренне реализованы в виде дерева.
  3. Неупорядоченный ассоциативный: похож на связанные контейнеры, но хранится неупорядоченным образом. Еще быстрее, потому что они реализованы в виде хеш-таблиц.
  4. Функторы: функциональные объекты, которые можно параметризовать в их конструкторах. (функционал.h)

Итераторы

Итераторы - это объекты, через которые мы можем получить доступ к контейнерам. Указатели - это разновидности итераторов. Пример: имя массива на самом деле является указателем на первый элемент в массиве, который помогает нам получить доступ ко всем элементам массива. Они помогают нам перемещаться по контейнерам в определенном порядке для чтения или записи.

Типы итераторов (необязательно знать для целей кодирования, но помогают разобраться в концепциях языка): input (подходит для потоков ввода, таких как буферы клавиатуры / файлы только для чтения), вывод (подходит для потоков вывода, таких как текст на экране), вперед ( односвязные списки, неупорядоченные наборы, карты, множественные наборы / карты), двунаправленный (двусвязный списки, мультимножества / карты) и произвольный доступ (массивы, удаление из очереди и векторы).

Важные функции итератора (общие для многих STL)

  • begin (): возвращает итератор в начало контейнера.
  • end (): возвращает итератор в конец. Если begin == end контейнер пуст.
  • empty (): возвращает истину, если контейнер пуст, в противном случае - ложь.
  • rbegin (), rend (): такие же, как begin и end, но для обратных контейнеров.
  • size (): возвращает размер контейнера.

Массивы и векторы

С точки зрения непрофессионала, массивы представляют собой контейнеры фиксированного размера, в которых хранятся данные определенного типа. Здесь важно отметить, что элементы в массиве хранятся в памяти непрерывно. Массивы поддерживают произвольный доступ для вставки и удаления элементов.

Векторы похожи на массивы, за исключением того, что нам не нужно заранее указывать размер массива - по мере добавления элементов в вектор размер изменяется соответствующим образом. Они похожи на ArrayLists в Java. Следовательно, их намного проще использовать, когда мы не знаем, каким будет размер массива.

Вставка и удаление в конце векторов проста и эффективна, однако вставка в начало или в середину векторов - дорогостоящий процесс. (Подумайте, почему?) В последнем случае лучше использовать списки.

Совет от профессионалов: вы можете использовать auto в качестве типа данных любого итератора при его объявлении, и он автоматически назначит себя любому типу STL.

Вот код, демонстрирующий использование векторов с помощью STL. Попробуй сам!

Попробуйте ответить на следующие вопросы о векторах / массивах:

  1. Легкий:

2. Средняя сложность:

Стеки

Стек определяется как набор элементов, в котором вставка нового элемента и удаление элементов, уже находящихся в стеке, производятся только на одном конце. Этот конец называется вершиной стека. Если элемент вставлен в стек, верхнее значение увеличивается или перемещается вверх от его текущего положения, а если элемент удаляется, верхнее значение уменьшается или перемещается вниз. Важно помнить: это линейная структура данных, данные хранятся друг над другом, используется стратегия последний пришел - первый ушел, вставка и удаление происходит на одном конце, который называется верхним, реализация стека выполняется с использованием одномерного массива.

Здесь приведен небольшой отрывок о том, как использовать стеки с STL. Мы рекомендуем вам использовать те же базовые концепции векторов и самостоятельно изучить STL.

Совет от профессионала: нельзя перемещаться по стеку от начала до конца, как по векторам. (Попробуйте и узнайте, почему!)

Постарайтесь решить следующий вопрос наиболее эффективным способом. (Подсказка: это можно решить за O (1) временную сложность!)

Очереди

Вы когда-нибудь ждали на автобусной остановке, чтобы сесть в автобус в очереди? Новый человек может присоединиться только в конце очереди, тогда как первый человек, который садится в автобус (и, следовательно, покидает очередь), является человеком в начале очереди. Именно так работает эта структура данных. Он следует стратегии первым пришел - первым обслужен.

Я не буду предоставлять здесь какие-либо фрагменты кода для очередей, потому что я хочу, чтобы вы, ребята, попытались реализовать его сами! Очередь имеет ту же функцию push и pop, что и стеки, и, если вы еще не догадались, файл заголовка, который нужно импортировать в начале кода, называется очередью.

Пища для размышлений: как вы думаете, можно ли перемещаться по очереди, как векторы?

Deques

Подобно очередям, двухсторонние очереди имеют дополнительное преимущество, позволяя выполнять операции push и pop на обоих концах очереди, т. Е. Элементы могут перемещаться не только сзади, но и на переднем конце, а элементы могут удаляться с обоих концов как хорошо. Кроме того, структура данных двухсторонней очереди позволяет вам перемещаться по очереди от начала до конца, даже если в этом нет необходимости.

Приоритетные очереди

Здесь важно не ввести вас в заблуждение по названию. Приоритетные очереди представляют собой структуры данных внутренней кучи (по умолчанию максимальная куча). Кучи - это полные двоичные деревья, в которых родительский узел всегда больше, чем 2 его дочерних узла в случае максимальной кучи, и наоборот, в случае минимальной кучи. Это означает, что корень максимальной кучи является максимальным элементом данных значений, к которым можно получить доступ за время O (1). Это внутренняя работа приоритетной очереди. Очередь приоритетов можно понимать как структуру данных, которая назначает приоритет каждому значению и сохраняет каждый элемент в соответствии с приоритетом, а не в порядке поступления, и является эффективной по времени.

Пища для размышлений: как вы думаете, можно ли использовать эту структуру данных для решения вопроса о максимальном количестве элементов, заданного в подразделе стеки? Если да, то как?

Вот небольшой фрагмент кода, демонстрирующий использование очереди приоритетов. Помните, что он находится в самом файле заголовка очереди. Также узнайте, как использовать приоритетную очередь, в которой элементы хранятся в виде минимальной кучи.

Связанные списки

Связанный список - это структура данных, которая состоит из последовательности узлов, так что в каждом узле есть поле, содержащее элемент данных, и другое поле, в котором хранится ссылка на следующий узел в последовательности. Связанные списки используются в качестве основного компонента графиков. Связанный список:

  • не имеет непрерывного хранилища памяти - какая бы случайная память ни была доступна, данные хранятся там
  • не обеспечивает произвольный доступ
  • вставка, удаление намного дешевле массивов

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

Наборы и хэш-карты

Вы можете сказать, что это самые важные и чрезвычайно полезные структуры данных. Этот фрагмент из HackerEarth должен оказаться полезным для понимания концепции:

Рассмотрим сценарий: вам дан очень большой массив с большими числами (который может иметь повторяющиеся элементы). Затем вам дадут номер и просто попросят проверить, существует ли данное число в массиве или нет. Здесь можно использовать хеширование вместо выполнения линейного поиска для улучшения временной сложности. Используйте массив bool, где индексы будут элементами в массиве, если элементы массива маленькие (если элементы массива большие, скажем, в миллионы, тогда мы не сможем создать массив такого большого размера). Итак, мы используем хеш-функцию, а затем хеш-элементы массива, а затем используем наш массив bool для хранения сопоставленных значений. Наборы делают это очень простым для нас. Все, что нам нужно сделать, это добавить значения массива в набор, а затем просто проверить за время O (1), существует ли данный элемент в наборе или нет. Set будет внутренне хранить все элементы только в виде хеш-таблицы, поэтому нам не нужно беспокоиться о реализации хеш-функции и связанного кода.

Предположим, мы расширяем эту проблему, чтобы не только определить, присутствует ли элемент в массиве или нет, но и найти количество вхождений данного элемента. Эффективный способ сделать это - также сохранить счетчики всех значений. Мы можем создать пару ключ-значение для каждого элемента в массиве. Ключом будет каждый уникальный элемент, и его значение будет указывать его количество в массиве. Затем мы сохраняем эту пару в хэш-карте, и мы можем получить доступ к счетчику любого элемента за время O (1). Простой способ визуализировать хэш-карту - представить себе огромную строку из n сегментов, помеченных от 1 до n, каждая из которых содержит определенное количество элементов. Чтобы узнать количество элементов в любой корзине b, все, что нам нужно сделать, это перейти к этой корзине и заглянуть внутрь.

Карты и наборы хеширования увеличивают сложность пространства, но значительно улучшают временную сложность в большинстве сценариев.

Примечание. Это одна из наиболее важных структур данных, которые задают при приеме на собеседование.

Вот фрагменты кода для наборов и хэш-карт на C ++:

Примечание. Ключи в хэш-карте должны быть уникальными. Для повторяющихся ключей используйте мульти-карту.

Вот несколько интересных вопросов, попробуйте найти наиболее эффективные решения этих проблем (Подсказка: используйте хеш-карты или наборы!):

1)

2)

3)

4)

Кучи

Я уверен, что, прочитав эту невероятно длинную статью, вы теперь обратили внимание на использование STL. Однако позвольте мне заверить вас, что кучи используются совсем по-другому. Посмотрите эту ссылку на GeeksForGeeks, чтобы получить очень хорошее объяснение: https://www.geeksforgeeks.org/heap-using-stl-c/

Фактически, ознакомьтесь с GeeksForGeeks, чтобы найти множество ресурсов по всем остальным C ++ STL и очень сложные коды, а также список функций, которые можно использовать для каждого из них.

Сортировка

Ознакомьтесь с этой действительно короткой статьей о том, как сортировать массивы и векторы с помощью одного оператора, и даже не беспокойтесь об использовании правильного типа алгоритма сортировки в правильном сценарии (да, я действительно сказал однострочная сортировка! )

Https://www.geeksforgeeks.org/sort-c-stl/

Заключение

Важно понимать, что цель этой статьи (и семинара) состоит только в том, чтобы предоставить базовое введение, чтобы помочь вам получить представление о том, какие существуют структуры данных и как начать работу с STL в C ++. Хорошее знание языка может иметь множество преимуществ. Например, в тесте кодирования, в то время как другие ваши коллеги, не имеющие знаний о STL, будут тратить много времени на определение каждой структуры данных, вы можете использовать этот предопределенный набор классов и завершить свой код до того, как другие одноранговые узлы даже достигнут int main ( ). Эти STL не только экономят ваше время, но и делают ваш код более эффективным и аккуратным. С практикой становится очень легко и удобно использовать эти STL. Надеюсь, вы могли бы извлечь из всего этого что-нибудь полезное!

использованная литература

#acmw #manipal # структуры данных #stl #workshop #womenwhocode #empowerment