Перевод книги Julian’а Smart’а – Глава XIII – Структуры данных (Часть 1)

Скачать PDF-версию (327 кб)

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

Заметим, что описание теории структур данных и их реализации выходит за рамки данной книги. Однако общие возможности описываемых структур данных должны быть понятны даже без понимания их реализации.

Почему не STL?

Для начала ответим на наиболее часто задаваемый вопрос о классах для данных в wxWidgets: Почему wxWidgets не использует стандартную библиотеку классов (STL)?. Главной причиной является историческая — wxWidgets появилась в 1992 году, задолго до того как реализация стандартной библиотеки классов была перенесена на различные платформы и компиляторы. По мере развития wxWidgets многие внутренние структуры стали поддерживать методы похожие на STL API. Ожидается, что в один прекрасный момент эти структуры будут просто заменены на их STL-эквиваленты.

Несмотря на это обстоятельство, вы можете использовать функциональность STL в ваших wxWidgets-приложениях уже сейчас. Для этого установите в файле setup.h значение переменной wxUSE_STL равным 1 (или используете параметр enable-stl на стадии конфигурирования перед сборкой библиотеки). Если вы это сделаете, то классы wxString и многие контейнеры будут построены на базе классов из стандартной библиотеки. Обратите внимание, что использование wxWidgets совместно с STL может увеличить размер и время компиляции приложения, особенно при использовании компилятора GCC.

Строки

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

Несмотря на то, что wxString является еще одним строковым классом он поддерживает некоторые дополнительные полезные возможности. wxString полностью поддерживает юникод, а также включает методы по преобразованию строки в различные кодировки.

Использование wxString дает возможность передавать строки в библиотеку или получать обратно без дополнительного процесса преобразования. Кроме того wxString реализует 90% методов стандартного класса std::string и значит каждый знакомый с std::string может сразу без дополнительного обучения использовать wxString.

Использование wxString

Использовать класс wxString очень легко. Везде, где вы бы обычно использовали бы std::string или вашу любимую реализацию строк, вы должны использовать wxString. Все функции, получающие строковые аргументы, должны использовать const wxString & (которая делает передачу строк внутрь функции быстрее, так как wxString использует механизм подсчета ссылок), а все функции, возвращающие строки, должны возвращать wxString, что позволяет безопасно получать из функции даже локальные переменные.

Так как программисты на C и C++ обычно хорошо знакомы с большинством строковых методов, то мы не будем помещать здесь большого и детального описания строкового API. За данной информацией обратитесь к документации wxWidgets, которая содержит впечатляющий список доступных методов.

Обратите внимание, что иногда wxString содержит два или более метода с одинаковой функциональностью. Например, Length, Len и length возвращают длину строки. Во всех подобных случаях рекомендуется использовать std::string-совместимые методы. Это сделает ваш код более понятным для других C++ программистов и позволит использовать его в других программах простой заменой wxString на std::string. Возможно в будущем wxWidgets начнет использовать std::string, поэтому применение таких методов позволит сделать ваши программы более совместимыми со следующими версиями (хотя старые методы wxString будут поддерживаться некоторое время в целях обратной совместимости).

wxString, символы и символьные литералы

wxWidgets использует тип wxChar, который является синонимом типов char или wchar_t, в зависимости от типа сборки (ANSI или юникод). Как уже упоминалось ранее, нет нужды разделять тип для строк char или wchar_t, так как wxString сохраняет строку, используя подходящий тип. Вот почему работая напрямую со строками wxString, желательно использовать тип wxChar вместо char или wchar_t. Следование данной рекомендации дает гарантии, что ваш код будет работать в ANSI и юникодных сборках без использования запутанных директив препроцессора.

Если вы используете wxWidgets в юникодном режиме, то стандартные строковые литералы имеют неправильный тип (char*). Чтобы иметь возможность использовать литералы в юникодном режиме их необходимо преобразовать в константы с широкими символами, что обычно делается с помощью специальной директивы L, которая указывается перед литералом. wxWidgets вводит макрос wxT (являющийся синонимом _T), чтобы получать правильный литерал вне зависимости от текущего режима сборки. Если юникодный режим не используется, то _T преобразуется в пустой макрос, но при сборке в юникодном режиме добавляется необходимый символ L для преобразования литерала в литерал с широкими символами. Например:

