第31章 C++ STL

STL

写道

The C++ STL (Standard Template Library) is a generic collection of class templates and
algorithms that allow programmers to easily implement standard data structures like
queues, lists, and stacks.

 

Iterator 

STL中所有提供的集合类模板都提供一种遍历访问的方式，即遍历器，这是一种很方便的遍历集合中元素的设计模式。

 

这这些集合类模板中，和Iterator使用有关的两个重要的方法就是begin()和end()。和这两个方法类似的还有cbegin()和cend()，以及rbegin()和rend()。这些方法都返回一个对应的Iterator。

 

其中，cbegin()和cend()，和begin()以及end()不一样的是，它们返回一个const_iterator。而rbegin()和rend()返回一个reverse_iterator。

 

不同的集合类模板返回的Iterator也不一样，如list和map返回的Iterator定义也不一样。

 

list

 

构造函数

    list()

        noexcept(is_nothrow_default_constructible<allocator_type>::value);

    explicit list(const allocator_type& a);

 

    explicit list(size_type n);

    explicit list(size_type n, const allocator_type& a); // C++14

 

    list(size_type n, const value_type& value);

    list(size_type n, const value_type& value, const allocator_type& a);

 

    template <class Iter>

        list(Iter first, Iter last);

    template <class Iter>

        list(Iter first, Iter last, const allocator_type& a);

 

    list(const list& x);

    list(const list&, const allocator_type& a);

 

    list(list&& x)

        noexcept(is_nothrow_move_constructible<allocator_type>::value);

    list(list&&, const allocator_type& a);

 

    list(initializer_list<value_type>);

    list(initializer_list<value_type>, const allocator_type& a);

 

 

std::list<int> list;

 

std::list<int> list2(5);

 

std::list<int> list2(5, 10);

 

std::list<int> list2(5, 10);

std::list<int> list3(list2.begin(), list2.end());

 

std::list<int> list2(5, 10);

std::list<int> list4(list2);

 

std::list<int> list2(5, 10);

std::list<int> list5(std::move(list2));

 

int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

std::list<int> list6(a, a + 10);

 

  std::list<int> list;

  list.assign(10, 10);

 

  std::list<int> list;

  for (int i = 0; i < 10; i++)

  {

    list.push_back(10);

  }

 

  std::list<int> list;

  std::list<int>::iterator it;

 

  it = list.begin();

  for (int i = 0; i < 10; i++)

  {

    list.insert(it, i);

  }

 

遍历

  for (std::list<int>::iterator it = list.begin(); it != list.end(); it++)

  {

    std::cout<<*it<<std::endl;

  }

 

定义

 

template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
class _LIBCPP_TYPE_VIS_ONLY list
    : private __list_imp<_Tp, _Alloc>
{
    typedef __list_imp<_Tp, _Alloc> base;
    typedef typename base::__node              __node;
    typedef typename base::__node_allocator    __node_allocator;
    typedef typename base::__node_pointer      __node_pointer;
    typedef typename base::__node_alloc_traits __node_alloc_traits;
    typedef typename base::__node_base         __node_base;
    typedef typename base::__node_base_pointer __node_base_pointer;
    typedef typename base::__link_pointer __link_pointer;

public:
    typedef _Tp                                      value_type;
    typedef _Alloc                                   allocator_type;
    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
                  "Invalid allocator::value_type");
    typedef value_type&                              reference;
    typedef const value_type&                        const_reference;
    typedef typename base::pointer                   pointer;
    typedef typename base::const_pointer             const_pointer;
    typedef typename base::size_type                 size_type;
    typedef typename base::difference_type           difference_type;
    typedef typename base::iterator                  iterator;
    typedef typename base::const_iterator            const_iterator;
    typedef _VSTD::reverse_iterator<iterator>         reverse_iterator;
    typedef _VSTD::reverse_iterator<const_iterator>   const_reverse_iterator;

    _LIBCPP_INLINE_VISIBILITY
    list()
        _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
    {
#if _LIBCPP_DEBUG_LEVEL >= 2
        __get_db()->__insert_c(this);
#endif
    }
    _LIBCPP_INLINE_VISIBILITY
    explicit list(const allocator_type& __a) : base(__a)
    {
#if _LIBCPP_DEBUG_LEVEL >= 2
        __get_db()->__insert_c(this);
#endif
    }
    explicit list(size_type __n);
