бирюльки

АНТОН ПАЛАГИН AKA TONY

Спецвыпуск: Хакер, номер #071, стр. 071-008-1

(TONY@EYKONTECH.COM)

СТРУКТУРЫ ДАННЫХ

ПРИ СОЗДАНИИ ПРАКТИЧЕСКИ ЛЮБОЙ ПРОГРАММЫ РАЗРАБОТЧИК ОБЯЗАТЕЛЬНО СТАЛКИВАЕТСЯ С ПРОБЛЕМОЙ ВЫБОРА СПОСОБА ПРЕДСТАВЛЕНИЯ ОБРАБАТЫВАЕМЫХ ДАННЫХ. СУЩЕСТВУЮТ МЕТОДОЛОГИИ РАЗРАБОТКИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ, ПРЕДЛАГАЮЩИЕ НАЧИНАТЬ ПРОЕКТИРОВАНИЕ ИМЕННО С ФОРМАЛИЗАЦИИ ДАННЫХ (ТАК НАЗЫВАЕМЫЕ DATA DRIVEN ПОДХОДЫ)

[массивы.]

Классический способ объединений данных, который можно встретить в любом языке программирования. Массив — это последовательный набор данных. Каждый элемент массива обладает своим порядковым номером. В языках программирования, которые позволяют обратиться напрямую к оперативной памяти, элементы массива хранятся в памяти друг за другом. Из кода C/C++ к элементам массива можно обратиться с помощью оператора «i», где i — порядковый номер элемента массива. Аналогом Си-массива является контейнер STL vector, который гарантирует последовательное размещение в памяти элементов массива, обеспечивает доступ к ним с помощью оператора «», а также механизма итераторов.

Естественно, функциональность вектора этим не ограничивается, он также позволяет вставлять новые элементы в начало, середину и конец вектора. Этим занимаются функции поэлементной и интервальной вставки insert, push_front и push_back. Кроме вставки вектор также позволяет производить поэлементное и интервальное удаление своих элементов с помощью функций erase и clear. Столь детальное внимание этому контейнеру уделяется неспроста, ведь правильный выбор контейнера, хранящего твои данные, гарантирует эффективное и безопасное выполнение кода. Об этом повествует книга Скотта Мейерса «Эффективное использование STL», которую необходимо иметь на своем рабочем столе.

Строго говоря, вектор — это наиболее общий тип контейнера, который больше всего похож на стандартный массив. Существуют его аналоги, такие как deque, rope, list, map, hash_map и т.д. Их необходимо выбирать, исходя из способа обращения к данным.

[производные массивов.]

У массивов есть несколько производных — многомерные массивы и ассоциативные массивы. Многомерные массивы хранят элементы, индексируемые не одним, а несколькими «координатами» (индексами), а ассоциативные массивы хранят элементы, индексируемые неким ключом, заданным программистом. Например, таким ключом может быть строка. Еще одной производной массива является стек. Если проводить ассоциации с реальной жизнью, то стек похож на женский чулок, в котором хранятся луковицы :). Если он завязан с одного конца, то ты можешь заложить в него только одну луковицу и забрать ее же. Самую первую заложенную луковицу ты сможешь забрать только после того, как вытащишь все луковицы, заложенные после нее. Это модель стека LIFO (last in first out). Если чулок развязать и закладывать луковицы с одной стороны, а извлекать с другой, то ты получишь стек FIFO (first in first out), также называемый очередью. Если пример с чулком не очень понятен, то просто попробуй купить билет в метро в восемь утра :). Стеки используются, например, при передаче аргументов в функцию. Когда ты работаешь с функцией, принимающей переменное число аргументов, ты как раз разматываешь подобный стек с помощью стандартных функций va_arg, va_start, va_end.