wxChar ch = wxT('*');
wxString s = wxT("Hello, world!");
wxChar* pChar = wxT("My string");
wxString s2 = pChar;

За более детальной информацией об использовании юникода в ваших приложениях, обратитесь к главе 16 Написание локализованных приложений.

Преобразование wxString в указатель языка C

Иногда необходимо получить доступ к данным wxString для низкоуровневой обработки на языке C. Для этого в wxWidgets есть несколько методов:

  • mb_str возвращает строку языка C c типом const char*. В юникодном режиме для этого происходит соответствующее преобразование, поэтому могут быть потеряны некоторое данные.
  • wc_str возвращает широкосимвольное представление строки с типом wchar_t*. В ANSI-режиме строка для этого преобразуется в юникод.
  • c_str возвращает указатель на реальные данные строки (типа const char* в режиме ANSI и const wchar_t* в юникодном режиме). Никакого преобразования при этом не происходит.

Вы можете производить преобразование между std::string и wxString, используя метод c_str как показано ниже:

std::string str1 = wxT("hello");
wxString str2 = str1.c_str();
std::string str3 = str2.c_str();

Одной из типичных ошибок при использовании wxString является надежда на неявное преобразование wxString в const char *. Советуем вам всегда использовать метод c_str, чтобы явно указать библиотеке, что необходимо выполнить преобразование. Опасность неявного преобразования демонстрируется в следующем примере:

// преобразовать входную строку к верхнему регистру, вывести результат
// на экран и возвратить результат (код неверный!)
const char *SayHELLO(const wxString& input)
{
    wxString output = input.Upper();
    printf("Hello, %s!\n", output);
    return output;
}

В этих четырех строках содержится две опасных ошибки. Первая происходит во время вызова оператора printf. Неявное преобразование wxString в строки языка C производится компилятором в случае функции типа puts, так как известно, что аргументом этой функции является значение типа const char *. Однако это не верно в случае функции с переменным числом аргументов, когда тип аргументов не известен. Так и происходит в нашем примере, а в результате во время вызова printf может произойти все что угодно (включая правильное отображение строки на экране), хотя в большинстве случаев программа аварийно завершит свою работу. Правильным решением является использование c_str:

printf(wxT("Hello, %s!\n"), output.c_str());

Вторая ошибка связана с тем, что из функции возвращается значение переменной output. Здесь будет использовано неявное преобразование, поэтому данный код скомпилируется, однако он возвращает указатель на буфер, принадлежащий локальной переменной, а она будет удалена при выходе из функции. Эта проблема решается просто: сделайте так, чтобы функция возвращала wxString вместо строк языка C. Конечная версия работающего кода выглядит следующим образом:

// преобразовать входную строку к верхнему регистру, вывести результат
// на экран и возвратить результат (исправленный код)
wxString SayHELLO(const wxString& input)
{
    wxString output = input.Upper();
    printf(wxT("Hello, %s!\n"), output.c_str());
    return output;
}

Стандартные строковые функции языка C

Т.к. большинство программ активно использует символьные строки, то стандартная библиотека языка C содержит множество функций для работы с ними. Однако не все из них обладают интуитивным поведением (например функция strncpy не всегда ставит завершающий ноль в результирующую строку) или являются безопасными с точки зрения возможности переполнения буфера. Более того, некоторые полезные функции не являются частью стандарта. Вот почему в дополнение к обычным функциям класса wxString существует несколько глобальных функций: wxIsEmpty проверяет является ли строка пустой (возвращает true для указателя NULL), wxStrlen корректно обрабатывает NULL и возвращает для него 0 и wxStricmp, которая является платформонезависимой чувствительной к регистру функцией сравнения, аналогичная функциям stricmp или strcasecmp.

Заголовочный файл “wx/string.h” также определяет функции wxSnprintf и wxVsnprintf, которые могут быть использованы вместо потенциально опасной стандартной функции sprintf. Данные функции используют snprintf, которая в большинстве случаев проверяет размеры буфера. Вы также можете использовать wxString::Printf, не беспокоясь об уязвимостях стандартной функции printf.

Операции преобразования числел

Программисту часто требуется преобразовывать число в строку и обратно, особенно при обработке пользовательского ввода или отображении результатов.

