Last updated：2026-10-12
STL traits type extraction¶
0.Introduction¶
In STL programming, containers and algorithms are designed independently, that is, data structures and algorithms are designed separately; the bridge connecting containers and algorithms is the iterator, and iterators make this independent design possible. As shown in the figure below:
The figure above shows that the goal of the STL is to separate data from algorithms, design each of them independently, and then glue the two back together through something called an iterator.
In design patterns, iterator is described as: a way to access each element of a container sequentially without exposing the container's internal representation. And type extraction (traits) technology exists precisely to solve problems related to iterators.
To apply generic algorithms (find, count, find_if) to a container, the most important thing is to provide the algorithm with a tool for accessing the container's elements, and the iterator plays this important role.
Inside an algorithm we may need to define simple intermediate variables or set the type of the algorithm's return variable; at that point we need to know what the type of the element the iterator points to is. But since there is no typeof-like function for deducing types, we cannot obtain it directly — so what can be done? This article explains it in detail.
An iterator is a kind of smart pointer, and therefore it has all the characteristics of an ordinary pointer — you can apply * and -> operations to it. However, when traversing a container, it is unavoidable to know something about the container's internals, so it is simply better to leave the development of iterators to the container's designers. That way, all implementation details are encapsulated and hidden from users — which is exactly why every STL container provides its own dedicated iterators.
And Traits is in 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;
};
Looks totally baffling, right? No worries — after reading this section you'll have gotten started with the STL, haha~
1.template parameter deduction¶
First, when using iterators in algorithms, you will very likely need their associated types (the type of what the iterator points to). Suppose the algorithm needs to declare a variable whose type is "the type of the object the iterator points to" — what should we do?
The solution: use function template's parameter deduction mechanism.
For example:
If T is a pointer to some object, what do we do when func needs the type of the object the pointer points to? This one is fairly easy; the template's parameter deduction mechanism can do the job,
template <class I>
inline
void func(I iter) {
func_impl(iter, *iter); // 传入iter和iter所指的值，class自动推导
}
Through the template's deduction mechanism, we effortlessly obtain the type of the object the pointer points to.
template <class I, class T>
void func_impl(I iter, T t) {
T tmp; // 这里就是迭代器所指物的类别
// ... 功能实现
}
int main() {
int i;
func(&i);
}
However, what the function's "template parameter deduction mechanism" deduces are only parameters; it cannot deduce the function's return type. If the function's return type needs to be deduced, it is powerless. Therefore, we introduce the following method.
2.Declaring nested types¶
The type of the object an iterator points to is called the iterator's value type.
Although in func_impl we can use T as the function's return value, the problem is that what users need to call is 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
}
If you try to compile the code above, compilation fails!
This problem is not hard to solve either: declaring a nested type seems like a good idea, so that we can obtain it directly. Just make an iterator, and when defining it give an alias to the type of the object it points to — done, like this:
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
}
A very elegant solution; everything looks perfect. But in fact there is still a problem, because if func is a generic algorithm, it must absolutely also accept a native pointer as an iterator, yet clearly you cannot get the following code to compile:
Our func cannot support native pointers, which is clearly unacceptable. At this point, template partial specialization comes to the rescue.
3.The savior Traits¶
As mentioned earlier, if we use typename I::value_type directly, the algorithm cannot accept native pointers, because a native pointer simply has no nested type called value_type.
Therefore, we still need to add an intermediate layer to determine whether it is a native pointer — and note, this is exactly the beauty of the traits technique.
If we only use the approach above, i.e. the nested value_type, then for pointers without value_type we can only partially specialize — and it would be a partial specialization of the callable function func. If func had a million lines of code, this would cause enormous visual pollution.
(1) Function partial specialization
Function partial specialization:
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;
}
Output:
(2) Adding an intermediate layer
What is Traits in the STL? Look at the figure below:
Using an intermediate layer iterator_traits fixes the form of func, eliminating a large amount of duplicated code; the only thing left to do is slightly specialize iterator_tartis so that it supports pointer and 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;
}
The process above first asks iterator_traits<I>::value_type: if the passed-in I is a pointer, the specialized version is entered and iterator_traits answers directly with T; if the passed-in I is a class type, it goes on to ask T::value_type.
Put plainly: the algorithm (func) asks iterator_traits (me), but when iterator_traits (me) finds a pointer in hand, I answer on its behalf. If it is a class type, iterator_traits (me) keeps asking (him --- T::value_type).
Summary: by defining nested types, we gained a way to know the type of the element an iterator points to; through the traits technique, we unified the function template's definitions for native pointers and custom iterators. The main reason we use the traits technique is to resolve the code duplication caused by the differences between native pointers and custom iterators — this is exactly the beauty of the traits technique.
Study books:
侯捷《 STL 源码剖析》
Study articles:
https://juejin.im/post/5b1a43fb51882513bf1795c6
Related Topics¶
- STL array source code analysis | C++那些事
- STL string deep dive | C++那些事
- STL string interview questions in depth | C++那些事
- STL deque source code analysis | C++那些事
- STL empty base optimization EBO | C++那些事
- STL hand-written hash table implementation | C++那些事
- STL hashtable hash table | C++那些事
- STL iterator source code analysis | C++那些事
- STL list source code analysis | C++那些事
- STL map and multimap | C++那些事