#if _LIBCPP_STD_VER > 11
    explicit list(size_type __n, const allocator_type& __a);
#endif
    list(size_type __n, const value_type& __x);
    list(size_type __n, const value_type& __x, const allocator_type& __a);
    template <class _InpIter>
        list(_InpIter __f, _InpIter __l,
             typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
    template <class _InpIter>
        list(_InpIter __f, _InpIter __l, const allocator_type& __a,
             typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);

    list(const list& __c);
    list(const list& __c, const allocator_type& __a);
    list& operator=(const list& __c);
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
    list(initializer_list<value_type> __il);
    list(initializer_list<value_type> __il, const allocator_type& __a);
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
    list(list&& __c)
        _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
    list(list&& __c, const allocator_type& __a);
    list& operator=(list&& __c)
        _NOEXCEPT_(
            __node_alloc_traits::propagate_on_container_move_assignment::value &&
            is_nothrow_move_assignable<__node_allocator>::value);
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
    _LIBCPP_INLINE_VISIBILITY
    list& operator=(initializer_list<value_type> __il)
        {assign(__il.begin(), __il.end()); return *this;}
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    template <class _InpIter>
        void assign(_InpIter __f, _InpIter __l,
             typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
    void assign(size_type __n, const value_type& __x);
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
    _LIBCPP_INLINE_VISIBILITY
    void assign(initializer_list<value_type> __il)
        {assign(__il.begin(), __il.end());}
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    allocator_type get_allocator() const _NOEXCEPT;

    _LIBCPP_INLINE_VISIBILITY
    size_type size() const _NOEXCEPT     {return base::__sz();}
    _LIBCPP_INLINE_VISIBILITY
    bool empty() const _NOEXCEPT         {return base::empty();}
    _LIBCPP_INLINE_VISIBILITY
    size_type max_size() const _NOEXCEPT
        {return numeric_limits<difference_type>::max();}

    _LIBCPP_INLINE_VISIBILITY
          iterator begin() _NOEXCEPT        {return base::begin();}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator begin()  const _NOEXCEPT {return base::begin();}
    _LIBCPP_INLINE_VISIBILITY
          iterator end() _NOEXCEPT          {return base::end();}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator end()    const _NOEXCEPT {return base::end();}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator cbegin() const _NOEXCEPT {return base::begin();}
    _LIBCPP_INLINE_VISIBILITY
    const_iterator cend()   const _NOEXCEPT {return base::end();}

    _LIBCPP_INLINE_VISIBILITY
          reverse_iterator rbegin() _NOEXCEPT
            {return       reverse_iterator(end());}
    _LIBCPP_INLINE_VISIBILITY
    const_reverse_iterator rbegin()  const _NOEXCEPT
        {return const_reverse_iterator(end());}
    _LIBCPP_INLINE_VISIBILITY
          reverse_iterator rend() _NOEXCEPT
            {return       reverse_iterator(begin());}
    _LIBCPP_INLINE_VISIBILITY
    const_reverse_iterator rend()    const _NOEXCEPT
        {return const_reverse_iterator(begin());}
    _LIBCPP_INLINE_VISIBILITY
    const_reverse_iterator crbegin() const _NOEXCEPT
        {return const_reverse_iterator(end());}
    _LIBCPP_INLINE_VISIBILITY
    const_reverse_iterator crend()   const _NOEXCEPT
        {return const_reverse_iterator(begin());}

    _LIBCPP_INLINE_VISIBILITY
    reference front()
    {
        _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
        return base::__end_.__next_->__as_node()->__value_;
    }
    _LIBCPP_INLINE_VISIBILITY
    const_reference front() const
    {
        _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
        return base::__end_.__next_->__as_node()->__value_;
    }
    _LIBCPP_INLINE_VISIBILITY
    reference back()
    {
        _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
        return base::__end_.__prev_->__as_node()->__value_;
    }
    _LIBCPP_INLINE_VISIBILITY
    const_reference back() const
    {
        _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
        return base::__end_.__prev_->__as_node()->__value_;
    }

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
    void push_front(value_type&& __x);
    void push_back(value_type&& __x);
#ifndef _LIBCPP_HAS_NO_VARIADICS
    template <class... _Args>
       void emplace_front(_Args&&... __args);
    template <class... _Args>
        void emplace_back(_Args&&... __args);
    template <class... _Args>
        iterator emplace(const_iterator __p, _Args&&... __args);
#endif  // _LIBCPP_HAS_NO_VARIADICS
    iterator insert(const_iterator __p, value_type&& __x);
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

    void push_front(const value_type& __x);
    void push_back(const value_type& __x);

    iterator insert(const_iterator __p, const value_type& __x);
    iterator insert(const_iterator __p, size_type __n, const value_type& __x);
    template <class _InpIter>
        iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,
             typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
    _LIBCPP_INLINE_VISIBILITY
    iterator insert(const_iterator __p, initializer_list<value_type> __il)
        {return insert(__p, __il.begin(), __il.end());}
#endif   // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY
    void swap(list& __c)
#if _LIBCPP_STD_VER >= 14
        _NOEXCEPT
#else
        _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
                   __is_nothrow_swappable<__node_allocator>::value)
#endif
        {base::swap(__c);}
    _LIBCPP_INLINE_VISIBILITY
    void clear() _NOEXCEPT {base::clear();}

    void pop_front();
    void pop_back();

    iterator erase(const_iterator __p);
    iterator erase(const_iterator __f, const_iterator __l);

    void resize(size_type __n);
    void resize(size_type __n, const value_type& __x);

    void splice(const_iterator __p, list& __c);
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
    _LIBCPP_INLINE_VISIBILITY
    void splice(const_iterator __p, list&& __c) {splice(__p, __c);}
#endif
    void splice(const_iterator __p, list& __c, const_iterator __i);
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
    _LIBCPP_INLINE_VISIBILITY
    void splice(const_iterator __p, list&& __c, const_iterator __i)
        {splice(__p, __c, __i);}
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
    void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
    _LIBCPP_INLINE_VISIBILITY
    void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l)
        {splice(__p, __c, __f, __l);}
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

    void remove(const value_type& __x);
    template <class _Pred> void remove_if(_Pred __pred);
    void unique();
    template <class _BinaryPred>
        void unique(_BinaryPred __binary_pred);
    void merge(list& __c);
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
    _LIBCPP_INLINE_VISIBILITY
    void merge(list&& __c) {merge(__c);}
