顺序容器（sequential container）

• 顺序容器为程序员提供了控制元素储存和访问顺序的能力。
• 这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

迭代器

• 提供对对象的间接访问。
• 使用迭代器可以访问某个元素，迭代器也能从一个元素移动到另外一个元素。
• 迭代器有 有效和无效之分，
• 有效的迭代器或指向某个元素，或指向容器中尾元素的下一位置。
• 其他情况都属于无效。

使用

• begin(): 负责返回指向第一个元素
• end():负责返回只想最后一个元素的下一个位置。也就是说，该迭代器指向的是容器一个本不存在的“尾后”（off the end）元素。
• 特殊情况下，如果容器为空，则begin和end返回的是同一个迭代器。都是尾后迭代器。

vector

特点

• 可变大小数组。
• 支持快速随机访问。
• 在尾部之外的位置插入或删除元素可能很慢。

函数接口

使用

代码：

int main()
{
    vector<int>::iterator it;
    vector<int> v1;

    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);

    for (auto it = v1.begin(); it != v1.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    v1.pop_back();
    v1.pop_back();
    v1.pop_back();

    for (auto it = v1.begin(); it != v1.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    it = v1.begin();
    it = v1.insert(it, 100);

    for (it = v1.begin(); it != v1.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    v1.push_back(12);
    v1.push_back(13);
    v1.push_back(14);
    v1.push_back(15);

    for (it = v1.begin(); it != v1.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    it = v1.begin();
    v1.erase(it + 3);

    for (it = v1.begin(); it != v1.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    vector<int> v2(3, 30);
    vector<int> v3(6, 60);

    for (it = v2.begin(); it != v2.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    for (it = v3.begin(); it != v3.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    v2.swap(v3);
    for (it = v2.begin(); it != v2.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    for (it = v3.begin(); it != v3.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    getchar();
    return 0;
}

运行结果：

实现

代码：

#include<iostream>
#include<vector>
#include<list>
#include<assert.h>

using namespace std;

template<class T>
class MyVector
{
public:
    MyVector()
        :_data(NULL)
        , _size(0)
        , _capacity(0)
    {}

    MyVector(const MyVector<T> &s)
    {
        _data = new T[s._size];
        for (size_t i = 0; i < _size; ++i)
        {
            _data[i] = s._data[i];
        }
        _size = s._size;
        _capacity = s._capacity;
    }

    ~MyVector()
    {
        if (_data)
        {
            delete[] _data;
            _data = NULL;
            _size = 0;
            _capacity = 0;
        }
    }

    void PushBack(const T& data)
    {
        CheckCapacity();
        _data[_size++] = data;
    }

    void PopBack()
    {
        assert(_size);
        --_size;
    }

    void Insert(size_t n, const T& data)
    {
        assert(n < _size);
        CheckCapacity();
        T cur = _size - 1;
        for (size_t i = n; i <_size; ++i)
        {
            _data[cur+1] = _data[cur];
            cur--;
        }
        _data[n] = data;
        ++_size;
    }

    void Erase(size_t n)
    {
        assert(n < _size);
        for (size_t i = n-1; i < _size; ++i)
        {
            _data[i] = _data[i + 1];
        }
        --_size;
    }

    void CheckCapacity()
    {
        if (_size == _capacity)
        {
            size_t NewCapacity =_capacity * 2 + 3;
            T* pData = new T[NewCapacity];

            for (size_t i = 0; i < _size; ++i)
            {
                pData[i] = _data[i];
            }

            delete[] _data;
            _data = pData;
            _capacity = NewCapacity;
        }
    }

    void Print()
    {
        assert(_size);
        for (size_t i = 0; i < _size; ++i)
        {
            cout << _data[i] << " ";
        }
        cout << endl;
    }

    void clear()
    {
        _size = 0;
    }

    void Swap(MyVector<T> v)
    {
        swap(_data, v._data);
        swap(_size, v._size);
        swap(_capacity, v._capacity);
    }

    T& operator[](size_t pos)
    {
        assert(pos<_size);
        return _data[pos];
    }

    size_t Size()
    {
        return _size;
    }

    size_t Capacity()
    {
        return _capacity;
    }

    bool Empty()
    {
        return (_size == 0);
    }
private:
    T* _data;
    size_t _size;
    size_t _capacity;
};

测试代码：

int main()
{
    MyVector<int> v1;
    v1.PushBack(1);
    v1.PushBack(2);
    v1.PushBack(3);
    v1.PushBack(4);
    v1.Print();

    v1.PopBack();
    v1.PopBack();
    v1.Print();

    v1.Insert(1, 2);
    v1.Insert(1, 2);
    v1.Insert(1, 2);
    v1.Print();

    v1.Erase(1);
    v1.Erase(1);
    v1.Erase(1);

    v1.Print();


    getchar();
    return 0;
}

运行结果：

list

特点

• 双向链表。
• 只支持双向顺序访问。
• 在list中任何位置进行插入/删除操作速度都很快。

函数接口

使用

代码：

int main()
{
    list<int> l1;
    list<int>::iterator it;

    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_back(4);

    for (auto it = l1.begin(); it != l1.end();++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    l1.pop_front();
    l1.pop_front();


    for (auto it = l1.begin(); it != l1.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    it = l1.begin();
    ++it;

    l1.insert(it, 10);
    l1.insert(it, 3, 30);

    for (auto it = l1.begin(); it != l1.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    it = l1.begin();
    advance(it,3);
    l1.erase(it);

    for (auto it = l1.begin(); it != l1.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    list<int> l2(3, 12);
    list<int> l3(5, 16);

    for (auto it = l2.begin(); it != l2.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
    for (auto it = l3.begin(); it != l3.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    l2.swap(l3);
    for (auto it = l2.begin(); it != l2.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
    for (auto it = l3.begin(); it != l3.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    getchar();
    return 0;
}

运行结果：

实现

代码：

#include<iostream>
#include<vector>
#include<list>
#include<assert.h>

using namespace std;

template<class T>
struct ListNode
{
    ListNode(const T& data = T())
    :_pre(NULL)
    , _next(NULL)
    , _data(data)
    {}

    ListNode<T>* _pre;
    ListNode<T>* _next;
    T _data;
};

//迭代器
template<class T, class Ref>
class ListIterator
{
    template<class T>//声明友元函数类
    friend class MyList;

    typedef ListIterator<T, Ref> self;
public:
    ListIterator()
        :_pNode(NULL)
    {}

    ListIterator(ListNode<T>* pNode)
        :_pNode(pNode)
    {}

    Ref operator*()
    {
        return _pNode->_data;
    }

    self& operator++()
    {
        _pNode = _pNode->_next;
        return *this;
    }

    self operator++(int)//后置
    {
        self tmp(*this);
        _pNode = _pNode->_next;
        return tmp;
    }

    self operator--()
    {
        _pNode = _pNode->_pre;
        return *this;
    }

    self& operator--(int)//后置
    {
        self tmp(*this);
        _pNode = _pNode->_pre;
        return tmp;
    }

    bool operator == (const self& s)
    {
        return _pNode == s._pNode;
    }

    bool operator != (const self& s)
    {
        return _pNode != s._pNode;
    }

private:
    ListNode<T>* _pNode;

};

template<class T>
class MyList
{
public:
    typedef ListIterator<T, T&> Iterator;

public:
    Iterator begin()
    {
        return Iterator(_pHead->_next);
    }

    Iterator end()
    {
        return Iterator(_pHead);
    }

    /*Iterator Find(const T& data)
    {
        ListNode<T>* pCur = _pHead->_next;
        while (pCur != _pHead)
        {
            if (data == pCur->_data)
                return Iterator(pCur);
            pCur = pCur->_next;
        }
    }*/

    MyList()
    {
        CreateHead();
    }

    MyList(size_t n, const T& data)
    {
        CreateHead();
        for (size_t = i; i < n; ++i)
        {
            PushBack(data);
        }
    }

    ~MyList()
    {
        Clear();
        delete _pHead;
        _pHead = NULL;
    }

    void Clear()
    {
        ListNode<T>* pCur = _pHead->_next;
        ListNode<T>* pPre = NULL;

        while (pCur != _pHead)
        {
            pPre = pCur;
            pCur = pCur->_next;
            delete pPre;
        }

        _pHead->_next = _pHead;
        _pHead->_pre = _pHead;

    }

    void PushBack(const T& data)
    {
        ListNode<T>* pTail = _pHead->_pre;
        ListNode<T>* pTmp = new ListNode<T>(data);
        pTail->_next = pTmp;
        pTmp->_next = _pHead;
        pTmp->_pre = pTail;
        _pHead->_pre = pTmp;
    }

    void PopBack()
    {
        if (_pHead == _pHead->_next)
        {
            assert(false);
            return;
        }

        ListNode<T>* pTmp = _pHead->_pre;
        pTmp->_pre->_next = _pHead;
        _pHead->_pre = pTmp->_pre;
        delete pTmp;
    }

    void PushFront(const T& data)
    {
        ListNode<T>* pTmp = _pHead->_next;
        ListNode<T>* pNew = new ListNode<T>(data);

        _pHead->_next = pNew;
        pNew->_next = pTmp;
        pTmp->_pre = pNew;
        pNew->_pre = _pHead;
    }

    void PopFront()
    {
        ListNode<T>* pTmp = _pHead->_next;
        _pHead->_next = pTmp->_next;
        pTmp->_next->_pre = _pHead;
        delete pTmp;
    }

    void Insert(const Iterator position, const T& data)
    {
        ListNode<T>* pTmp = _pHead->_next;

        while (pTmp != _pHead)
        {
            if (pTmp->_data == data)
                break;
            pTmp = pTmp->_next;
        }

        ListNode<T>* pNew = new ListNode<T>(data);
        pNew->_next = pTmp->_next;
        pNew->_pre = pTmp;
        pTmp->_next = pNew;
    }

    void Erase(const Iterator position)
    {
        ListNode<T>* pCur = _pHead->_next;

        while (pCur != _pHead)
        {
            if (pCur == position._pNode)
            {
                break;
            }
            pCur = pCur->_next;
        }

        pCur->_pre->_next = pCur->_next;
        pCur->_next->_pre = pCur->_pre;
        delete pCur;
    }

    bool Empty()
    {
        return _pNext->next == _pHead;
    }

    size_t Size() const
    {
        size_t count = 0;
        ListNode<T>* pCur = _pHead->_next;
        while (pCur != _pHead)
        {
            pCur = pCur->_next;
            count++;
        }
        return count;
    }

    void Print()
    {
        ListNode<T>* pTmp = _pHead->_next;
        while (pTmp != _pHead)
        {
            cout <<pTmp->_data<<" ";
            pTmp = pTmp->_next;
        }
        cout << endl;
    }

protected:
    void CreateHead()
    {
        _pHead = new ListNode<T>;
        _pHead->_next = _pHead;
        _pHead->_pre = _pHead;
    }
private:
    ListNode<T>* _pHead;
};

测试代码：

int main()
{
    MyList<int> l1;
    l1.PushBack(1);
    l1.PushBack(2);
    l1.PushBack(3);
    l1.PushBack(4);
    l1.Print();



    l1.PopBack();
    l1.PopBack();
    l1.Print();

    l1.PushFront(10);
    l1.PushFront(20);
    l1.PushFront(30);
    l1.Print();

    l1.PopFront();
    l1.PopFront();
    l1.PopFront();
    l1.PopBack();
    l1.PopBack();

    l1.Print();

    l1.PushBack(10);
    l1.PushBack(20);
    l1.PushBack(30);

    MyList<int>::Iterator it;
    //for (auto it = l1.begin(); it != l1.end(); ++it)
    //{
    //cout << *it << " ";
    //}
    //cout << endl;

    it = l1.begin();
    it++;

    l1.Insert(it, 2);
    l1.Print();

    it = l1.begin();

    l1.Erase(it);
    l1.Print();

    getchar();
    return 0;
}

运行结果：