2.8. Стандартный массив - это вектор

2.8. Стандартный массив - это вектор

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

Разумеется, вектор реализован в виде шаблона класса. Так, мы можем написать

vectorint ivec(10);

vectorstring svec(10);

Есть два существенных отличия нашей реализации шаблона класса Array от реализации шаблона класса vector. Первое отличие состоит в том, что вектор поддерживает как присваивание значений существующим элементам, так и вставку дополнительных элементов, то есть динамически растет во время выполнения, если программист решил воспользоваться этой его возможностью. Второе отличие более радикально и отражает существенное изменение парадигмы проектирования. Вместо того чтобы поддержать большой набор операций-членов, применимых к вектору, таких, как sort(), min(), max(), find()и так далее, класс vector предоставляет минимальный набор: операции сравнения на равенство и на меньше, size() и empty(). Более общие операции, перечисленные выше, определены как независимые обобщенные алгоритмы.

Для использования класса vector мы должны включить соответствующий заголовочный файл.

#include vector

// разные способы создания объектов типа vector

vectorint vec0; // пустой вектор

const int size = 8;

const int value = 1024;

// вектор размером 8

// каждый элемент инициализируется 0

vectorint vec1(size);

// вектор размером 8

// каждый элемент инициализируется числом 1024

vectorint vec2(size,value);

// вектор размером 4

// инициализируется числами из массива ia

int ia[4] = { 0, 1, 1, 2 };

vectorint vec3(ia,ia+4);

// vec4 - копия vec2

vectorint vec4(vec2);

Так же, как наш класс Array, класс vector поддерживает операцию доступа по индексу. Вот пример перебора всех элементов вектора:

#include vector

extern int getSize();

void mumble()

{

int size = getSize();

vectorint vec(size);

for (int ix=0; ixsize; ++ix)

vec[ix] = ix;

// ...

}

Для такого перебора можно также использовать итераторную пару. Итератор – это объект класса, поддерживающего абстракцию указательного типа. В шаблоне класса vector определены две функции-члена – begin() и end(), устанавливающие итератор соответственно на первый элемент вектора и на элемент, который следует за последним. Вместе эти две функции задают диапазон элементов вектора. Используя итератор, предыдущий пример можно переписать таким образом:

#include vector

extern int getSize();

void mumble()

{

int size = getSize();

vectorint vec(size);

vectorint::iterator iter = vec.begin();

for (int ix=0; iter!=vec.end(); ++iter, ++ix)

*iter = ix;

// ...

}

Определение переменной iter

vectorint::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 );

vectorint::iterator it = vec.begin(), end_it = vec.end();

cout "Начальный массив: ";

for ( ; it != end_it; ++ it ) cout *it ;

cout " ";

// сортировка массива

sort( vec.begin(), vec.end() );

cout "упорядоченный массив: ";

it = vec.begin(); end_it = vec.end();

for ( ; it != end_it; ++ it ) cout *it ;

cout " ";

int search_value;

cout "Введите значение для поиска: ";

cin search_value;

// поиск элемента

vectorint::iterator found;

found = find( vec.begin(), vec.end(), search_value );

if ( found != vec.end() )

cout "значение найдено! ";

else cout "значение найдено! ";

// инвертирование массива

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 string

#include "TelephoneNumber.h"

mapstring, telephoneNum telephone_directory;

(Классы векторов, отображений и других контейнеров в подробностях описываются в главе 6. Мы попробуем реализовать систему текстового поиска, используя эти классы. В главе 12 рассмотрены обобщенные алгоритмы, а в Приложении приводятся примеры их использования.)

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

Упражнение 2.22

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

string pals[] = {

"pooh", "tiger", "piglet", "eeyore", "kanga" };

(a) vectorstring svec1(pals,pals+5);

(b) vectorint ivec1(10);

(c) vectorint ivec2(10,10);

(d) vectorstring svec2(svec1);

(e) vectordouble dvec;

Упражнение 2.23

Напишите две реализации функции min(), объявление которой приведено ниже. Функция должна возвращать минимальный элемент массива. Используйте цикл for и перебор элементов с помощью

индекса

template class elemType

итератора

elemType min (const vectorelemType vec);

2013-11-14 09:35:20 Safronik

Есть места где вы не объясняете код. Просто вставляете непонятную инструкцию или строчку. Сложно.

2012-06-27 18:30:04 FeelUs

"Упражнение 2.8 Отношение наследования между типом и подтипом служит примером отношения является." - как-то не по русски

2012-05-30 18:46:11

"... private: static const int DefaultArraySize = 12; " - на это билдер ругался до тех пор, пока я не поместил обьявление класса в .h ----------------------------- Не " else ix[ix] = array[ix]; " , а "...iа[ix]". ----------------------------- " int IntArray::operator[] (int index) " ругается на непричасность к классу IntArray ----------------------------- Словил ошибку линкёра после переноса реализации класса в IntArray.cpp (в IntArray.h есть его обьявление, директивы include тоже, эта пара - один unit.

2011-10-14 19:42:59 Crazy_penguin

Глава 2 - Рассматривается ООП, конструкторы и деструкторы. Глава 3 - Изучаем, что такое переменные и цикл for. Кто-то кого-то где-то ...