I'm trying to implement some STL containers as an exercise.
I have implemented a red-black-tree that takes as template parameter the type of the Key that the nodes will store. This has been enough to implement a set, but now that I'm trying to implement a map, I need the red-black-tree to store key and value.
I've seen the implementation for the std::set and std::map in the GNU docs and both use the same stl_tree.h file. That red-black tree implementation uses a _Key and _Val as template parameters:
00326 template<typename _Key, typename _Val, typename _KeyOfValue,
00327 typename _Compare, typename _Alloc = allocator<_Val> >
00328 class _Rb_tree
00329 {
00330 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
00331 _Node_allocator;
00332
00333 protected:
00334 typedef _Rb_tree_node_base* _Base_ptr;
00335 typedef const _Rb_tree_node_base* _Const_Base_ptr;
00336 typedef _Rb_tree_node<_Val> _Rb_tree_node;
00337
00338 public:
00339 typedef _Key key_type;
00340 typedef _Val value_type;
00341 typedef value_type* pointer;
from: https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/stl__tree_8h-source.html
However, the std::set implementation just stores a Key and uses a typedef to define value_type as _Key.
00106 template<class _Key, class _Compare, class _Alloc>
00107 class set
00108 {
00109 // concept requirements
00110 typedef typename _Alloc::value_type _Alloc_value_type;
00111 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
00112 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
00113 _BinaryFunctionConcept)
00114 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
00115
00116 public:
00117 // typedefs:
00118 //@{
00119 /// Public typedefs.
00120 typedef _Key key_type;
00121 typedef _Key value_type;
00122 typedef _Compare key_compare;
00123 typedef _Compare value_compare;
00124 typedef _Alloc allocator_type;
00125 //@}
00126
00127 private:
00128 typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
00129
00130 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
00131 key_compare, _Key_alloc_type> _Rep_type;
00132 _Rep_type _M_t; // red-black tree representing set
from: https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/stl__set_8h-source.html
(Also map: https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/stl__map_8h-source.html)
That would be equivalent to _Rb_tree<key_type, key_type, ... . Does that mean that the std::set stores the same key two times?
I know I could just implement another red-black-tree whose nodes store a key and a value and change the find method to recive the key as parameter and return the value. That would be enough to implement a map at this moment, but now I'm curious about the real std implementation of the red-black-tree. How is this behaviour achieved?