Технология ООП
Санкт-Петербургский государственный политехнический университет
11 октября 2011
Технология ООП
Цель введения стандартных имен типов
Каждый контейнер:
с помощью typedef дает стандартные имена используемым
типам
определяет эти типы своим способом, наиболее
подходящим для реализации
Следовательно, все псевдонимы во внешний мир передаются
одинаково.
Технология ООП
Стандартные имена типов
Пример псевдонима в классе MyVector.
template<typename T> c l a s s MyVector {
typedef T value_type ;
};
i n t main ( )
{
i n t k1 ;
MyVector<i n t > : : v a l u e _ t y p e k2 ;
}
Технология ООП
Псевдонимы контейнеров STL
value_type // тип элемента к он те й не р а
allocator_type // тип распределите ля памяти
size_type // тип индексов ( э к в и в а л е н т
s i z e o f ( ) элемента )
difference_type // тип р е з у л ь т а т а вычитания
адрес ов двух элементов
iterator // v a l u e _ t y p e ∗
const_iterator // c o n s t v a l u e _ t y p e ∗
reverse_iterator // v a l u e _ t y p e ∗ в обратном
порядке
c o n s t _ r e v e r s e _ i t e r a t o r // c o n s t v a l u e _ t y p e ∗
reference // v a l u e _ t y p e&
const_ r e f e r e n c e // c o n s t v a l u e _ t y p e&
Технология ООП
Пример использования псевдонима value_type
Пример псевдонима value_type для нахождения суммы
элементов произвольного контейнера.
template<typename C> typename C : : v a l u e _ t y p e sum ( C&
c)
// typename о б я з а т е л ь н о
{
/∗ typename ∗/ C : : v a l u e _ t y p e s = C : : v a l u e _ t y p e ( ) ;
// typename н е о б я з а т е л ь н о
/∗ typename ∗/ C : : i t e r a t o r i t = c . b e g i n ( ) ;
w h i l e ( i t != c . end ( ) )
{
s += ∗ i t ;
++i t ;
}
return s ;
}
Технология ООП
Пример использования псевдонима value_type
i n t main ( )
{
MyVector<i n t > v ( 1 0 , 1 ) ;
i n t r e s = sum ( v ) ; //
MyVector<double> v1 ( 1 0 , 1 . 1 ) ;
double r e s 1 = sum ( v1 ) ; //
MyVector<MyString > v2 ( 1 0 , M y S t r i n g ( "A" ) ) ;
M y S t r i n g r e s 2 = sum ( v2 ) ; //
}
Технология ООП
Шаблонные методы класса
Обычные методы (в частности, конструктор) могут быть
шаблонными, базирующимися на другом типе параметра.
Виртуальные методы не могут быть шаблонными.
Технология ООП
Пример использования шаблонных методов класса
template <c l a s s T , i n t s i z e > c l a s s MyArray
{
T m_ar [ s i z e ] ;
public :
v o i d copy (T∗ p , s i z e _ t num)
{
i n t n = ( num<s i z e ) ? num : size ;
f o r ( i n t i = 0 ; i <n ; i ++) { m_ar [ i ] = p [ i ] ; }
}
};
i n t main ( ) {
MyArray<i n t , 5> a ;
a [ 0 ] = 5 . 5 ; //OK
int i a r [20] = {4 ,7 ,8};
a . copy ( i a r , 2 0 ) ; //OK
double d a r [ 1 0 ] = { 1 . 1 , 2 . 2 , 3 . 3 ,...};
a . copy ( dar , 1 0 ) ; // ошибка
}
Технология ООП
Пример использования шаблонных методов класса
template <c l a s s T , i n t s i z e > c l a s s MyArray
{
T m_ar [ s i z e ] ;
public :
template<typename Other> v o i d copy ( O t h e r ∗ p ,
s i z e _ t num)
{
i n t n = ( num<s i z e ) ? num : s i z e ;
f o r ( i n t i = 0 ; i <n ; i ++) { m_ar [ i ] = p [ i ] ; }
}
};
Технология ООП
Виртуальные методы шаблонных классов
шаблоны могут участвовать в наследовании (при этом
перемежаться с нешаблонными классами)
методы шаблонных классов (не шаблонные) могут быть
виртуальными
Технология ООП
Виртуальные методы шаблонных классов
template<typename T> c l a s s A{
T m_a;
p u b l i c : A( const T& a ) {m_a = a ; }
v i r t u a l v o i d f ( ) {m_a++;}
};
template<typename T> c l a s s B : p u b l i c A<T>{
T m_b;
p u b l i c : B( const T& a , const T& b ) : A<T>(a ) {m_b
= b;}
v i r t u a l v o i d f ( ) {m_b++;}
};
i n t main ( )
{
B<i n t >∗ pB = new B<i n t >(1 ,5) ;
A<i n t >∗ pA = new B<i n t >(1 ,5) ;
pA−>f ( ) ;
pB−>f ( ) ;
}
Технология ООП
typename
c l a s s A{
public :
c l a s s B{
};
};
template<typename T> c l a s s C{
typename T : : B∗ p ;
};
C<A> c c c ;
Технология ООП
Специализация шаблонного класса
template<> c l a s s MyArray<i n t ,10 >;
template c l a s s MyArray<i n t ,10 >;
template i n t& MyArray<i n t , 1 0 > : : o p e r a t o r [ ] ( i n t ) ;
Технология ООП
std::vector
template<c l a s s _Ty ,
c l a s s _Ax = a l l o c a t o r <_Ty> >
class vector
: p u b l i c _Vector_val<_Ty , _Ax>
{...};
Распределитель памяти (allocator) — отвечает за выделение,
освобождение, перераспределение памяти. Для специфических
задач программисту предоставляется возможность реализовать
собственный алокатор. Класс _Vector_val содержит
встроенный объект распределителя памяти (алокатора).
Технология ООП
Внутреннее устройство vector
Размеры vector:
size() //???
capaсity() //???
Технология ООП
Оптимизации операций
Технология ООП
Конструкторы vector
vector ( ) ;
e x p l i c i t v e c t o r ( s i z e _ t y p e _Count ) ;
v e c t o r ( s i z e _ t y p e _Count , const Type& _Val ) ;
v e c t o r ( const v e c t o r& _Right ) ;
template<c l a s s I n p u t I t e r a t o r > v e c t o r ( I n p u t I t e r a t o r
_ F i r s t , I n p u t I t e r a t o r _Last ) ;
v e c t o r ( v e c t o r&& _Right ) ;
Технология ООП
Методы, связанные с размером
s i z e _ t y p e s i z e ( ) const ;
s i z e _ t y p e c a p a c i t y ( ) const ;
void r e s e r v e ( size_type n ) ;
void r e s i z e ( size_type n ) ;
v o i d r e s i z e ( s i z e _ t y p e n , T& x ) ;
s i z e _ t y p e max_size ( ) const ;
bool empty ( ) const ;
Технология ООП
Примеры использования методов управления размером
v e c t o r <i n t > v ;
v . r e s i z e (10) ;
s i z e _ t n = v . s i z e ( ) ; //
v e c t o r <i n t > v ;
v . r e s e r v e (10) ;
s i z e _ t n = v . s i z e ( ) ; //
Технология ООП
Получение/модификация значений элементов
reference at ( s i z e _ t y p e pos ) ;
reference operator [ ] ( s i z e _ t y p e pos ) ;
reference front () ;
reference back ( ) ;
Технология ООП
Получение/модификация значений элементов
v e c t o r <i n t > v ( 1 0 , 1 ) ;
// Распечатать значения элементов
// ???
// Получить / изменить значение i −ого элемента
// ???
Технология ООП
Вставка/удаление последнего элемента
v o i d push_back ( const T& x ) ;
v o i d pop_back ( ) ;
v e c t o r <i n t > v ;
v . r e s i z e (10) ;
v . push_back ( 1 ) ;
s i z e _ t n = v . s i z e ( ) ; //
v e c t o r <i n t > v ;
v . r e s e r v e (10) ;
v . push_back ( 1 ) ;
s i z e _ t n = v . s i z e ( ) ; //
Нет операций с началом последовательности: push_front(),
pop_front()
Технология ООП
Использование итераторов
i t e r a t o r begin () ;
c o n s t _ i t e r a t o r b e g i n ( ) const ;
i t e r a t o r end ( ) ;
i t e r a t o r end ( ) const ;
reverse_iterator rbegin () ;
c o n s t _ r e v e r s e _ i t e r a t o r r b e g i n ( ) const ;
r e v e r s e _ i t e r a t o r rend () ;
c o n s t _ r e v e r s e _ i t e r a t o r r e n d ( ) const ;
Технология ООП
Использование итераторов
Пример: прохождение последовательности в обратном порядке
с помощью “прямого” итератора
char a r [ ] = "QWERTY" ;
// с о з д а т ь вектор , элементы к о т о р о г о должны быть
копиями символов массива
// с о з д а т ь итератор для в е к т о р а
// вывести значения элементов в е к т о р а с помощью
и те р а т о р а
Технология ООП
Использование итераторов
char a r [ ] = "QWERTY" ;
v e c t o r <char> v ( ar , a r+s i z e o f ( a r ) −1) ;
v e c t o r <char > : : i t e r a t o r i t =v . end ( ) ;
w h i l e ( i t != v . b e g i n ( ) )
{
i t −−;
cout <<∗i t <<"␣" ;
}
cout <<e n d l ;
Технология ООП
Использование итераторов
Пример: прохождение последовательности в обратном порядке
с помощью “реверсивного” итератора
char a r [ ] = "QWERTY" ;
v e c t o r <char> v ( ar , a r+s i z e o f ( a r ) −1) ;
v e c t o r <char > : : r e v e r s e _ i t e r a t o r r i t =v . r b e g i n ( ) ;
w h i l e ( r i t != v . r e n d ( ) )
{
cout <<∗ r i t <<"␣" ;
r i t ++; // ! ! ! !
}
cout <<e n d l ;
Технология ООП
operator ->
c l a s s A{ i n t m_a;
p u b l i c : A( i n t a=0){m_a = a ; }
i n t GetA ( ) { r e t u r n m_a; }
};
i n t main ( )
{
v e c t o r <A> v ( 1 0 , A( 1 ) ) ;
v e c t o r <A> : : i t e r a t o r i t = v . b e g i n ( ) ;
w h i l e ( i t != v . end ( ) )
{
s t d : : cout << ( ∗ i t ) . GetA ( ) ;
s t d : : cout << i t −>GetA ( ) ;
++i t ;
}
}
Технология ООП
Оператор замещения
void a s s i g n ( c o n s t _ i t e r a t o r f i r s t , c o n s t _ i t e r a t o r
last ) ;
v o i d a s s i g n ( s i z e _ t y p e n , const T& x ) ;
v e c t o r <i n t > v1 ( 1 0 , 1 ) ;
v e c t o r <i n t > v2 ( 1 1 , 1 2 ) ;
i n t ar [ ] = {5 ,7 ,1 , −6 , . . . } ;
// заменить элементы v1 на элементы v2
// заменить элементы v1 на элементы a r
Технология ООП
Оператор вставки
i t e r a t o r i n s e r t ( i t e r a t o r i t , const T& x ) ;
v o i d i n s e r t ( i t e r a t o r i t , s i z e _ t y p e n , const T& x ) ;
void i n s e r t ( i t e r a t o r i t , c o n s t _ i t e r a t o r f i r s t ,
const_iterator last ) ;
Технология ООП
Пример использования оператора вставки
v e c t o r <i n t > v ;
//формируем значения элементов таким образом , чтобы
содержимое в е к т о р а стало 1 , 2 , 3 , 4
// т р е б у е т с я в с т а в и т ь между элементами значение 33 −
1 ,33 ,2 ,33 ,3 ,33 ,4
Технология ООП
Пример использования оператора вставки
v e c t o r <i n t > : : i t e r a t o r i t =v . b e g i n ( ) ;
int size = v . size () ;
f o r ( i n t i =0; i <s i z e ; i++ )
{
++i t ;
i t = v . i n s e r t ( i t , 33) ;
++i t ;
}
Технология ООП
Оператор удаления
iterator erase ( iterator i t ) ;
iterator erase ( iterator f i r s t , iterator last ) ;
void c l e a r ( ) ;
Требуется удалить все 33 из полученного вектора v.
Технология ООП
Пример использования оператора удаления
v e c t o r <i n t > : : i t e r a t o r i t =v . b e g i n ( ) ;
w h i l e ( i t != v . end ( ) )
{
i f ( ∗ i t ==33) {
i t = v . erase ( i t ) ;
}
else {
++i t ;
}
}
Технология ООП
Уменьшение емкости вектора
void s h r i n k _ t o _ f i t ( ) ;
Обмен двух векторов местами:
v o i d swap ( v e c t o r <Type , A l l o c a t o r >& x ) ;
Технология ООП
Пример создание двухмерных массивов
v e c t o r < v e c t o r <i n t > > vv ;
t y p e d e f v e c t o r <i n t > VECT_INT ;
v e c t o r <VECT_INT> vv ;
В отличие от обычного массива строки такого вектора могут
быть разной длины.
Технология ООП
Пример использования класса vector
v e c t o r < v e c t o r <i n t > > vv1 ( 1 0 , v e c t o r <i n t >(10 ,1) ) ;
//
v e c t o r < v e c t o r <i n t > > vv2 ; //
vv2 [ 2 ] [ 5 ] = 1 ; //
vv2 . a t ( 2 ) . a t ( 5 ) = 1 ; //
//
int ar [ 1 0 ] [ 3 ] = {{1 ,2 ,3} ,{4 ,5 ,6} ,};
// Создать в е к т о р в е к т о р о в таким образом , чтобы
элементы каждого в е к т о р а стали копиями
элементов соответствующей строки массива
Технология ООП
Если вектор содержит указатели
{
v e c t o r <M y S t r i n g∗> v ;
v . push_back ( new M y S t r i n g ( "AAA" ) ) ;
v . push_back ( new M y S t r i n g ( "BBB" ) ) ;
// Печать
} // ???
Технология ООП