歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C++中vector的實現

注意幾點:

分配內存不要使用new和delete,因為new的同時就把對象構造了,而我們需要的是原始內存。所以應該使用標准庫提供的allocator類來實現內存的控制。當然也可以重載operator new操作符,因為二者都是使用malloc作為底層實現,所以直接采用malloc也可以。

對象的復制必須使用系統提供的uninitialized_fill和uninitialized_copy,因為我們無法手工調用構造函數。

對於C++中的對象,除了POD之外,使用memcpy系列的函數是絕對錯誤的。

myvector.h

#ifndef _VECTOR_H_
#define _VECTOR_H_
#include <stddef.h>
#include <algorithm>
#include <memory>

template <typename T>
class Vector
{
    public:
        typedef T *iterator;
        typedef const T *const_iterator;
        typedef size_t size_type;
        typedef T value_type;

        class reverse_iterator
        {
            public:
                reverse_iterator(iterator it = NULL):current_(it) {}
                iterator base() const { return current_; }

                reverse_iterator &operator++()//前置
                {
                    --current_;
                    return *this;
                }

                reverse_iterator operator++(int)//後置
                {
                    reverse_iterator temp(*this);
                    --current_;
                    return temp;
                }

                reverse_iterator &operator--()
                {
                    ++current_;
                    return *this;
                }

                reverse_iterator operator--(int)
                {
                    reverse_iterator temp(*this);
                    ++current_;
                    return temp;
                }

                T &operator*()
                {
                    iterator temp = current_;
                    return *--temp;
                }

                T *operator->() 
                {
                    iterator temp = current_;
                    return --temp;
                }

                friend bool operator==(const reverse_iterator &lhs,
                        const reverse_iterator &rhs)
                {
                    return lhs.current_ == rhs.current_;
                }
                friend bool operator!=(const reverse_iterator &lhs,
                        const reverse_iterator &rhs)
                {
                    return lhs.current_ != rhs.current_;
                }
            private:
                iterator current_;
        };

        Vector() { create(); }//無參構造函數
        explicit Vector(size_type n, const T &t = T()) { create(n, t); }
        Vector(const Vector &v) { create(v.begin(), v.end());}// 拷貝構造函數
        ~Vector() { uncreate();}

        Vector &operator=(const Vector &other);
        T &operator[] (size_type i) { return data_[i]; }
        const T &operator[] (size_type i) const {return data_[i]; }

        void push_back(const T &t);

        size_type size() const { return avail_ - data_;}
        size_type capacity()const { return limit_ - data_;}

        iterator begin() { return data_; }
        const_iterator begin() const {return data_;}
        iterator end() {return avail_;}
        const_iterator end() const { return avail_; }

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

        void swap(Vector &rhs)
        {
            std::swap(data_, rhs.data_);
            std::swap(avail_, rhs.avail_);
            std::swap(limit_, rhs.limit_);
        }
    private:
        iterator data_;//首元素
        iterator avail_;//末尾元素的下一個
        iterator limit_;

        std::allocator<T> alloc_;//內存分配器

        void create();
        void create(size_type, const T &);
        void create(const_iterator, const_iterator);

        void  uncreate();

        void grow();
        void uncheckAppend(const T &);
};

    template <typename T>
inline Vector<T> &Vector<T>::operator=(const Vector &rhs)
{
    if(this != rhs)
    {
        uncreate();//釋放原來的內存
        create(rhs.begin(), rhs.end());
    }
    return *this;
}

    template <typename T>
inline void Vector<T>::push_back(const T &t)
{
    if(avail_ == limit_)
    {
        grow();
    }
    uncheckAppend(t);
}

    template <typename T>
inline void Vector<T>::create()
{
    //分配空的數組
    data_ = avail_ = limit_ = 0;
}

    template <typename T>
inline void Vector<T>::create(size_type n, const T &val)
{
    //分配原始內存
    data_ = alloc_.allocate(n);
    limit_ = avail_ = data_ + n;
    //向原始內存填充元素
    std::uninitialized_fill(data_, limit_, val);
}

    template <typename T>
inline void Vector<T>::create(const_iterator i, const_iterator j)
{
    data_ = alloc_.allocate(j-i);
    limit_ = avail_ = std::uninitialized_copy(i, j, data_);
}

    template <typename T>
inline void Vector<T>::uncreate()
{
    if(data_)//逐個析構
    {
        iterator it = avail_;
        while(it != data_)
        {
            alloc_.destroy(--it);
        }
        alloc_.deallocate(data_, limit_ - data_ );//真正釋放內存
    }
    data_ = limit_ = avail_ = 0;//重置指針
}

    template <typename T>
inline void Vector<T>::grow()
{
    //內存變為2倍
    size_type new_size = std::max(2 * (limit_ - data_), std::ptrdiff_t(1));
    //分配原始內存
    iterator new_data = alloc_.allocate(new_size);
    //復制元素
    iterator new_avail = std::uninitialized_copy(data_, avail_, new_data);

    uncreate();//釋放以前內存

    data_ = new_data;
    avail_ = new_avail;
    limit_ = data_ + new_size;
}

    template <typename T>
inline void Vector<T>::uncheckAppend(const T &val)
{
    alloc_.construct(avail_++, val);
}

#endif /*VECTOR_H*/

test_main.cpp

#include "myvector.h"
#include <iostream>
#include <string>
using namespace std;

void print_reverse(Vector<string> &vec)
{
    cout << "reverse_iterator: " << endl;
    for(Vector<string>::reverse_iterator it = vec.rbegin();
            it != vec.rend();
            ++it)
    {
        cout << *it << endl;   
    }
    cout << endl;
}

void print(Vector<string> &vec)
{
    cout << "iterator: " << endl;
    for(Vector<string>::iterator it = vec.begin();
            it != vec.end();
            ++it)
    {
        cout << *it << endl;   
    }
    cout << endl;
}

int main(int argc, const char *argv[])
{
    Vector<string> vec(3, "hello");

    for(Vector<string>::const_iterator it = vec.begin();
        it != vec.end();
        ++it)
    {
        cout << *it << endl;   
    }
  cout << endl;
 
    cout << "size=" << vec.size() << endl;
    cout << "capacity:" << vec.capacity() << endl;
    vec.push_back("foo");
    vec.push_back("bar");

    cout << "size:=" << vec.size() << endl;
    cout << "capacity=" << vec.capacity() << endl;
 
  print_reverse(vec);
  print(vec);
    return 0;
}

C++ 設計新思維》 下載見 http://www.linuxidc.com/Linux/2014-07/104850.htm

C++ Primer Plus 第6版 中文版 清晰有書簽PDF+源代碼 http://www.linuxidc.com/Linux/2014-05/101227.htm

讀C++ Primer 之構造函數陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm

讀C++ Primer 之智能指針 http://www.linuxidc.com/Linux/2011-08/40177.htm

讀C++ Primer 之句柄類 http://www.linuxidc.com/Linux/2011-08/40175.htm

將C語言梳理一下,分布在以下10個章節中:

  1. Linux-C成長之路(一):Linux下C編程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
  2. Linux-C成長之路(二):基本數據類型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
  3. Linux-C成長之路(三):基本IO函數操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
  4. Linux-C成長之路(四):運算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
  5. Linux-C成長之路(五):控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
  6. Linux-C成長之路(六):函數要義 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
  7. Linux-C成長之路(七):數組與指針 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
  8. Linux-C成長之路(八):存儲類,動態內存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
  9. Linux-C成長之路(九):復合數據類型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
  10. Linux-C成長之路(十):其他高級議題

Copyright © Linux教程網 All Rights Reserved