Последнее обновление：2026-10-12

Извлечение типов traits в STL

0. Введение

В программировании на STL контейнеры и алгоритмы проектируются независимо, то есть структуры данных и алгоритмы разрабатываются по отдельности; мостом, соединяющим контейнеры и алгоритмы, являются итераторы — именно они делают такое независимое проектирование возможным. Как показано на схеме ниже:

Приведённая схема показывает: цель STL — разделить данные и алгоритмы, проектировать их по отдельности, а затем склеить их обратно посредством вещи под названием iterator.

В шаблонах проектирования об iterator сказано: способ последовательного доступа к каждому элементу контейнера, при котором не раскрывается внутреннее представление контейнера. А техника извлечения типов как раз и предназначена для решения проблем, связанных с iterator.

Применение обобщённых алгоритмов (find, count, find_if) к некоторому контейнеру требует прежде всего дать алгоритму инструмент доступа к элементам контейнера — и эту важную роль играет iterator.

В алгоритмах нам может понадобиться объявить простые промежуточные переменные или задать тип возвращаемой переменной алгоритма. В этот момент нужно знать, каков тип элемента, на который указывает итератор, но поскольку функций определения типа вроде typeof нет, получить его напрямую мы не можем — что же делать? Об этом и пойдёт речь в этой статье.

Итератор — это своего рода умный указатель, поэтому он обладает всеми особенностями обычного указателя — к нему применимы операции * и ->. Однако при обходе контейнера неизбежно нужно хоть что-то знать о его внутреннем устройстве, поэтому разработку итераторов проще всего возложить на разработчиков контейнера: так все детали реализации, наоборот, оказываются инкапсулированы и скрыты от пользователя — именно поэтому каждый контейнер STL предоставляет собственный итератор.

А Traits в bits/stl_iterator_base_types.h:

template<class _Tp>
struct iterator_traits<_Tp*>
{
    typedef ptrdiff_t difference_type;
    typedef typename _Tp::value_type value_type;
    typedef typename _Tp::pointer pointer;
    typedef typename _Tp::reference reference;
    typedef typename _Tp::iterator_category iterator_category;
};

Смотрите и ничего не понимаете? Ничего страшного: прочитав этот раздел, вы войдёте в STL, ха-ха~

1. Выведение параметров template

Прежде всего, при использовании итераторов в алгоритмах весьма вероятно, что понадобятся их связанные типы (associated type) — тип того, на что итератор указывает. Предположим, алгоритму необходимо объявить переменную с типом «тип объекта, на который указывает итератор». Что делать?

Решение: воспользоваться механизмом выведения аргументов function template.

Например:

Если T — некоторый указатель на конкретный объект, то как в func получить тип объекта, на который указывает указатель? Это довольно просто: с задачей справится механизм выведения аргументов шаблона,

template <class I>
inline
void func(I iter) {
    func_impl(iter, *iter); // 传入iter和iter所指的值，class自动推导
}

Благодаря механизму выведения шаблона мы запросто получаем тип объекта, на который указывает указатель.

template <class I, class T>
void func_impl(I iter, T t) {
        T tmp; // 这里就是迭代器所指物的类别
        // ... 功能实现
}

int main() {
    int i;
    func(&i);
}

Но механизм «выведения аргументов template» функции выводит только аргументы и не может вывести тип возвращаемого значения функции. Если потребуется вывести возвращаемое значение функции, он бессилен. Поэтому мы приходим к следующему методу.

2. Объявление вложенного типа

Тип объекта, на который указывает итератор, называется value type итератора.

Хотя в func_impl мы можем сделать T возвращаемым значением функции, проблема в том, что пользователь вызывает func.

template <class I, class T>
T func_impl(I iter, T t) {
        T tmp; // 这里就是迭代器所指物的类别
        // ... 功能实现
}
template <class T>
(*T) func(T t) { // !!!Wrong code
    return func_impl(t, *t); // forward the task to func_impl
}
int main() {
    int i  =10;
    cout<<func(&i)<<endl; // !!! Can’t pass compile
}

Если скомпилировать этот код — компиляция завершится неудачей!

Эта проблема тоже несложно решается: объявление вложенного типа выглядит неплохой идеей, ведь тогда мы сможем получать тип напрямую. Достаточно сделать iterator и при определении задать псевдоним для типа указуемого объекта — вот так:

template <class T>
struct MyIter {
    typedef T value_type; // 内嵌型别声明
    T* ptr;
    MyIter(T* p = 0) : ptr(p) {}
    T& operator*() const { return *ptr; }
};

template <class I>
typename I::value_type
func(I ite) {
    std::cout << "class version" << std::endl;
    return *ite;
}
int main() {
    // ...
    MyIter<int> ite(new int(8));
    cout << func(ite);  // 输出8
}

Весьма элегантное решение, выглядит всё прекрасно. Но на деле проблема остаётся: если func — обобщённый алгоритм, он обязан также принимать обычный указатель в качестве итератора, однако очевидно, что следующий код скомпилировать не удастся:

