Шилдт c++_базовый_курс издание 3. Герберт Шилдт С базовый курс

• Название: Герберт Шилдт С базовый курс
• Анкор: Шилдт c++_базовый_курс издание 3.pdf
• Дата: 13.02.2017
• Размер: 9.37 Mb.
• Имя файла: Шилдт c++_базовый_курс издание 3.pdf
• Тип: Книга; #2637
• страница: 26 из 33

Вставка и удаление элементов из вектора
Помимо занесения новых элементов в конец вектора, у нас есть возможность вставлять элементы в середину вектора, используя функцию insert(). Удалять элементы можно с помощью функции erase(). Использование функций insert() и erase() демонстрируется в следующей программе.

// Демонстрация вставки элементов в вектор и удаления их из него.
#include
#include
using namespace std;
int main()
{
vector v;
unsigned int i;
for(i=0; i<10; i++) v.push_back('A' + i);
// Отображаем исходное содержимое вектора.
cout << "Размер = " << v.size() << endl;
cout << "Исходное содержимое вектора:\n";
for(i=0; i cout << endl << endl;
vector:: iterator p = v.begin();
p += 2; // указатель на 3-й элемент вектора
// Вставляем 10 символов 'X' в вектор v.
v.insert(p, 10, 'X');

/* Отображаем содержимое вектора после вставки символов. */
cout << "Размер вектора после вставки = " << v.size()<< endl;
cout << "Содержимое вектора после вставки:\n";
for(i=0; i cout << endl << endl;
// Удаление вставленных элементов.
p = v.begin();
p += 2; // указатель на 3-й элемент вектора v.erase(р, р+10); // Удаляем 10 элементов подряд.
/* Отображаем содержимое вектора после удаления символов. */
cout << "Размер вектора после удаления символов = "<< v.size()
<< endl;
cout << "Содержимое вектора после удаления символов:\n";
for(i=0; i cout << endl;
return 0;
}
При выполнении эта программа генерирует следующие результаты.
Размер = 10
Исходное содержимое вектора:
A B C D E F G H I J
Размер вектора после вставки = 20

Содержимое вектора после вставки:
A B X X X X X X X X X X C D E F G H I J
Размер вектора после удаления символов = 10
Содержимое вектора после удаления символов:
A B C D E F G H I J
Сохранение в векторе объектов класса
В предыдущих примерах векторы служили для хранения значений только встроенных типов, но этим их возможности не ограничиваются. В вектор можно помещать объекты любого типа, включая объекты классов, создаваемых программистом. Рассмотрим пример, в котором вектор используется для хранения объектов класса three_d. Обратите внимание на то, что в этом классе определяются конструктор по умолчанию и перегруженные версии операторов "<" и "==". Имейте в виду, что, возможно, вам придется определить и другие операторы сравнения. Это зависит от того, как используемый вами компилятор реализует библиотеку STL.
// Хранение в векторе объектов класса.
#include
#include
using namespace std;
class three_d {
int x, y, z;
public:
three_d() { x = у = z = 0; }
three_d(int a, int b, int с) { x = a; у = b; z = c; }
three_d &operator+(int a) {
x += a;
у += a;

z += a;
return *this;
}
friend ostream &operator<<(ostream &stream, three_d obj);
friend bool operator<(three_d a, three_d b);
friend bool operator==(three_d a, three_d b);
};
/* Отображаем координаты X, Y, Z с помощью оператора вывода для класса three_d. */
ostream &operator<<(ostream &stream, three_d obj)
{
stream << obj.x << ", ";
stream << obj.у << ", ";
stream << obj.z << "\n";
return stream;
}
bool operator<(three_d a, three_d b)
{
return (a.x + a.у + a.z) < (b.x + b.y + b.z);
}

bool operator==(three_d a, three_d b)
{
return (a.x + a.у + a.z) == (b.x + b.y + b.z);
}
int main()
{
vector v;
unsigned int i;
// Добавляем в вектор объекты.
for(i=0; i<10; i++)
v.push_back(three_d(i, i+2, i-3));
// Отображаем содержимое вектора.
for(i=0; i cout << v[i];
cout << endl;
// Модифицируем объекты в векторе.
for(i=0; i

// Отображаем содержимое модифицированного вектора.
for(i=0; i return 0;
}
Эта программа генерирует такие результаты.
0, 2, -3 1, 3, -2 2, 4, -1 3, 5, 0 5, 7, 2 6, 8, 3 7, 9, 4 8, 10, 5 9, 11, 6 10, 12, 7 11, 13, 8 12, 14, 9 13, 15, 10 14, 16, 11 15, 17, 12 16, 18, 13 17, 19, 14 18, 20, 15 19, 21, 16

Векторы обеспечивают безопасность хранения элементов, обнаруживая при этом чрезвычайную мощь и гибкость их обработки, но уступают массивам в эффективности использования. Поэтому для большинства задач программирования чаще отдается предпочтение обычным массивам. Однако возможны ситуации, когда уникальные особенности векторов оказываются важнее затрат системных ресурсов, связанных с их использованием.
О пользе итераторов
Частично сила библиотеки STL обусловлена тем, что многие ее функции используют итераторы. Этот факт позволяет выполнять операции с двумя контейнерами одновременно.
Рассмотрим, например, такой формат векторной функции insert().
template
void insert(iterator i, InIter start, InIter end);
Эта функция вставляет исходную последовательность, определенную параметрами start
и end, в приемную последовательность, начиная с позиции i. При этом нет никаких требований, чтобы итератор i относился к тому же вектору, с которым связаны итераторы
start и end. Таким образом, используя эту версию функции insert(), можно один вектор вставить в другой. Рассмотрим пример.
// Вставляем один вектор в другой.
#include
#include
using namespace std;
int main()
{
vector v, v2;
unsigned int i;
for(i=0; i<10; i++) v.push_back('A' + i);
// Отображаем исходное содержимое вектора.
cout << "Исходное содержимое вектора:\n";

for(i=0; i cout << v[i] << " ";
cout << endl << endl;
// Инициализируем второй вектор.
char str[] = "-STL — это сила!-";
for(i=0; str[i]; i++) v2 .push_back (str [i]);
/* Получаем итераторы для середины вектора v, а также начала и конца вектора v2. */
vector::iterator р = v.begin()+5;
::iterator p2start = v2.begin();
vector::iterator p2end = v2.end();
// Вставляем вектор v2 в вектор v.
v.insert(p, p2start, p2end);
// Отображаем результат вставки.
cout << "Содержимое вектора v после вставки:\n";
for(i=0; i return 0;
}
При выполнении эта программа генерирует следующие результаты.
Исходное содержимое вектора:

A B C D E F G H I J
Содержимое вектора v после вставки:
A B C D E - S T L -- это cилa! - F G H I J
Как видите, содержимое вектора v2 вставлено в середину вектора v.
По мере дальнейшего изучения возможностей, предоставляемых STL, вы узнаете, что итераторы являются связующими средствами, которые делают библиотеку единым целым.
Они позволяют работать с двумя (и больше) объектами STL одновременно, но особенно полезны при использовании алгоритмов, описанных ниже в этой главе.
Списки
Список — это контейнер с двунаправленным последовательным доступом к его
элементам.
Класс list поддерживает функционирование двунаправленного линейного списка. В
отличие от вектора, в котором реализована поддержка произвольного доступа, список позволяет получать к своим элементам только последовательный доступ.
Двунаправленность списка означает, что доступ к его элементам возможен в двух направлениях: от начала к концу и от конца к началу.
Шаблонная спецификация класса list выглядит следующим образом.
template > class list
Здесь T — тип данных, сохраняемых в списке, а элемент Allocator означает распределитель памяти, который по умолчанию использует стандартный распределитель. В
классе list определены следующие конструкторы.
explicit list(const Allocator &а = Allocator() );
explicit list(size_type num, const T &val = T(), const Allocator
&a = Allocator());
list(const list &ob);
template list(InIter start, InIter end, const
Allocator &a = Allocator());
Конструктор, представленный в первой форме, создает пустой список. Вторая форма предназначена для создания списка, который содержит num элементов со значением val.
Третья создает список, который содержит те же элементы, что и объект ob. Четвертая создает список, который содержит элементы в диапазоне, заданном параметрами start и
end.

Для класса list определены следующие операторы сравнения:
==, <, <=, !=, > и >=
Функции-члены, определенные в классе list, перечислены в табл. 21.3. В конец списка,
как и в конец вектора, элементы можно помещать с помощью функции push_back(), но с помощью функции push_front() можно помещать элементы в начало списка. Элемент можно также вставить и в середину списка, для этого используется функция insert(). Один список можно поместить в другой, используя функцию splice(). А с помощью функции merge() два списка можно объединить и упорядочить результат.

Чтобы достичь максимальной гибкости и переносимости для любого объекта, который подлежит хранению в списке, следует определить конструктор по умолчанию и оператор "
<" (и желательно другие операторы сравнения). Более точные требования к объекту (как к потенциальному элементу списка) необходимо согласовывать в соответствии с документацией на используемый вами компилятор.
Рассмотрим простой пример списка.
// Базовые операции, определенные для списка.
#include
#include
using namespace std;

int main()
{
list lst; // создание пустого списка int i;
for(i=0; i<10; i++) lst.push_back('A'+i);
cout << "Размер = " << lst.size() << endl;
cout << "Содержимое : ";
list::iterator p = lst.begin();
while(p != lst.end()) {
cout << *p;
p++;
}
return 0;
}
Результаты выполнения этой программы таковы:
Размер = 10
Содержимое : ABCDEFGHIJ
При выполнении эта программа создает список символов. Сначала создается пустой объект списка. Затем в него помещается десять букв (от А до J). Заполнение списка реализуется путем использования функции push_back(), которая помещает каждое новое значение в конец существующего списка. После этого отображается размер списка и его содержимое. Содержимое списка выводится на экран в результате выполнения следующего кода.
list::iterator р = lst.begin();

while(p != lst.end()) {
cout << *p;
p++;
}
Здесь итератор p инициализируется таким образом, чтобы он указывал на начало списка.
При выполнении очередного прохода цикла итератор р инкрементируется, чтобы указывать на следующий элемент списка. Этот цикл завершается, когда итератор р указывает на конец списка. Применение подобных циклов — обычная практика при использовании библиотеки
STL. Например, аналогичный цикл мы применили для отображения содержимого вектора в предыдущем разделе.
Поскольку списки являются двунаправленными, заполнение их элементами можно производить с обоих концов. Например, при выполнении следующей программы создается два списка, причем элементы одного из них расположены в порядке, обратном по отношению к другому.
/* Элементы можно помещать в список как с начала, так и с конца.
*/
#include
#include
using namespace std;
int main()
{
list lst;
list revlst;
int i;
for(i=0; i<10; i++ ) lst.push_back('A'+i);
cout << "Размер списка lst = " << lst.size() << endl;

cout << "Исходное содержимое списка: ";
list::iterator p;
/* Удаляем элементы из списка lst и помещаем их в список revlst в обратном порядке. */
while(!lst.empty()) {
р = lst.begin();
cout << *р;
revlst.push_front(*р);
lst.pop_front();
}
cout << endl << endl;
cout << "Размер списка revlst = ";
cout << revlst.size() << endl;
cout << "Реверсированное содержимое списка: ";
p = revlst.begin();
while(p != revlst.end()) {
cout << *p;
p++;
}

return 0;
}
Эта программа генерирует такие результаты.
Размер списка lst = 10
Исходное содержимое списка: ABCDEFGHIJ
Размер списка revlst = 10
Реверсированное содержимое списка: JIHGFEDCBA
В этой программе список реверсируется путем удаления элементов с начала списка lst и занесения их в начало списка revlst.
Сортировка списка
Список можно отсортировать с помощью функции-члена sort(). При выполнении следующей программы создается список случайно выбранных целых чисел, который затем упорядочивается по возрастанию.
// Сортировка списка.
#include
#include
#include
using namespace std;
int main()
{
list lst;
int i;
// Создание списка случайно выбранных целых чисел.
for(i=0; i<10; i++ )lst.push_back(rand() );

cout << "Исходное содержимое списка:\n";
list::iterator p = lst.begin();
while(p != lst.end()) {
cout << *p << " ";
p++;
}
cout << endl << endl;
// Сортировка списка.
lst.sort();
cout << "Отсортированное содержимое списка:\n";
p = lst.begin();
while(p != lst.end()) {
cout << *p << " ";
p++;
}
return 0;
}
Вот как может выглядеть один из возможных вариантов выполнения этой программы.
Исходное содержимое списка:
41 18467 6334 26500 19169 15724 11478 29358 26962 24464
Отсортированное содержимое списка:

41 6334 11478 15724 18467 19169 24464 26500 26962 29358
Объединение одного списка с другим
Один упорядоченный список можно объединить с другим. В результате мы получим упорядоченный список, который включает содержимое двух исходных списков. Новый список остается в вызывающем списке, а второй список становится пустым. В следующем примере выполняется слияние двух списков. Первый список содержит буквы ACEGI, а второй— буквы BDFHJ. Эти списки затем объединяются, в результате чего образуется упорядоченная последовательность букв ABCDEFGHIJ.
// Слияние двух списков.
#include
#include
using namespace std;
int main()
{
list lst1, lst2;
int i;
for(i=0; i<10; i+=2) lst1.push_back('A'+i);
for(i=1; i<11; i+=2) lst2.push_back('A'+i);
cout << "Содержимое списка lst1: ";
list::iterator p = lst1.begin();
while(p != lst1.end()) {
cout << *p;
p++;
}

cout << endl << endl;
cout << "Содержимое списка lst2: ";
р = lst2.begin();
while(p != lst2.end()) {
cout << *p;
p++;
}
cout << endl << endl;
// Теперь сливаем эти два списка.
lst1.merge(lst2);
if(lst2.empty())
cout << "Список lst2 теперь пуст.\n";
cout << "Содержимое списка lst1 после объединения:\n";
р = lst1.begin();
while(p != lst1.end()) {
cout << *p;
p++;
}
return 0;
}
Результаты выполнения этой программы таковы.

Содержимое списка lst1: ACEGI
Содержимое списка lst2: BDFHJ
Список lst2 теперь пуст.
Содержимое списка lst1 после объединения:
ABCDEFGHIJ
Хранение в списке объектов класса
Рассмотрим пример, в котором список используется для хранения объектов типа
myclass. Обратите внимание на то, что для объектов типа myclass перегружены операторы "
<", ">", "!=" и "==". (Для некоторых компиляторов может оказаться излишним определение всех этих операторов или же придется добавить некоторые другие.) В
библиотеке STL эти функции используются для определения упорядочения и равенства объектов в контейнере. Несмотря на то что список не является упорядоченным контейнером, необходимо иметь средство сравнения элементов, которое применяется при их поиске, сортировке или объединении.
// Хранение в списке объектов класса.
#include
#include
#include
using namespace std;
class myclass {
int a, b;
int sum;
public:
myclass() { a = b = 0; }
myclass(int i, int j) {

a = i;
b = j;
sum = a + b;
}
int getsum() { return sum; }
friend bool operator<(const myclass &o1, const myclass &o2);
friend bool operator>(const myclass &o1, const myclass &o2);
friend bool operator==(const myclass &o1, const myclass
&o2);
friend bool operator!=(const myclass &o1, const myclass
&o2);
};
bool operator<(const myclass &o1, const myclass &o2)
{
return o1.sum < o2.sum;
}
bool operator>(const myclass &o1, const myclass &o2)
{
return o1.sum > o2.sum;
}

bool operator==(const myclass &o1, const myclass &o2)
{
return o1.sum == o2.sum;
}
bool operator!=(const myclass &o1, const myclass &o2)
{
return o1.sum != o2.sum;
}
int main()
{
int i;
// Создание первого списка.
list lst1;
for(i=0; i <10; i++) lst1.push_back(myclass(i, i));
cout << "Первый список: ";
list::iterator p = lst1.begin();
while(p != lst1.end()) {
cout << p->getsum() << " ";

p++;
}
cout << endl;
// Создание второго списка.
list lst2;
for(i=0; i<10; i++) lst2.push_back(myclass(i*2, i*3));
cout << "Второй список: ";
p = lst2.begin();
while(p != lst2.end()) {
cout << p->getsum() << " ";
p++;
}
cout << endl;
// Теперь объединяем списки lst1 и lst2.
lst1.merge(lst2);
// Отображаем объединенный список.
cout << "Объединенный список: ";
р = lst1.begin();
while(p != lst1.end()) {
cout << p->getsum() << " ";

p++;
}
return 0;
}
Эта программа создает два списка объектов типа myclass и отображает их содержимое.
Затем выполняется объединение этих двух списков с последующим отображением нового содержимого результирующего списка. Итак, программа генерирует такие результаты.
Первый список: 0 2 4 6 8 10 12 14 16 18
Второй список: 0 5 10 15 20 25 30 35 40 45
Объединенный список: 0 0 2 4 5 6 8 10 10 12 14 15 16 18 20 25 30 35 40 45