ToLong(long* val, int base=10) пытается преобразовать строку в число со знаком в указанной системе счисления. Метод возвращает true в случае успеха (результат операции будет записан в переменную на которую указывает val), или false, если строка не представляется в виде корректного числа в выбранной системе счисления base. Основание системы счисления (base) может принимать значения от 2 до 36 включительно или 0, которое означает использование стандартных правил языка C: если число начинается с 0x, предполагается, что оно шестнадцатиричное; если начинается с 0, то считается восьмеричным, и десятичным во всех остальных случаях.

ToULong(unsigned long* val, int base=10) работает аналогично ToLong, но преобразовывает строку в беззнаковое число.

ToDouble(double* val) пытается преобразовать строку в число с плавающей точкой. Возвращается true в случае успеха (результат будет записан в переменную на которую указывает val) или false, если строка не является таким числом.

Printf(const wxChar* pszFormat, ...) похож на стандартную функцию языка C sprintf и позволяет поместить информацию в wxString, используя стандартное форматирование для строк языка C. Метод возвращает число записаных байт.

static Format(const wxChar* pszFormat, ...) возвращает строку wxString, содержащую результат вызова Printf с параметрами. Преимуществом Format над Printf является возможность добавления результата Format к существующей строке:

int n = 10;
wxString s = "Some Stuff";
s += wxString::Format(wxT("%d"),n );

operator< < может использоваться для добавления значений типа int, float или double к строке wxString.

wxStringTokenizer

wxStringTokenizer поможет вам разбить строку на несколько лексем, заменяя и расширяя возможности функции strtok языка C. Для этого необходимо создать объект класса wxStringTokenizer, передать ему требующую разбиения строку и разделитель лексем (по умолчанию, в качестве символа-разделителя лексем используется пробел). Далее необходимо вызывать функцию GetNextToken (получить следующую лексему) до тех пор, пока HasMoreTokens (есть ли лексемы) не возвратит false.

wxStringTokenizer tkz(wxT("first:second:third:fourth"), wxT(":"));
while (tkz.HasMoreTokens() ) {
    wxString token = tkz.GetNextToken();
    // здесь идет обработка лексемы
}

По умолчанию, когда символом-разделителем является пробел, wxStringTokenizer ведет себя аналогично функции strtok. Однако класс также возвратит пустые лексемы (если такие будут). Эта возможность полезна при разборе строго форматированных данных, когда есть фиксировано число полей, но некоторые из них могут быть пустыми, как например в случае файла с запятыми или символами табуляции в качестве разделителей.

Поведение wxStringTokenizer зависит от последнего параметра конструктора, который может принимать одно из следующих значений:

  • wxTOKEN_DEFAULT: Используется поведение, описанное ранее: аналогично wxTOKEN_STRTOK в случае, когда строка с разделителями состоит только из пробелов, и как с wxTOKEN_RET_EMPTY иначе.
  • wxTOKEN_RET_EMPTY: В этом режиме возвращаются пустые лексемы в середине строки. Поэтому строка a::b: разобьется на три лексемы: a, < <>> (пустая строка) и b.
  • wxTOKEN_RET_EMPTY_ALL: В этом режиме также возвращаются пустые завершающие лексемы (после последнего символа-разделителя). Следовательно, a::b: будет разбит на четыре лексемы — три такие как в случае wxTOKEN_RET_EMPTY и пустая лексема в конце.
  • wxTOKEN_RET_DELIMS: В этом режиме разделитель в конце лексемы присоединяется к самой лексеме (кроме последней лексемы, у которой такой символ отсутствует). В противном случае поведение похоже на wxTOKEN_RET_EMPTY.
  • wxTOKEN_STRTOK: В этом случае класс ведет себя также как и стандартная функция strtok. Пустые лексемы никогда не возвращаются.

Класс wxStringTokenizer имеет две полезные функции:

  • CountTokens возвращает число оставшихся лексем в строке, и 0, когда лексем уже не осталось.
  • GetPosition возвращает текущую позицию разборщика в оригинальной строке.

wxRegEx

Класс wxRegEx можно использовать для работы с регулярными выражениями. Он поддерживает регулярные выражения для поиска и замены в строках. Класс wxRegEx может использовать системную библиотеку (если она доступна и имеет поддержку регулярных выражений POSIX, как в случае современных вариантов Unix, включая Linux и Mac~OS~X) или встроенную библиотеку Генри Спенсера (Henry Spencer). Регулярные выражения, удовлетворяющие стандарту POSIX, делятся на два множества: расширенные (extended) и простые (basic). Встроенная библиотека также вводит третий режим (продвинутый), который не доступен при использовании системной библиотеки.

