符合 STL 标准的容器示例

• 下载源文件 - 20 Kb

引言

在网上或 C++ STL 书籍中很难找到关于如何实现完全符合 STL 标准的容器，以及如何使用类迭代器、分配器等方面的资料。因此，我创建了这个易于理解的示例，它应该大致展示所有内容。它将链表建模为 SGI 的 STL 实现中的 < slist >。此示例中没有异常处理，但应该很容易添加。

背景

你需要对 STL 的使用有一个基本的了解。

使用代码

首先，请查看 stl_boost/my_container.hpp 以及 stl_boost/_test/_my_container.cpp 测试示例。my_container.hpp 中的代码文档完善，旨在用作“自解释的工作示例”。希望很快能看到一些通用的 STL 容器... :-)

这里展示了代码中最有趣的部分

template < typename T, class A = std::allocator< T > >
class my_container 
{
public:
// -----------------------
// --- Typedefs PUBLIC ---
// -----------------------
typedef A                           allocator_type;
typedef typename A::value_type      value_type;
typedef typename A::reference       reference;
typedef typename A::const_reference const_reference;
typedef typename A::pointer         pointer;
typedef typename A::const_pointer   const_pointer;
typedef typename A::size_type       size_type;
typedef typename A::difference_type difference_type;

// ------------------------------------
// --- NodeType Inner Class PRIVATE ---
// ------------------------------------
private:
struct my_container_node
{
    // --- Typedefs ---
    typedef my_container_node                            node_value_type;
    typedef typename node_allocator::pointer             node_pointer;
    typedef typename node_allocator::const_pointer       node_const_pointer;
    typedef typename A::rebind< node_value_type >::other node_allocator;

    // --- Member data ---
    node_pointer m_pNext;
    T            m_Data;
};

// --------------------------------------
// --- Iterators Inner classes PUBLIC ---
// --------------------------------------
public:

/* Base iterator template class. Bsed on this two typedefs are made: one
 * for const_iterator and one for iterator. This way we make sure we only 
 * have to overload the iterator operators (like '++' '==' etc.) one 
 * place. */
template < bool bIsConst > class iterator_base
{
public:
    // --- Typedefs PUBLIC ---
    typedef typename std::forward_iterator_tag iterator_category;
    typedef typename A::value_type             value_type;
    typedef typename A::difference_type        difference_type;

    /// Select pointer or const_pointer to T.
    typedef typename tutils::select< bIsConst, const_pointer,
                        pointer >::result pointer;

    /// Select reference or const_reference to T.
    typedef typename tutils::select< bIsConst, const_reference,
                        reference >::result reference;

    /// Select node_pointer or node_const_pointer.
    typedef typename tutils::select< bIsConst, node_const_pointer,
                        node_pointer >::result node_pointer;
private:
    node_pointer get_node_pointer() { return m_pNode; }
    node_pointer m_pNode;
};


// --- ITERATOR TYPEDEFS ---

/* Iterator. Used to iterate through a container. This is the normal mutable 
 * iterator which allows modifying the pointed to object T.*/
typedef iterator_base< false > iterator;


/* Const iterator. Used to iterate through a container. Not able to modify 
 * the pointed to object T. */
typedef iterator_base< true > const_iterator;

// ------------------------------------------
// --- Constructors and destructor PUBLIC ---
// ------------------------------------------

/* Create with allocator. Construct empty container, allocator. */
explicit my_container(const allocator_type& alloc)
             : m_NodeAlloc(alloc), m_pFirst(0), m_pLast(0) {}


private:
// -------------------------------------------
// --- Create/destroy node methods PRIVATE ---
// -------------------------------------------

/* Create node.
 * We only allocate space for the node, but don't call the constructor for 
 * 'elem'. At least it seems like that's the way STL container classes do
 * it!*/
node_pointer create_node(const_reference elem)
{
    node_pointer pNode = m_NodeAlloc.allocate(1);// Allocate space for 1 node
    m_NodeAlloc.construct(pNode, node_value_type(elem));
    return pNode;
}

/** Delete node.*/
void    delete_node(node_pointer pNode)
{
    m_NodeAlloc.destroy(pNode);
    m_NodeAlloc.deallocate(pNode, 1);  // De-allocate space for 1 node
}


// --------------------------------
// --- Member variables PRIVATE ---
// --------------------------------
node_allocator        m_NodeAlloc;    //< Allocator for the nodes.
node_pointer        m_pFirst;    //< Points to FIRST node in  list
node_pointer        m_pLast;    //< Points to LAST actual node in list
};