#endif
    template <class _Comp>
        void merge(list& __c, _Comp __comp);
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
    template <class _Comp>
    _LIBCPP_INLINE_VISIBILITY
        void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
    void sort();
    template <class _Comp>
        void sort(_Comp __comp);

    void reverse() _NOEXCEPT;

    bool __invariants() const;

#if _LIBCPP_DEBUG_LEVEL >= 2

    bool __dereferenceable(const const_iterator* __i) const;
    bool __decrementable(const const_iterator* __i) const;
    bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;

#endif  // _LIBCPP_DEBUG_LEVEL >= 2

private:
    static void __link_nodes  (__link_pointer __p, __link_pointer __f, __link_pointer __l);
    void __link_nodes_at_front(__link_pointer __f, __link_pointer __l);
    void __link_nodes_at_back (__link_pointer __f, __link_pointer __l);
    iterator __iterator(size_type __n);
    template <class _Comp>
        static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);

    void __move_assign(list& __c, true_type)
        _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
    void __move_assign(list& __c, false_type);
};

map

  std::map<char*, int> map;

  map["key1"] = 1;

  map["key2"] = 2;

  map["key3"] = 3;

  map["key4"] = 4;

  map["key5"] = 5;

  map["key6"] = 6;

 

bool compare(char* left, char* right) 