На платформах, где доступна системная библиотека, она как правило используется в обычной сборке. В юникодной сборке обычно используется встроенная библиотека. Однако используемую библиотеку возможно изменить при сборке wxWidgets. При использовании системной библиотеки, в юникодной сборке выражения и данные переводятся в 8-битовую кодировку перед тем как передаются библиотеке.

Используйте wxRegEx так, как если бы вы использовали любой другой POSIX-совместимый процессор регулярных выражений. За описанием продвинутых возможностей класса и специфики его использования, обратитесь к документации библиотеки и описанию API.

wxArray

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

Типы массивов

В wxWidgets существует три типа массивов. Все эти типы являются наследниками от wxBaseArray, который работает с нетипизированными данными, а поэтому не может быть использован непосредственно. Макросы WX_DEFINE_ARRAY, WX_DEFINE_SORTED_ARRAY и WX_DEFINE_OBJARRAY используются для создания новых классов-наследников от него. На такие классы обычно ссылаются по именам wxArray, wxSortedArray и wxObjArray, но важно понимать, что классов с такими именами не существует.

wxArray подходит для хранения простых типов и указателей, которые не считаются полноценными объектами. Если в массиве хранятся указатели на объекты, то они автоматически не уничтожаются при удалении указателя из массива. Кроме того заметим, что все функции массива объявлены как подставляемые (inline), поэтому без последствий (как в скорости выполнения, так и в размере выполняемого файла) можно объявлять очень много различных типов для массивов. У класса есть одно серьезное ограничение: он может использоваться только для хранения простых типов (bool, char, short, int, long и их беззнаковых вариантов) или указателей (на любой тип). Данные типа float или double не могут хранится в wxArray.

wxSortedArray – это вариант класса wxArray, который необходимо использовать, когда операция поиска по массиву выполняется очень часто. При использовании wxSortedArray необходимо дополнительно объявить функцию для сравнения двух элементов массива. Элементы в массиве сортируются в соответствии с этой функцией. Если вы ищите в массиве во много раз чаще, чем добавляете в него новую информацию, то wxSortedArray может дать огромный прирост в скорости по сравнению с wxArray. Заметим, что на типы, хранимые в wxSortedArray действуют те же ограничения, что и на типы в классе wxArray. Таким образом, в данных массивах можно хранить только простые типы данных или указатели.

Класс wxObjArray трактует элементы массива как объекты. Он может удалять эти элементы, когда они удаляются из массива, корректно вызывая при этом деструктор. Он также копирует объекты, используя конструктор копирования самого объекта. Определение wxObjArray состоит из двух частей. Во-первых, вы должны объявить новый класс wxObjArray, используя макрос WX_DECLARE_OBJARRAY. Во-вторых, вы должны подключить файл , который определяет реализацию шаблона, и определить реализацию вашего класса с помощью макроса WX_DEFINE_OBJARRAY в точке, где уже полностью определен класс элементов, содержащихся в массиве. Эта технология будет продемонстрирована на примере чуть позднее.

wxArrayString

wxArrayString – это эффективный контейнер, предназначенный для хранения объектов типа wxString и имеет те же возможности, что и wxArray. Он также очень маленький и занимает в памяти не намного больше места, чем стандартный массив языка C типа wxString[] (wxArrayString использует знание о внутренней структуре класса wxString, чтобы достичь этого). Все методы, доступные в классе wxArray также доступны и в wxArrayString.

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

Ссылка, возвращаемая методами Item, Last или operator[], не является константной, а поэтому вы можете сразу модифицировать объект:

array.Last().MakeUpper();

Существует также сортированный вариант wxArrayString, который называется wxSortedArrayString. Он поддерживает те же самые методы, но содержит все текстовые строки, отсортированные в алфавитном порядке. wxSortedArrayString использует бинарный поиск при выполнеии метода Index, что очень эффективно, если вы редко добавляете строки в массив и часто осуществляете по ним поиск. Методы Insert и Sort не должны вызываться у wxSortedArrayString, так как это может нарушить порядок элементов в массиве.

