Стандартный массив – это вектор
Хотя встроенный массив формально и обеспечивает механизм контейнера, он, как мы видели выше, не поддерживает семантику абстракции контейнера. До принятия стандарта C++ для программирования на таком уровне мы должны были либо приобрести нужный класс, либо реализовать его самостоятельно. Теперь же класс массива является частью стандартной библиотеки C++. Только называется он не массив, а вектор.
Разумеется, вектор реализован в виде шаблона класса. Так, мы можем написать
vector<int> ivec(10);
vector<string> svec(10);
Есть два существенных отличия нашей реализации шаблона класса Array от реализации шаблона класса vector. Первое отличие состоит в том, что вектор поддерживает как присваивание значений существующим элементам, так и вставку дополнительных элементов, то есть динамически растет во время выполнения, если программист решил воспользоваться этой его возможностью. Второе отличие более радикально и отражает существенное изменение парадигмы проектирования. Вместо того чтобы поддержать большой набор операций-членов, применимых к вектору, таких, как sort(), min(), max(), find()и так далее, класс vector
предоставляет минимальный набор: операции сравнения на равенство и на меньше, size() и empty(). Более общие операции, перечисленные выше, определены как независимые обобщенные алгоритмы.
Для использования класса vector мы должны включить соответствующий заголовочный файл.
#include <vector>
|
// разные способы создания объектов типа vector vector<int> vec0; // пустой вектор const int size = 8; const int value = 1024; // вектор размером 8 // каждый элемент инициализируется 0 vector<int> vec1(size); // вектор размером 8 // каждый элемент инициализируется числом 1024 vector<int> vec2(size,value); // вектор размером 4 // инициализируется числами из массива ia int ia[4] = { 0, 1, 1, 2 }; vector<int> vec3(ia,ia+4); // vec4 - копия vec2 |
vector<int> vec4(vec2);
Так же, как наш класс Array, класс vector
поддерживает операцию доступа по индексу. Вот пример перебора всех элементов вектора:
#include <vector> |
void mumble()
{
int size = getSize();
vector<int> vec(size);
for (int ix=0; ix<size; ++ix)
vec[ix] = ix;
// ...
}
Для такого перебора можно также использовать итераторную пару. Итератор – это объект класса, поддерживающего абстракцию указательного типа. В шаблоне класса vector определены две функции-члена – begin() и end(), устанавливающие итератор соответственно на первый элемент вектора и на элемент, который следует за последним. Вместе эти две функции задают диапазон элементов вектора. Используя итератор, предыдущий пример можно переписать таким образом:
#include <vector> |
void mumble()
{
int size = getSize();
vector<int> vec(size);
vector<int>::iterator iter = vec.begin();
for (int ix=0; iter!=vec.end(); ++iter, ++ix)
*iter = ix;
// ...
}
Определение переменной iter
vector<int>::iterator iter = vec.begin();
инициализирует ее адресом первого элемента вектора vec. iterator определен с помощью typedef в шаблоне класса vector, содержащего элементы типа int. Операция инкремента
++iter
перемещает итератор на следующий элемент вектора. Чтобы получить сам элемент, нужно применить операцию разыменования:
*iter
В стандартной библиотеке С++ имеется поразительно много функций, работающих с классом vector, но определенных не как функции-члены класса, а как набор обобщенных алгоритмов. Вот их неполный перечень:
алгоритмы поиска: find(), find_if(), search(), binary_search(), count(), count_if();
алгоритмы сортировки и упорядочения: sort(), partial_sort(), merge(), partition(), rotate(), reverse(), random_shuffle();
алгоритмы удаления: unique(), remove();
численные алгоритмы: accumulate(), partial_sum(), inner_product(), adjacent_difference();
алгоритмы генерации и изменения последовательности: generate(), fill(), transform(), copy(), for_each();
алгоритмы сравнения: equal(), min(), max().
В число параметров этих обобщенных алгоритмов входит итераторная пара, задающая диапазон элементов вектора, к которым применяется алгоритм. Скажем, чтобы упорядочить все элементы некоторого вектора ivec, достаточно написать следующее:
sort ( ivec.begin(), ivec.end() );
Чтобы применить алгоритм sort()
только к первой половине вектора, мы напишем:
sort ( ivec.begin(), ivec.begin() + ivec.size()/2 );
Роль итераторной пары может играть и пара указателей на элементы встроенного массива. Пусть, например, нам дан массив:
int ia[7] = { 10, 7, 9, 5, 3, 7, 1 };
Упорядочить весь массив можно вызовом алгоритма sort():
sort ( ia, ia+7 );
Так можно упорядочить первые четыре элемента:
sort ( ia, ia+4 );
Для использования алгоритмов в программу необходимо включить заголовочный файл
#include <algorithm>
Ниже приведен пример программы, использующей разнообразные алгоритмы в применении к объекту типа vector:
#include <vector> #include <algorithm> #include <iostream> int ia[ 10 ] = { 51, 23, 7, 88, 41, 98, 12, 103, 37, 6 }; int main() { vector< int > vec( ia, ia+10 ); vector<int>::iterator it = vec.begin(), end_it = vec.end(); cout << "Начальный массив: "; for ( ; it != end_it; ++ it ) cout << *it << ' '; cout << "\n"; // сортировка массива sort( vec.begin(), vec.end() ); cout << "упорядоченный массив: "; it = vec.begin(); end_it = vec.end(); for ( ; it != end_it; ++ it ) cout << *it << ' '; cout << "\n\n"; int search_value; cout << "Введите значение для поиска: "; cin >> search_value; // поиск элемента vector<int>::iterator found; found = find( vec.begin(), vec.end(), search_value ); if ( found != vec.end() ) cout << "значение найдено!\n\n"; else cout << "значение найдено!\n\n"; // инвертирование массива reverse( vec.begin(), vec.end() ); cout << "инвертированный массив: "; it = vec.begin(); end_it = vec.end(); for ( ; it != end_it; ++ it ) cout << *it << ' '; cout << endl; |
}
Стандартная библиотека С++ поддерживает и ассоциативные массивы. Ассоциативный массив – это массив, элементы которого можно индексировать не только целыми числами, но и значениями любого типа. В терминологии стандартной библиотеки ассоциативный массив называется отображением (map). Например, телефонный справочник может быть представлен в виде ассоциативного массива, где индексами служат фамилии абонентов, а значениями элементов – телефонные номера:
#include <map> |
#include "TelephoneNumber.h"
map<string, telephoneNum> telephone_directory;
(Классы векторов, отображений и других контейнеров в подробностях описываются в главе 6. Мы попробуем реализовать систему текстового поиска, используя эти классы. В главе 12 рассмотрены обобщенные алгоритмы, а в Приложении приводятся примеры их использования.)
В данной главе были очень бегло рассмотрены основные аспекты программирования на С++, основы объектно-ориентированного подхода применительно к данному языку и использование стандартной библиотеки. В последующих главах мы разберем эти вопросы более подробно и систематично.
Упражнение 2.22
Поясните результаты каждого из следующих определений вектора:
string pals[] = { "pooh", "tiger", "piglet", "eeyore", "kanga" }; (a) vector<string> svec1(pals,pals+5); (b) vector<int> ivec1(10); (c) vector<int> ivec2(10,10); (d) vector<string> svec2(svec1); (e) vector<double> dvec; |
Напишите две реализации функции min(), объявление которой приведено ниже. Функция должна возвращать минимальный элемент массива. Используйте цикл for и перебор элементов с помощью
индекса
итератора
template <class elemType> |
Часть II
Основы языка
Код программы и данные, которыми программа манипулирует, записываются в память компьютера в виде последовательности битов. Бит – это мельчайший элемент компьютерной памяти, способная хранить либо 0, либо 1. На физическом уровне это соответствует электрическому напряжению, которое, как известно, либо есть , либо нет. Посмотрев на содержимое памяти компьютера, мы увидим что-нибудь вроде:
00011011011100010110010000111011 ...
Очень трудно придать такой последовательности смысл, но иногда нам приходится манипулировать и подобными неструктурированными данными (обычно нужда в этом возникает при программировании драйверов аппаратных устройств). С++ предоставляет набор операций для работы с битовыми данными. (Мы поговорим об этом в главе 4.)
Как правило, на последовательность битов накладывают какую-либо структуру, группируя биты в байты и слова. Байт содержит 8 бит, а слово – 4 байта, или 32 бита. Однако определение слова может быть разным в разных операционных системах. Сейчас начинается переход к 64-битным системам, а еще недавно были распространены системы с 16-битными словами. Хотя в подавляющем большинстве систем размер байта одинаков, мы все равно будем называть эти величины машинно-зависимыми.
Так выглядит наша последовательность битов, организованная в байты.
Рис 1.
Адресуемая машинная память
Теперь мы можем говорить, например, о байте с адресом 1040 или о слове с адресом 1024 и утверждать, что байт с адресом 1032 не равен байту с адресом 1040.
Однако мы не знаем, что же представляет собой какой-либо байт, какое-либо машинное слово. Как понять смысл тех или иных 8 бит? Для того чтобы однозначно интерпретировать значение этого байта (или слова, или другого набора битов), мы должны знать тип данных, представляемых данным байтом.
С++ предоставляет набор встроенных типов данных: символьный, целый, вещественный – и набор составных и расширенных типов: строки, массивы, комплексные числа. Кроме того, для действий с этими данными имеется базовый набор операций: сравнение, арифметические и другие операции. Есть также операторы переходов, циклов,
условные операторы. Эти элементы языка С++ составляют тот набор кирпичиков, из которых можно построить систему любой сложности. Первым шагом в освоении С++ станет изучение перечисленных базовых элементов, чему и посвящена часть II данной книги.
Глава 3 содержит обзор встроенных и расширенных типов, а также механизмов, с помощью которых можно создавать новые типы. В основном это, конечно, механизм классов, представленный в разделе 2.3. В главе 4 рассматриваются выражения, встроенные операции и их приоритеты, преобразования типов. В главе 5 рассказывается об инструкциях языка. И наконец глава 6 представляет стандартную библиотеку С++ и контейнерные типы – вектор и ассоциативный массив.