{

  return strcmp(left, right);

}

 

  std::map<char *, int, bool (*) (char*, char*)> map2(compare);

  map2["key1"] = 10;

  map2["key2"] = 20;

  map2["key3"] = 30;

  map2["key4"] = 40;

  map2["key5"] = 50;

  map2["key6"] = 60;

 

struct compare_st

{

  bool operator() (char* left, char* right) const

  {

    return strcmp(left, right);

  }

};

 

  std::map<char *, int, compare_st> map3;

  map3["key1"] = 100;

  map3["key2"] = 200;

  map3["key3"] = 300;

  map3["key4"] = 400;

  map3["key5"] = 500;

  map3["key6"] = 600;

 

class Compare

{

  public: bool operator() (char* left, char* right) const

  {

    return strcmp(left, right);

  }

};

 

  std::map<char *, int, Compare> map4;

  map4["key1"] = 1000;

  map4["key2"] = 2000;

  map4["key3"] = 3000;

  map4["key4"] = 4000;

  map4["key5"] = 5000;

  map4["key6"] = 6000;

 

 

  std::map<char *, int> map1;

  map1["key1"] = 1;

  map1["key2"] = 2;

  map1["key3"] = 3;

  map1["key4"] = 4;

  map1["key5"] = 5;

  map1["key6"] = 6;

  std::map<char *, int> map5(map1.begin(), map1.end());

 

  std::map<char *, int> map1;

  map1["key1"] = 1;

  map1["key2"] = 2;

  map1["key3"] = 3;

  map1["key4"] = 4;

  map1["key5"] = 5;

  map1["key6"] = 6;

  std::map<char *, int, bool (*) (char*, char*)> map6(map1.begin(), map1.end(), compare);

 

  std::map<char *, int> map1;

  map1["key1"] = 1;

  map1["key2"] = 2;

  map1["key3"] = 3;

  map1["key4"] = 4;

  map1["key5"] = 5;

  map1["key6"] = 6;

  std::map<char *, int, compare_st> map7(map1.begin(), map1.end());

 

  std::map<char *, int> map1;

  map1["key1"] = 1;

  map1["key2"] = 2;

  map1["key3"] = 3;

  map1["key4"] = 4;

  map1["key5"] = 5;

  map1["key6"] = 6;

  std::map<char *, int, Compare> map8(map1.begin(), map1.end());

 

  std::map<char *, int> map1;

  map1["key1"] = 1;

  map1["key2"] = 2;

  map1["key3"] = 3;

  map1["key4"] = 4;

  map1["key5"] = 5;

  map1["key6"] = 6;

  std::map<char *, int> map6(map1);

 

  std::map<char *, int> map1;

  map1["key1"] = 1;

  map1["key2"] = 2;

  map1["key3"] = 3;

  map1["key4"] = 4;

  map1["key5"] = 5;

  map1["key6"] = 6;

std::map<char *, int> map10(std::move(map1));

 

遍历

  for (std::map<char *, int>::iterator it = map.begin(); it != map.end(); it++)

  {

    std::cout<<it->first<<"=>"<<it->second<<std::endl;

  }

队列

 

queue

 

  std::queue<int> queue1;

 

  for (int i = 0; i < 10; i++)

  {

    queue1.push(i);

  }

 

  while (! queue1.empty()) 

  {

    std::cout<<queue1.front()<<std::endl;

    queue1.pop();

  }

 

优先级队列

 

priority_queue

 

  std::priority_queue<int> queue1;

 

  for (int i = 0; i < 10; i++)

  {

    queue1.push(i);

  }

 

  while (! queue1.empty()) 

  {

    std::cout<<queue1.top()<<std::endl;

    queue1.pop();

  }