Создание и уничтожение массивов и управление памятью

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

Автоматическое управление памятью в массиве элементарно: массив начинает работу с предварительного выделения некоторого количества памяти (определяемого WX_ARRAY_DEFAULT_INITIAL_SIZE); когда при добавлении элементов требуемая память превысит выделенное значение, массив делает перераспределение, увеличивая вместимость массива на 50\% от его текущего объема, но не более ARRAY_MAXSIZE_INCREMENT. Метод Shrink освобождает любую незанятую память. Метод Alloc может быть очень полезен, если вы точно знаете, сколько элементов вы разместите в массиве. Используя этот метод вы зарезервировать память для заданного числа элементов, что позволит избежать слишком частого перераспределения памяти.

Пример использования массивов

Следующий пример показывает все важные моменты использования wxObjArray для хранения данных пользовательского типа. Использование wxArray при хранении указателей работает точно также в терминах синтаксиса и семантики, за исключением того, что wxArray никогда не берет во владение хранимые объекты, а потому они должны уничтожаться пользователем.

// Наши данные, которые мы сохраняем в списке (класс покупателей)
class Customer
{
public:
    int CustID;
    wxString CustName;
};

// эта часть может быть в файле объявления или реализации (.cpp)
// объявляем наш класс для массива:
// этот макрос объявляет и частично реализует класс CustomerArray
// (который является наследником от wxArrayBase)
WX_DECLARE_OBJARRAY(Customer, CustomerArray);

// главным требованием является помещение данной директивы ПОСЛЕ
// полного объявления класса Покупатель (для WX_DECLARE_OBJARRAY
// неполной (forward) декларации вполне достаточно), но обычно
// данный макрос помещают в файле с реализацией, а не в заголовочный файл
#include 
WX_DEFINE_OBJARRAY(CustomerArray);

// Используется для сортировки при сравнении объектов
int arraycompare(Customer** arg1, Customer** arg2)
{
    return ((*arg1)->CustID & (*arg2)->CustID);
}

// Демонстрация возможностей массива
void ArrayTest()
{
    // Создаем экземпляр нашего массива
    CustomerArray MyArray;

    bool IsEmpty = MyArray.IsEmpty(); // должно быть true

    // Создаем несколько покупателей
    Customer CustA;
    CustA.CustID = 10;
    CustA.CustName = wxT("Bob");

    Customer CustB;
    CustB.CustID = 20;
    CustB.CustName = wxT("Sally");

    Customer* CustC = new Customer();
    CustC->CustID = 5;
    CustC->CustName = wxT("Dmitri");

    // Добавляем двух покупателей в массив
    MyArray.Add(CustA);
    MyArray.Add(CustB);

    // Добавляем последнего покупателя в заданное место массива
    // Массив не владеет объектом CustC, он владеет только его копией
    MyArray.Insert(*CustC, (size_t)0);

    int Count = MyArray.GetCount(); // должно возвратить 3

    // Если объект не найден, то метод возвратит wxNOT_FOUND
    int Index = MyArray.Index(CustB); // должно возвратить 2

    // Process each customer in the array
    // Обрабатываем каждого покупателя в архиве
    for (unsigned int i = 0; i & MyArray.GetCount(); i++)
    {
        Customer Cust = MyArray[i]; // or MyArray.Item(i);

        // Обрабатываем покупателя
    }

    // Сортируем покупателей с помощью функции сортировки
    MyArray.Sort(arraycompare);

    // Удаляем Покупателя A из массива, но не удаляем его
    // Remove Customer A from the array, but do not delete
    Customer* pCustA = MyArray.Detach(1);
    // Мы должны удалять объект сами, если используем Detach
    delete pCustA;

    // метод Remove также удаляет и хранимый объект
    MyArray.RemoveAt(1);

    // Очищаем массив, удаляя все объекты
    MyArray.Clear();

    // Массив никогда не владел этим объектом
    delete CustC;
}

wxList и wxNode

Класс wxList представляет двусвязный список, который может хранить данные произвольного типа. wxWidgets требует, чтобы вы явно определили новый тип списка для каждого отдельного типа данных, что позволяет библиотеке проводить строгую проверку типов для хранимых в списке значений. Класс wxList также позволяет дополнительно определить тип значений для ключа, с помощью которого можно осуществить примитивный поиск (обратитесь к разделу о типе wxHashMap, если вам необходима структура с быстрым доступом к произвольному месту).

