Чтобы избежать избыточных определений operator!= из operator== и operator›, ‹=, ›= из operator‹, библиотека обеспечивает следующее:
template ‹class Tl, class T2›
inline bool operator!=(const T1& x, const T2& y) {
return !(x == y);
}
template ‹class Tl, class T2›
inline bool operator›(const T1& x, const T2& y) {
return y ‹ x;
}
template ‹class Tl, class T2›
inline bool operator‹=(const T1& x, const T2& y) {
return !(y ‹ x);
}
template ‹class Tl, class T2›
inline bool operator›=(const T1& x, const T2& y) {
return !(x ‹ y);
}
Библиотека включает шаблоны для разнородных пар значений.
template ‹class T1, class T2›
struct pair {
T1 first;
T2 second;
pair() {}
pair(const T1& x, const T2& y): first(x), second(y) {}
};
template ‹class T1, class T2›
inline bool operator==(const pair‹Tl,T2›& x, const pair‹Tl,T2›& y) {
return x.first == y.first && x.second == y.second;
}
template ‹class T1, class T2›
inline bool operator‹(const pair‹Tl,T2›& x, const pair‹Tl,T2›& y) {
return x.first ‹ y.first || (!(y.first ‹ x.first) && x.second ‹ y.second);
}
Библиотека обеспечивает соответствующую шаблонную функцию make_pair, чтобы упростить конструкцию пар. Вместо выражения, например:
return pair‹int, double›(5, 3.1415926); // явные типы,
можно написать
return make_pair(5, 3.1415926); // типы выводятся.
template ‹class Tl, class T2›
inline pair‹Tl,T2› make_pair(const T1& x, const T2& y) {
return pair‹Tl,T2›(x, y);
}
Итераторы - это обобщение указателей, которые позволяют программисту работать с различными структурами данных (контейнерами) единообразным способом. Чтобы создать шаблонные алгоритмы, которые правильно и эффективно работают с различными типами структур данных, нам нужно формализовать не только интерфейсы, но также семантику и предположения сложности итераторов. Итераторы - это объекты, которые имеют operator*, возвращающий значение некоторого класса или встроенного типа T, называемого значимым типом ( value type ) итератора. Для каждого типа итератора X, для которого определено равенство, имеется соответствующий знаковый целочисленный тип, называемый типом расстояния ( distanсe type ) итератора.
Так как итераторы - обобщение указателей, их семантика - обобщение семантики указателей в C++. Это гарантирует, что каждая шаблонная функция, которая использует итераторы, работает с обычными указателями. Есть пять категорий итераторов в зависимости от операций, определённых для них: ввода ( input iterators ), вывода ( output iterators ), последовательные ( forward iterators ), двунаправленные ( bidirectional iterators ) и произвольного доступа ( random access iterators .) Последовательные итераторы удовлетворяют всем требованиям итераторов ввода и вывода и могут использоваться всякий раз, когда определяется тот или другой вид. Двунаправленные итераторы удовлетворяют всем требованиям последовательных итераторов и могут использоваться всякий раз, когда определяется последовательный итератор. Итераторы произвольного доступа удовлетворяют всем требованиям двунаправленных итераторов и могут использоваться всякий раз, когда определяется двунаправленный итератор. Имеется дополнительный атрибут, который могли быть иметь последовательные, двунаправленные и произвольного доступа итераторы, то есть они могут быть модифицируемые ( mutable ) или постоянные ( constant ) в зависимости от того, ведёт ли себя результат operator* как ссылка или как ссылка на константу. Постоянные итераторы не удовлетворяют требованиям итераторов вывода.
Таблица 1. Отношения среди категорий итераторов
Произвольного доступа -› Двунаправленные -› Последовательные --> |
- › Ввода |
- › Вывода |
Точно также, как обычный указатель на массив гарантирует, что имеется значение указателя, указывающего за последний элемент массива, так и для любого типа итератора имеется значение итератора, который указывает за последний элемент соответствующего контейнера. Эти значения называются законечными ( past-the-end ) значениями. Значения итератора, для которых operator* определён, называются разыменовываемыми ( dereferenceable ). Библиотека никогда не допускает, что законечные значения являются разыменовываемыми. Итераторы могут также иметь исключительные ( singular ) значения, которые не связаны ни с каким контейнером. Например, после объявления неинициализированного указателя x (например, int* x;), всегда должно предполагаться, что x имеет исключительное значение указателя. Результаты большинства выражений не определены для исключительных значений. Единственное исключение - присваивание неисключительного значения итератору, который имеет исключительное значение. В этом случае исключительное значение перезаписывается таким же образом, как любое другое значение. Разыменовываемые и законечные значения всегда являются неисключительными.
Читать дальше