eXile 的专栏

posts - 6, comments - 13, trackbacks - 0, articles - 0

[ 深入STL ] std::vector 的指针特化

Posted on 2005-10-22 15:00 eXile 阅读(1099) 评论(3)  编辑 收藏 收藏至365Key

　为了高效使用std::vector，　我们有时候必须使用 std::vector<T*>，原因很多，为了支持多态，为了减小移动元素的代价，等等。使用不同类型的指针容器时，代码膨胀是必须要考虑 的问题。我们希望所有的指针容器能共享同一份实现代码，这可以通过模板特化实现。
　　首先想到的是 vector<void*>,　它如果能作为所有vector<T*>的基类，那剩下的问题就简单了。但是无法直接这样做，因为 void* 也是指针，它也试图利用vector<T*>实例化，所以你不能这样写：

  template <class T>
class vector<T*> : private std::vector<void*>
{
//...
};
　　编译器会抱怨这个程序不能通过编译。vector<long>是一个无奈的选择，你得这样写：
template <class T>
class vector<T*> : private std::vector<long>
{
//...
};
       大量的强制转换是需要的，但至少它可以运行。有没有更好的办法呢？Boost的disable_if手法显然可以帮助我们。它的定义很简单：
template <bool flag, typename T=void>
struct disable_if
{
    typedef T type;
};

template <typename T>
struct disable_if<true,T>
{
};
　　我们还需要一个工具类，以判断一个Ｔ类型是不是void, 它的定义同样简单：
template <class U,class V>
struct is_same
{
    static const bool  value = false ;
};
template <class U>
struct is_same<U,U>
{
    static const bool  value = true;
};
　　现在我们可以这样写：
template <class T>
class vector<T*,  typename disable_if<is_same<T,void>::value, std::allocator<T*> >::type>
            : private std::vector<void*>
{
//..
};
　ＯＫ，搞定了。如果希望使用特化的版本，加入这个实现文件的头文件，如果希望使用标准实现，去掉这个头文件就可以了。完整的程序如下：

namespace std{

template <class T>
class vector<T*,
            typename disable_if<is_same<T,void>::value,
            std::allocator<T*> >::type
            >
            : private std::vector<void*>
{
    typedef std::vector<void*>    base_t;
    typedef vector<T*>            self_t;   

public:
    typedef T                    element_type;
   
    typedef T*                    value_type;
    typedef value_type*            pointer;
    typedef const value_type*    const_pointer;
    typedef value_type*            iterator;
    typedef const value_type*    const_iterator;
    typedef value_type&            reference;
    typedef const value_type&    const_reference;
    typedef size_t                size_type;
    typedef ptrdiff_t            difference_type;
 
    typedef std::reverse_iterator<const_iterator>
                const_reverse_iterator;
    typedef std::reverse_iterator<iterator>
                reverse_iterator;
   
    typedef std::allocator<T*>    allocator_type;

public:
    allocator_type get_allocator() const
    { return allocator_type( base_t::get_allocator() ); }

    iterator begin()
    {    return iterator_cast(base_t::begin());    }
    const_iterator begin() const
    {    return iterator_cast(base_t::begin());    }
    iterator end()
    {    return iterator_cast(base_t::end());    }
    const_iterator end() const
    {    return iterator_cast(base_t::end());    }

    reverse_iterator rbegin()
    {    return reverse_iterator(end());    }
    const_reverse_iterator rbegin() const
    {    return const_reverse_iterator(end());    }
    reverse_iterator rend()
    {    return reverse_iterator(begin()); }
    const_reverse_iterator rend() const
    {    return const_reverse_iterator(begin());    }

    using base_t::size;
    using base_t::max_size;
    using base_t::capacity;
    using base_t::empty;
    using base_t::reserve;
    using base_t::pop_back;
    using base_t::resize;

    reference operator[](int index)
    {   
        ASSERT( index>=0 && index<size()) ;
        return reinterpret_cast<reference>(base_t::operator[](index));   
    }
    const_reference operator[](int index) const
    {   
        ASSERT( index>=0 && index<size()) ;
        return reinterpret_cast<const_reference>(base_t::operator[](index));   
    }

    vector() : base_t()    {}
    explicit vector(size_type n) : base_t(n)    { }
    vector(const self_t& rhs) : base_t(rhs)    {}

    self_t& operator=(const self_t& rhs)
    {
        base_t::operator=(rhs);
        return *this;
    }

    template <class _InputIterator>
    void assign(_InputIterator first, _InputIterator  last)
    {   
        base_t::assign(first,last);
    }

    reference front() { return *begin(); }
    const_reference front() const { return *begin(); }
    reference back() { return *(end() - 1); }
    const_reference back() const { return *(end() - 1); }

    void push_back(const_reference x)
    {    base_t::push_back(x);    }
     
    void swap(self_t& x)
    {    base_t::swap(x);    }

    iterator insert(iterator pos, const_reference x)
    {   
        return iterator_cast(base_t::insert(
                iterator_cast(pos),
                x) );
    }
    iterator insert(iterator pos)
    {    return this->insert(pos,0);     }

    template <class _InputIterator>
    void insert(iterator __pos, _InputIterator __first, _InputIterator __last)
    {   
        base_t::insert(iterator_cast(__pos),__first,__last);
    }

    void insert (iterator __pos, size_type __n,  const_reference x)
    {    base_t::insert(iterator_cast(__pos),__n,x);     }


    iterator erase(iterator pos)
    {
        return  iterator_cast( base_t::erase(iterator_cast(pos)) );
    }

    iterator erase(iterator first, iterator last)
    {   
        return iterator_cast(base_t::erase(
                    iterator_cast(first),
                    iterator_cast(last) ));
    }

private:
    iterator iterator_cast(typename base_t::iterator it) const
    {
        return iterator(&*it);
    }
    const_iterator iterator_cast(typename base_t::const_iterator it) const
    {
        return const_iterator(&*it);
    }
    typename base_t::iterator iterator_cast(iterator it) const
    {
        return &*it;
    }
    iterator iterator_cast(const_iterator it) const
    {
       return &*it;
    }
};

} // std

# re: [ 深入STL ] std::vector 的指针特化  回复   

2005-10-23 19:17 by Ninputer

不明白了，如果有vector<void*>的显式特化在先，那么
template <class T>
class vector<T*> : private std::vector<void*>

显然是可以通过编译的，因为void*的特化比T*的特化更适合void*。为什么不先显式特化出vector<void*>呢。

我还试验了一下，甚至不用显式特化，先显式实例化一下都可以
template <typename T> class SomeStruct{public: T x;};

template class SomeStruct<void*>;

template <typename T> class SomeStruct<T*> : public SomeStruct<void*>
{};

# re: [ 深入STL ] std::vector 的指针特化  回复   

2005-10-23 19:31 by Ninputer

晕了，即使什么都不做
template <class T>
class vector<T*> : private std::vector<void*>
{
//...
};

也能通过编译

# to: Niputer  回复   

2005-10-24 11:51 by eXile

对于你所说的情况, 我在手头的几个编译器上做了一下测试, 发现:
Intel C++ 8.1/9.0, g++ 3.2, BCB6 均编译失败，而 VC7.1 则通过了编译.
对于加不加 void* 的显式特化, 结果均是如此.
看来 VC7.1 对于模板的偏特化还挺智能的, 对于 SNAFE(替换失败非错误)技术显然支持得更好.