wxList использует абстрактный класс wxNode (узел списка). Если вы объявляете новый тип списка, то также создается тип для узлов, являющихся наследником от wxNodeBase — он позволяет осуществить строгую проверку типа. Самые важные методы класса: GetNext, GetPrevious и GetData возвращают следующий и предыдущий узел, а также данные текущего узла соответственно.

Заметим, что удаление из списка работает не совсем так, как от нее ожидается. По умолчанию, при удалении узла не удаляются данные, которые в нем содержатся. Используя метод DeleteContents, можно изменить это поведение – список удалит данные вместе с узлом. Если вам требуется полностью очистить список и все данные в нем, то не забудьте вызывать DeleteContents с параметром true перед вызовом Clear.

Для иллюстрации возможностей класса, мы приведем маленький, но всесторонний пример кода, который дополнительно продемонстрирует процедуру создания нового типа списка. Заметим, что макрос WX_DECLARE_LIST обычно располагается в заголовочном файле, тогда как макрос WX_DEFINE_LIST должен почти всегда располагаться в файле с реализацией.

// Наши данные, которые мы сохраняем в списке (класс покупателей)
class Customer
{
public:
    int CustID;
    wxString CustName;
};

// Эта часть должна быть в заголовочном файле или в файле с реализацией
// объявляем тип для списка:
// этот макрос объявляет и частично реализует класс CustomerList
// (который является наследником от wxListBase)
WX_DECLARE_LIST(Customer, CustomerList);

// главным требованием является помещение данной дерективы ПОСЛЕ
// полного объявления класса Покупатель (для WX_DECLARE_LIST
// неполной (forward) декларации вполне достаточно), но обычно
// данный макрос помещают в файле с реализацией, а не в заголовочный файл
#include 
WX_DEFINE_LIST(CustomerList);

// Используется для сортировки при сравнении объектов
int listcompare(const Customer** arg1, const Customer** arg2)
{
    return ((*arg1)->CustID & (*arg2)->CustID);
}

// Демонстрация возможностей списка
void ListTest()
{
    // Создаем экзмпляр нашего списка
    CustomerList* MyList = new CustomerList();

    bool IsEmpty = MyList->IsEmpty(); // должно быть true

    // Создаем несколько покупателей
    Customer* CustA = new Customer;
    CustA->CustID = 10;
    CustA->CustName = wxT("Bob");

    Customer* CustB = new Customer;
    CustB->CustID = 20;
    CustB->CustName = wxT("Sally");

    Customer* CustC = new Customer;
    CustC->CustID = 5;
    CustC->CustName = wxT("Dmitri");

    // Добавляем двух покупателей в список
    MyList->Append(CustA);
    MyList->Append(CustB);

    // Добавляем последнего покупателя в заданное место списка
    MyList->Insert((size_t)0, CustC);

    int Count = MyList->GetCount(); // должно возвратить 3

    // Если объект не найден, то метод возвратит wxNOT_FOUND
    int index = MyList->IndexOf(CustB); // должно возвратить 2

    // Вместе с классом создается тип для узла, который
    // содержит объект, определенного при создании типа
    CustomerList::Node* node = MyList->GetFirst();

    // Обходим узлы и обрабатываем покупателей
    while (node)
    {
        Customer* Cust = node->GetData();

        // Обрабатываем покупателя

        node = node->GetNext();
    }

    // Возвращает узел на определенном месте
    node = MyList->Item(0);

    // Сортируем покупателей с помощью функции сортировки
    MyList->Sort(listcompare);

    // Удаляем узел Покупателя A из списка
    MyList->DeleteObject(CustA);
    // Объект CustA НЕ удален при удалении узла
    delete CustA;

    // Возвращаем узел, который содержит данные клиента
    node = MyList->Find(CustB);

    // Устанавливаем, что надо удалять данные при удалении узла
    MyList->DeleteContents(true);

    // Удаляем узел и данные которые он содержит (CustB)
    MyList->DeleteNode(node);

    // Удаляем список и все связанные с ним данные
    // (DeleteContents установлен в true)
    MyList->Clear();

    delete MyList;
}

wxHashMap