int *p = new int(5);
cout<<func(p)<<endl; // error

Наш func не поддерживает обычные указатели, что, разумеется, неприемлемо. Тут и пригодится template partial specialization.

3. Traits — спаситель

Как уже говорилось, при прямом использовании typename I::value_type алгоритм не сможет принимать обычные указатели, поскольку у обычного указателя вовсе нет вложенного типа value_type.

Поэтому нужно добавить промежуточный слой, который будет проверять, не является ли это обычным указателем, — и в этом вся прелесть приёма traits.

Если ограничиться описанным выше подходом, то есть вложенным value_type, то для указателей без value_type придётся делать частичную специализацию — причём частичную специализацию вызываемой функции func; если бы в func был миллион строк кода, это создало бы чудовищное визуальное загрязнение.

（1）Частичная специализация функции

Частичная специализация функции:

template <class T>
struct MyIter {
    typedef T value_type; // 内嵌型别声明
    T* ptr;
    MyIter(T* p = 0) : ptr(p) {}
    T& operator*() const { return *ptr; }
};

template <class I>
typename I::value_type
func(I ite) {
    std::cout << "class version" << std::endl;
    return *ite;
}
template <class I>
I
func(I* ite) {
    std::cout << "pointer version" << std::endl;
    return *ite;
}
template <class I>
I func(const I* ite) {
    std::cout << "const pointer version" << std::endl;
    return *ite;
}
int main() {
    // ...
    MyIter<int> ite(new int(8));
    cout << func(ite)<<endl;
    int *p = new int(52);
    cout<<func(p)<<endl;
    const int k = 3;
    cout<<func(&k)<<endl;
}

Вывод:

class version
8
pointer version
52
const pointer version
3

（2）Добавляем промежуточный слой

Что же такое Traits в STL? Взгляните на схему:

Промежуточный слой iterator_traits фиксирует форму func и резко сокращает дублирование кода; всё, что остаётся, — слегка специализировать iterator_traits, чтобы он поддерживал pointer и const pointer:)

#include <iostream>

template <class T>
struct MyIter {
    typedef T value_type; // 内嵌型别声明
    T* ptr;
    MyIter(T* p = 0) : ptr(p) {}
    T& operator*() const { return *ptr; }
};
// class type
template <class T>
struct iterator_traits {
    typedef typename T::value_type value_type;
};
// 偏特化1
template <class T>
struct iterator_traits<T*> {
    typedef T value_type;
};
// 偏特化2
template <class T>
struct iterator_traits<const T*> {
    typedef T value_type;
};

template <class I>
typename iterator_traits<I>::value_type
// 首先询问iterator_traits<I>::value_type,如果传递的I为指针,则进入特化版本,iterator_traits直接回答;如果传递进来的I为class type,就去询问T::value_type.
func(I ite) {
    std::cout << "normal version" << std::endl;
    return *ite;
}
int main() {
    // ...
    MyIter<int> ite(new int(8));
    std::cout << func(ite)<<std::endl;
    int *p = new int(52);
    std::cout<<func(p)<<std::endl;
    const int k = 3;
    std::cout<<func(&k)<<std::endl;
}

Описанный процесс таков: сначала спрашивается iterator_traits<I>::value_type; если переданный I — указатель, входит специализированная версия, и iterator_traits отвечает напрямую T; если же переданный I — class type, вопрос переадресуется T::value_type.

Популярное объяснение: алгоритм (func) спрашивает iterator_traits (меня), но когда iterator_traits (я) обнаруживает, что у него в руках указатель, я отвечаю за него сам. Если же это class type, iterator_traits (я) продолжает спрашивать (его — T::value_type).

Итог: объявляя вложенный тип, мы получили способ узнавать тип элемента, на который указывает iterator; с помощью приёма traits мы объединили определения шаблона функции для обычных указателей и пользовательских iterator. Приём traits используется главным образом для устранения дублирования кода, порождаемого различиями между обычными указателями и пользовательскими iterator, — в этом и заключается прелесть приёма traits.

Книги для изучения:

侯捷《 STL 源码剖析》

Статьи для изучения:

https://juejin.im/post/5b1a43fb51882513bf1795c6

https://www.cnblogs.com/mangoyuan/p/6446046.html

http://www.cppblog.com/nacci/archive/2005/11/03/911.aspx

Похожие темы

• Анализ исходников STL array | C++那些事
• Глубокий анализ STL string | C++那些事
• Разбор вопросов собеседования про STL string | C++那些事
• Анализ исходников STL deque | C++那些事
• Оптимизация пустого базового класса EBO в STL | C++那些事
• Реализация хеш-таблицы своими руками | C++那些事
• Хеш-таблица STL hashtable | C++那些事
• Анализ исходников STL итераторов | C++那些事
• Анализ исходников STL list | C++那些事
• STL map и multimap | C++那些事

Комментарии