Читайте также:
|
Контейнер vector ведет себя как массив, но может автоматически увеличиваться по мере необходимости. Он поддерживает прямой доступ и связанное хранение и имеет очень гибкую длину. По этим и многим другим причинам контейнер vector является наиболее предпочтительным последовательным контейнером для большинства областей применения.
Контейнер array обладает некоторыми преимуществами контейнера vector, однако его длина не обладает такой гибкостью.
Контейнер deque (двусторонняя очередь) обеспечивает быструю вставку и удаление в начале и в конце контейнера. Он, как и контейнер vector, обладает преимуществами прямого доступа и гибкой длины, но не обеспечивает связанное хранение.
Контейнер list — это двунаправленный список, который обеспечивает двунаправленный доступ, быструю вставку и удаления в любом месте контейнера, но не поддерживает прямой доступ к элементам контейнера.
Контейнер forward_list — однонаправленный список. Это версия контейнера list только с доступом в прямом направлении.
Ассоциативные контейнеры
В ассоциативных контейнерах элементы вставляются в предварительно определенном порядке — например, с сортировкой по возрастанию. Также доступны неупорядоченные ассоциативные контейнеры. Ассоциативные контейнеры можно объединить в два подмножества: сопоставления (set) и наборы (map).
Контейнер map, который иногда называют словарем, состоит из пар "ключ-значение". Ключ используется для упорядочивания последовательности, а значение связано с ключом. Например, map может содержать ключи, представляющие каждое уникальное ключевое слово в тексте, и соответствующие значения, которые обозначают количество повторений каждого слова в тексте. unordered_map — это неупорядоченная версия map.
set — это контейнер уникальных элементов, упорядоченных по возрастанию. Каждое его значение также является и ключом. unordered_set — это неупорядоченная версия set.
Контейнеры map и set разрешают вставку только одного экземпляра ключа или элемента. Если необходимо включить несколько экземпляров элемента, следует использовать контейнер multimap или multiset. Неупорядоченные версии этих контейнеров — unordered_multimap и unordered_multiset. Упорядоченные контейнеры map и set поддерживают двунаправленные итераторы, а их неупорядоченный аналоги — итераторы с перебором в прямом направлении.
Контейнеры-адаптеры
Контейнер-адаптер — это разновидность последовательного или ассоциативного контейнера, который ограничивает интерфейс для простоты и ясности. Контейнеры-адаптеры не поддерживают итераторы.
Контейнер queue соответствует семантике FIFO (первым поступил — первым обслужен). Первый элемент, который отправляется, то есть вставляется, в очередь, должен быть первым элементом, извлекаемым из очереди.
Контейнер priority_queue упорядочен таким образом, что первым в очереди всегда оказывается элемент с наибольшим значением.
Контейнер stack соответствует семантике LIFO (последним поступил — первым обслужен). Последний элемент, отправленный в стек, становится первым извлекаемым элементом.
Поскольку контейнеры-адаптеры не поддерживают итераторы, их нельзя использовать в алгоритмах STL.
Требования для элементов контейнеров
Как правило, элементы, вставленные в контейнер STL, могут быть практически любого типа объекта, если их можно копировать. Элементы, доступные только для перемещения — например, объекты vector<unique_ptr<T>>, создаваемые с помощью unique_ptr<>, — также можно использовать, если вы не вызываете функции-члены, которые пытаются скопировать их.
Деструктору не разрешено вызывать исключение.
Для упорядоченных ассоциативных контейнеров — ранее описанных в этом разделе — необходимо определить открытый оператор сравнения. (По умолчанию это оператор operator<, однако поддерживаются даже типы, которые не работают с operator<.)
Для некоторых операций в контейнерах может также потребоваться открытый конструктор по умолчанию и открытый оператор равенства. Например, неупорядоченным ассоциативным контейнерам требуется поддержка сравнения на равенство и хэширования.
Доступ к элементам контейнера
Доступ к элементам контейнеров осуществляется с помощью итераторов.
Класс vector
Входящий в STL класс vector (вектор) является шаблонным классом последовательных контейнеров, которые упорядочивают элементы заданного типа в линейный порядок и позволяют быстрый произвольный доступ к любому элементу. Векторы являются наиболее подходящим типом контейнера для последовательности, когда на первом месте стоит производительность произвольного доступа.
template <
class Type,
class Allocator = allocator<Type>
>
class vector
Параметры
Тип Тип данных элемента, который должен храниться в векторе
Allocator Тип, представляющий объект хранимого распределителя, инкапсулирующего сведения о выделении и освобождения памяти объекта vector. Этот аргумент является необязательным и по умолчанию используется значение allocator <Type>.
Заметки
Для векторов время выполнения вставок и удалений элементов в конце последовательности является постоянной величиной. Вставка или удаление элементов в середине вектора требует линейное время. Производительность контейнера класс deque главная по отношению к вставкам и удалениям в начале и в конце последовательности. Контейнер класс списка главный по отношению к вставкам и удаления в любом месте внутри последовательности.
Распространение вектора возникает, когда функцию-член следует увеличить последовательностью, содержащейся в объекте вектора за его текущей емкостью устройства хранения. Другие вставки и стирания могут изменять различные адреса хранилища внутри последовательности. Во всех случаях эти итераторы или ссылки, которые указывают на измененные части последовательности будут недопустимыми. Если перераспределение не происходит, только итераторы и ссылки перед точкой вставки и удаления остаются допустимыми.
vector<bool> Класс полная вектора специализация шаблона класса для элементов bool типа с распределителем базового типа, используемого специализации.
Вложенный класс vector<bool> ссылочный класс, объекты которых могут предоставить ссылки на элементы (одним битам) в объект вектора<bool>.
Члены
конструкторов;
| vector | Построение вектора определенного размера или с элементами конкретного значения или с определенным allocator или как копию какого-либо вектора. |
Определения типов
| allocator_type | Тип, представляющий класс allocator для двух объектов. |
| const_iterator | Тип, который предоставляет произвольно-доступный итератор, который может считывать элемент const в векторе. |
| const_pointer | Тип, который содержит указатель элемент const в векторе. |
| const_reference | Тип, который предоставляет ссылку на элемент const хранящихся в векторе для чтения и выполнения операций const. |
| const_reverse_iterator | Тип, который предоставляет произвольно-доступный итератор, который может считывать любой элемент const в векторе. |
| difference_type | Тип, который содержит различие между адресами 2 элементов в векторе. |
| iterator | Тип, который предоставляет произвольно-доступный итератор, который может считывать и изменять любой элемент в векторе. |
| pointer | Тип, который содержит указатель элемент в векторе. |
| reference | Тип, который предоставляет ссылку на элемент, хранящийся в векторе. |
| reverse_iterator | Тип, который предоставляет произвольно-доступный итератор, который может считывать и изменять любой элемент в обращенном векторе. |
| size_type | Тип, который подсчитывает число элементов в векторе. |
| value_type | Тип, представляющий тип данных, хранящихся в векторе. |
Функции-члены
| assign | Удаляет вектор и копирует указанные элементы в пустой вектору. |
| at | Возвращает ссылку на элемент в указанном расположении в векторе. |
| back | Возвращает ссылку на последний элемент вектора. |
| begin | Возвращает произвольно-доступный итератор на первый элемент в векторе. |
| capacity | Возвращает количество элементов, вектор может содержать без выделить больше хранилища. |
| cbegin | Возвращает произвольно-доступный итератор const на первый элемент в векторе. |
| cend | Возвращает произвольно-доступный итератор константного выражения, указывающего только за пределы вектора. |
| crbegin | Возвращает итератор const на первый элемент в обращенном векторе. |
| crend | Возвращает итератор const в конец обращенного вектора. |
| clear | Удаляет элементы вектора. |
| Data | Возвращает указатель на первый элемент в векторе. |
| emplace | Вставляет элемент построен на месте в вектор в указанной позиции. |
| emplace_back | Добавляет элемент, созданный на месте в конец вектора. |
| Empty | Тесты, если контейнер вектора пуст. |
| end | Возвращает произвольно-доступный итератор, указывающий на конец вектора. |
| erase | Удаляет элемент или набор элементов в векторе из заданных позиций. |
| front | Возвращает ссылку на первый элемент в векторе. |
| get_allocator | Возвращает объект в класс allocator используемому вектором. |
| insert | Вставляет один или несколько элементов в вектор в указанной позиции. |
| max_size | Возвращает максимальная длина вектора. |
| pop_back | Удаляет элемент вектора в конце. |
| push_back | Добавьте элемент в конец вектора. |
| rbegin | Возвращает итератор на первый элемент в обращенном векторе. |
| rend | Возвращает итератор в конец обращенного вектора. |
| reserve | Резервирует минимальную длину хранения для двух объектов. |
| resize | Определяет новый размер для двух. |
| shrink_to_fit | Отменяет резерв рабочей мощности. |
| size | Возвращает количество элементов в векторе. |
| swap | Меняет местами элементы 2 векторов. |
Операторы
| operator[] | Возвращает ссылку на элемент вектора в указанной позиции. |
| operator= | Заменяет элементы вектора копией другого вектора. |
Требования
Header:<vector>
Пространство имён: std
Вектор — это своего рода массив с “интеллектом”, помнящий свой размер и поддерживающий свою целостность. Они, среди прочих контейнеров, отличаются эффективностью доступа к элементам. К недостаткам следует отнести сложность вставки элементов в середину вектора, поскольку при этом приходится перемещать часть его содержимого.
Создание векторов
Объявления векторов могут выглядеть примерно так:
#include <vector>
vector<int> vint;
vector<double> vdouble (100);
vector<string> vstr(10);
vector<MyClass> myvect(20);
Короче говоря, вы можете создать либо пустой вектор, либо вектор указанного размера. Кроме размера, можно указать также начальное значение, которое будет присвоено всем элементам:
vector<int> vint1(24, -1);
Можно объявить вектор из объектов своего собственного класса. Следует при этом иметь в виду, что любой структурный тип должен иметь:
· конструктор по умолчанию
· конструктор копии
· деструктор
· операцию взятия адреса
· операцию присваивания.
На самом деле для простых классов, не содержащих указателей на какие-либо динамические объекты, годятся те функции-элементы, что компилятор генерирует сам, за исключением разве что конструктора по умолчанию. (Он генерируется автоматически, только если вы не определили вообще никаких конструкторов. Создаваемые таким конструктором объекты будут содержать “мусор”.) Советую вам обязательно объявлять, хотя бы пустой, конструктор по умолчанию для классов, которые будут размещаться в контейнерах.
Естественно, потребуются еще какие-то механизмы присваивания и извлечения значений элементов данных создаваемого объекта и т. п. Но это вопрос внешний по отношению к функционированию контейнера.
Если вы хотите выполнять поиск или сортировку, потребуются операции равенства (==) и “меньше” (<).
Скелет класса, пригодного для помещения в вектор, может иметь такой вид:
class Coord {
int x, у;
public:
Coord(): x(0), у(0) {}
void set(int _x, int y) { x = x; у = _y; }
void get(int &_x, int &_y) { _x = x, _y = y;) };
Для доступа к данным вектора применяется индексация:
vstr[3] = "Third value: ";
vdouble[10] = 3.3333333333;
cout<< vstr[l]<< vdouble[10] << endl;
Можно конструировать вектор с помощью итераторов, например:
int iArr[16];
vector<int> iVectl(iArr, iArr + 16);
vector<int> iVect2(iVect!.begin(), iVect!.end());
(Для обычного массива, как мы уже говорили, итератором является простой указатель. Второй из векторов конструируется из первого спецификацией его начального и конечного итераторов.)
Действия над векторами
Вектор характеризуется своим размером и вместимостью. Размер — это число элементов, хранящихся в векторе в настоящий момент. Вместимость показывает предел увеличения размера вектора без дополнительного выделения памяти.
Размер и вместимость вектора можно получить с помощью его методов size() и capacity():
cout <<"Size: "<< vdouble.size ()<<"Capacity: " << vdouble.capacity () <<end1;
Есть еще функция max_size(), которая возвращает верхний предел размера и вместимости, определяемый обычно размером наибольшего доступного блока памяти.
Функция resize () позволяет изменить размер массива. Функция is_empty () возвращает true, если вектор пуст (размер равен 0). Вместимость вектора можно изменить его функцией reserve (). Заблаговременное резервирование позволяет избежать частых автоматических выделений памяти:
vdouble.reserve (1000);
Функция clear () удаляет все элементы вектора.
Функция assign () присваивает указанное значение первым n элементам:
vdouble.assign (100, 1.0);
Альтернативная форма функции позволяет присвоить элементам значения из диапазона другого контейнера:
void assign (Input-Iterator first, Inputlterator last);
Функции front() и back () возвращают значения соответственно первого и последнего элементов вектора.
Наиболее часто используемыми функциями векторов являются, вероятно, erase () и insert (). Они служат для удаления и вставки элементов. При удалении элемента (или нескольких элементов) из вектора все последующие сдвигаются к началу. Эти функции перегружены; мы приводим только две формы insert ():
iterator erase (iterator position);
iterator erase (iterator first, iterator last);
iterator insert(iterator pos, const T& x);
void insert(iterator pos,
Inputlterator first, Inputlterator last);
Эти функции позволяют соответственно удалить элемент, удалить диапазон, вставить элемент и вставить диапазон элементов из другого контейнера.
С помощью функций push_back () и pop_back () вектор можно использовать как стек. Первая из них вставляет элемент в конец вектора, вторая — удаляет конечный элемент (она не возвращает его значение).
Вот небольшая иллюстрация:
#include <iostream>
#include <vector>
#pragma hdrstop
#include <condefs.h>
using namespace std;
//
// Вспомогательная функция для вывода содержимого контейнера
//
template<class T> void Display(const Т &с) {
cout<< "(";
copy(с.begin (), c.end(),
ostream_iterator<T::value_type> (cout, " "));
cout << "} Size: " << c.size() << endl;
}
int main ()
(
int iarr[5] = (1, 2, 3, 4, 5);
vector<int> vintl(iarr, iarr + 5);
cout << "Initial vector: ";
Display(vinti);
vector<int>::iterator p =
find(vinti.begin (), vintl.end(), 3);
vinti.erase (p);
cout << "After erasing 3: ";
Display(vinti);
vinti.insert (p, iarr, iarr + 3);
cout << "After insertion: ";
Display(vinti);
cout << "Pop and push: ";
vinti.pop_back();
Display(vinti);
vinti.push back(33);
cout << " Display(vinti);
vinti.pop_back ();
return 0;
}
Программа выводит:
Initial vector: {12345} Size: 5
After erasing 3: {1245} Size: 4
After insertion: {1212345} Size: 7
Pop and push: {121234} Size: 6
{ 1 2 1 2 3 4 33 } Size: 7
42. Объектно-ориентированные приложения. Объектно-ориентированные стековые операции в С++. Объектно-ориентированный связанный список в С++. Динамическое распределение памяти: связанные списки. Особенности использования связанных списков.
Законченный проект программы со связанным списком и всеми (семью) характеристиками ООП. Создание родительского класса. Производные классы-потомки. Использование дружественного класса. Анализ законченной программы объектно-ориентированного связанного списка. Эти 2 вопроса объединены в один. (нужны допы)
Работа в объектно-ориентированной среде.
Правила объектно-ориентированного программирования.
class base
{
private:
data obj;
public:
virtual ~base(void);
base(void);
base(const base &r);
const base& operator=(const base &r);
private:
// private function.
};
//———————-
base::~base(void){}
inline base::base(void):obj(value){}
inline base::base(const base &r):obj(r.obj){}
inline const base& base::operator=(const base &r)
{
if(this!=&r)
{
obj=r.obj;
}
return *this;
}
//———————————
class derived:public base
{
private:
cls obj;
public:
virtual ~derived(void);
derived(void);
derived(const derived &r);
const derived& operator=(const derived &r);
private:
// private function.
};
//———————-
derived::~derived(void){}
inline derived::derived(void):base(value),obj(value){}
inline derived::derived(const derived &r):base(r),obj(r.obj){}
inline const derived& derived::operator=(const derived &r)
{
if(this!=&r)
{
((base)this)=r;
obj=r.obj;
}
return *this;
}
Примеры объектно ориентированных программ
Объектно ориентированный код во всех языках программирования имеет некоторые общие особенности, имеется семь общих стандартных характеристик истинных объектно-ориентированных программ:
Объектно-ориентированные стековые операции.
Рассмотрим пример класса С++, реализующего стековые операции.
Стеком называется связный список объектов с доступом в одной точке — вершине стека. Добавлять или извлекать элементы стека можно только через его вершину. Таким образом последний добавленный элемент будет извлечен первым.
Класс, реализующий стек, является простой, объектно-ориентированной программой, хотя в нем и не используются управление памятью, наследование и полиморфизм.
В классе имеется шесть методов для управления стеком: clear() - очистка, top() - определение верхнего элемента, isempty() - проверка стека на пустоту, isfull() - проверка стека на полное заполнение, push() - извлечение из стека, pop() - заталкивание в стек.
#include <string.h>
#include <iostream.h>
class stack
{
enum {maxlen=80};
char str1[maxlen];
int first;
public:
void clear(){first=0;}
char top(){return str1[first];}
int isempty(){return (first==0);}
int isfull(){return (first==maxlen-1);}
void push(char chr){str[++first]=chr;}
char pop(){return (str1[first--]);}
};
main()
{
stack mystack;
char str[11]=”0123456789”;
mystack.clear();
int i;
// Load string to stack:
for(i=0;i<strlen(str);i++)
{
if(!mystack.isfull())
mystack.push(str[i]);
cout<<str[i]<<endl;
}
// Unload characters from stack
while(!mystac.isempty())
cout<<mystack.pop()<<endl;
return 0;
}
Загрузка и выгрузка выполняются через верхушку стека, поэтому первый записываемый символ оказывается наиболее глубоко.
Объектно-ориентированные связанные списки.
Связным списком называется связный набор элементов со связями, устанавливающими порядок следования объектов в списке. Первый элемент списка называют головой списка, последний — хвостом. Наиболее часто рассматривают односвязный список, в котором устанавливаются связи типа "Следующий", и двусвязный список со связями типа "Предыдущий-Следующий". Доступ к элементам списка осуществляется посредством операций определения предыдущего и последующего элемента по уже известному (например по голове или хвосту).
Для реализации концепции связанного списка необходимы все характеристики ООП.
Рассмотрим пример, создающий информационный список сотрудников.
Родительский класс nnr содержит сведения, общие для всех порождаемых классов-потомков (фамилия и имя сотрудника, должность, номер социальной страховки и стаж работы), они содержатся в разделе protected. Класс использует дружественный класс payroll_list:
class nnr
{
friend class payroll_list;
protected:
char lstname[20];
char fstname[15];
char job_title[30];
char sosial_sec[12];
int year_hired;
nnr *pointer;
nnr *next_link;
public:
nnr(…){…next_link=0;}
void send_info();
…
};
На основе класс nnr строятся классы-потомки, один из них salesperson:
class salesperson:publuc nnr
{
friend class payroll_list;
private:
float sales;
int comm_rate;
public:
salesperson(…):nnr(…){sales=…;}
void fill_sales(float d_sales)
{sales=d_sales;}
void fill_comm_rate(int d_rate)
{comm_rate=d_rate;}
void add_info(){pointer=this;}
void send_info()
{
nnr::send_info();
cout<<”sales ”<<sales<<endl;
cout<<”Commision ”<<comm_rate;
}
};
В этом классе добавляется два частных элемента (общая продажа и процент комиссионных). Для выделения памяти для каждого дополнительного элемента связного списка в методы addinfoиспользуется не операция динамического выделения памяти, а указатель на объект this.
Выходная информация о конкретном сотруднике является уникальной. Функция send_info выводит сначала общую информацию вызовом методы базового класса, а затем частную информацию.
В дружественном классе payroll_list содержатся средства для печати связанного списка, добавления и удаления записей в списке:
class payroll_list
{
private:
nnr *location;
public:
payroll_list(){location=0;}
void print_payroll_list();
void insert_employee(nnr *node);
void remove_employee(char *social_sec);
…
};
Рассмотрим функцию print_payroll_list(). Сначала в ней значение указателя на список присваиваивается переменной present. если указатель не нулевой, то в списке есть еще записи, которые передаются методы send_info(). Далее указатель смещается, и процесс повторяется:
void payroll_list::print _payroll_list()
{
nnr *present=location;
while(present!=0)
{
present_>send_info();
present=present_>next_link;
}
}
Переменная pointer содержит адрес памяти, где находится данный представитель класса. Это значение используется в методы insert_employee() для реализации связи между записями связного списка. При добавлении записи располагаются в алфавитном порядке по фамилиям сотрудников. Когда находится уже имеющаяся в списке фамилия (node_>lstname), большая, чем current_node_>lstname, то первый цикл заканчивается. Это стандартная процедура вставки в связанный список: указатель previous_node ссылается на запись, после которой вставляется новая запись, а current_node указывает на запись, которая будет следовать за вновь добавленной записью.
Когда точка вставки определена, программа создает новую связь или узел путем вызова методы node_>add_info(). Указатель current_node связывается с указателем next_link этого нового узла. Кроме того, проводится проверка на начало списка:
void payroll_list::insert_employee(nnr* node)
{
nnr *current_node=location;
nnr *previoise_node=0;
while(current_node!=0 &&
strcmp(current_node->lstrname,node->lstrname)<0)
{
previous_node=current_node;
current_node=current_node->next_link;
}
node->add_info();
node->pointer->next_link=current_node;
if(previouse_node==0)
location=node->pointer;
else
previouse_node->next_link=node->pointer;
}
При удалении из связного списка используется номер социальной страховки для исключения возможности ошибочного удаления. Алгоритм удаления аналогичен предыдущему:
void payroll_list::remove_employee(char* social_sec)
{
nnr *current_node=location;
nnr *previoise_node=0;
while(current_node!=0 &&
strcmp(current_node->social_sec,social_sec)!=0)
{
previous_node=current_node;
current_node=current_node->next_link;
}
if(current_node!=0 && previouse_node==0)
{
location=current_node->nex_link;
delete current_node;
}else
if(current_node!=0 && previouse_node!=0)
{
previouse_node->next_link=current_node->next_link;
delete current_node;
}
}
Первый условный оператор соответствует началу списка. В этом случае указатель начала списка перемещается к следующему элементу. Второй оператор if используется для удаления промежуточного узла. Для этого более удаленному узлу присваиваивается адрес узла, который следует за удаляемым.
Основные понятия (7 понятий ООП)
Дата добавления: 2015-09-03; просмотров: 272 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Структура библиотеки | | | Абстракция |