wxHashMap — это простой, типизированный и достаточно эффективный класс для создания отображений (hash maps), интерфейс которого отчасти повторяет интерфейс соответствующего STL-контейнера. В частности, он моделирует часть поведения стандартного класса std::map и нестандартного std::hash_map. Используя специальные макросы для создания хэш-карт, вы можете выбирать тип для ключей и значений, включая int, wxString или void* (для хранения произвольных классов).

Существует три макроса для объявления отображений. Объявление отображения CLASSNAME, типом wxString, используемым в качестве ключа, и типом VALUE_T для значений, выглядит следующим образом:

WX_DECLARE_STRING_HASH_MAP(VALUE_T, CLASSNAME);

Объявление отображения CLASSNAME, с ключами void* и значениями
типа VALUE_T:

Объявление отображения CLASSNAME, с ключами void* и значениями
типа VALUE_T:

Объявление отображения CLASSNAME с заданным ключем и значением в общем случае имеет вид

WX_DECLARE_HASH_MAP(KEY_T, VALUE_T, HASH_T, KEY_EQ_T, CLASSNAME);

где HASH_T и KEY_EQ_T — типы, необходимые для хэширования и сравнения ключей. В wxWidgets реализовано три предопределенных хэширующих функции: wxInteger — для целочисленных типов (int, long, short и их беззнаковых версий), wxStringHash — для строк (wxString, wxChar*, char*) и wxPointerHash для указателей на любые типы. Аналогично определены три предиката равенства: wxIntegerEqual, wxStringEqual и wxPointerEqual.

Следующий пример показывает использование методов класса wxHashMap, а также создание и использование различных отображений:

// Наши данные, которые мы храним в отображении (класс покупателей)
class Customer
{
    public:
        int CustID;
        wxString CustName;
};

// Объявляем класс для отображения
// Этот макрос декларирует и реализует отображение CustomerList
WX_DECLARE_HASH_MAP(int, Customer*, wxIntegerHash,
                    wxIntegerEqual, CustomerHash);

void HashTest()
{
    // Объявляем экземпляр нашего класса
    CustomerHash MyHash;

    bool IsEmpty = MyHash.empty(); // должно быть true

    // Создаем несколько покупателей
    Customer* CustA = new Customer;
    CustA->CustID = 10;
    CustA->CustName = wxT("Bob");

    Customer* CustB = new Customer;
    CustB->CustID = 20;
    CustB->CustName = wxT("Sally");

    Customer* CustC = new Customer;
    CustC->CustID = 5;
    CustC->CustName = wxT("Dmitri");

    // Добавляем покупателей в отображение
    MyHash[CustA->CustID] = CustA;
    MyHash[CustB->CustID] = CustB;
    MyHash[CustC->CustID] = CustC;

    int Size = MyHash.size(); // должно возвратить 3

    // метод count возвращает 0 или 1, т.е. существует ли
    // число 20 в отображении
    int Present = MyHash.count(20); // должно быть 1

    // Итератор для нашего отображения
    CustomerHash::iterator i = MyHash.begin();

    // метод End возвращает псевдоэлемент, следующий за последним
    while (i != MyHash.end())
    {
        // first - это ключ, а second - его значение
        int CustID = i->first;
        Customer* Cust = i->second;

        // обрабатываем покупателя

        // переходим к следующему элементу
        i++;
    }

    // Удаляем покупателя
    MyHash.erase(10);

    // Объект CustA НЕ УДАЛЯЕТСЯ при удалении из отображения
    delete CustA;

    // Возвращает итератор на узел с определенным ключом
    CustomerHash::iterator i2 = MyHash.find(21);

    // метод Find возвращает hash::end, если ключ не найден
    bool NotFound = (i2 == MyHash.end()); // должно быть true

    // На этот раз поиск должен быть успешным
    i2 = MyHash.find(20);

    // Удаляем элемент, используя итератор
    MyHash.erase(i2);
    delete CustB;

    // В качестве побочного эффекта данного действия будет
    // вставлено значение NULL для ключа 30
    Customer* Cust = MyHash[30]; // в Cust запишется NULL

    // Очищает структуру от всех элементов
    MyHash.clear();

    delete CustC;
}

Читать вторую часть этой главы.

Leave a Reply

Your email address will not be published. Required fields are marked *

Please leave these two fields as-is: