相关文章推荐
小百科  ›  std::list 简述及其用到 - 千秋 - 博客园
博客园 list iterator cout
空虚的显示器
2 年前 
template <class T, class Alloc = allocator<T> > class list;

list是一种序列容器，它允许在序列中的任意位置进行常数时间的插入和删除操作，并可以在两个方向上进行迭代（遍历）。

list容器是基于双链表实现的，可以将其包含的每个元素存储在不同且不相关的存储位置上。通过链接到前一个元素和后一个元素的每个元素的关联关系在链表内部保持顺序。

list与forward_list非常相似：主要的区别是forward_list对象是单向链表，因此只能单向（forward）迭代（遍历），占用空间更小也更高效。

与其他基本的标准序列容器(array、vector和deque)相比，list在任何位置进行插入、获取和移动元素等操作方面都表现得更好，因此在使用这些操作的算法中也表现得更好，比如排序算法。

与其他序列容器相比，list和forward_list的主要缺点是它们无法使用元素位置对元素直接访问。例如，要访问list中的第6个元素，必须从已知位置(如开始或结束)遍历到该位置，需要花费的时间与这些位置之间的距离呈线性关系。它们还要消耗一些额外的内存来保存将每个元素关联起来的链接信息（也就是指针）。

顺序容器中的元素按照严格的线性顺序存储。各个元素通过使用它们在这个序列中的位置来访问。

每个元素都保存了如何定位下一个和前一个元素的信息，允许在特定元素之前或之后(甚至在整个范围内)进行常数时间的插入和删除操作，但不允许直接随机访问。

容器使用allocator对象来动态处理其存储需求。

元素的类型。

别名为成员类型 list :: value_type。

  • Alloc

    • 用于定义分配模型的分配器对象的类型。 默认情况下，使用allocator类模板，该模板定义最简单的内存分配模型，并且与值无关。

    别名为成员类型 list :: allocator_type。

    member typedefinitionnotes value_type The first template parameter ( T ) allocator_type The second template parameter ( Alloc ) defaults to: allocator<value_type> reference value_type& const_reference const value_type& pointer allocator_traits<allocator_type>::pointer for the default allocator: value_type* const_pointer allocator_traits<allocator_type>::const_pointer for the default allocator: const value_type* iterator a bidirectional iterator to value_type convertible to const_iterator const_iterator a bidirectional iterator to const value_type reverse_iterator reverse_iterator<iterator> const_reverse_iterator reverse_iterator<const_iterator> difference_type a signed integral type, identical to: iterator_traits<iterator>::difference_type usually the same as ptrdiff_t size_type an unsigned integral type that can represent any non-negative value of difference_type usually the same as size_t // constructors used in the same order as described above: std::list< int > first; // empty list of ints std::list< int > second ( 4 , 100 ); // four ints with value 100 std::list< int > third (second.begin(),second.end()); // iterating through second std::list< int > fourth (third); // a copy of third // the iterator constructor can also be used to construct from arrays: int myints[] = { 16 , 2 , 77 , 29 }; std::list < int > fifth (myints, myints + sizeof (myints) / sizeof ( int ) ); std::cout << " The contents of fifth are: " ; for (std::list< int >::iterator it = fifth.begin(); it != fifth.end(); it++ ) std::cout << *it << ' ' ; std::cout << ' \n ' ; return 0 ; Output: The contents of fifth are: 16 2 77 29 构造函数示例
  • (destructor) 析构函数 
    • ~list()
  • operator= 赋值
    • copy (1) 
    list& operator= (const list& x);
move (2)

    list& operator= (list&& x);
initializer list (3)

    list& operator= (initializer_list<value_type> il);
    
  std::list<int> first (3);      // list of 3 zero-initialized ints
  std::list<int> second (5);     // list of 5 zero-initialized ints
  second = first;
  first = std::list<int>();
  std::cout << "Size of first: " << int (first.size()) << '\n';
  std::cout << "Size of second: " << int (second.size()) << '\n';
  return 0;
Output:
Size of first: 0
Size of second: 3
    
crbegin 
const_reverse_iterator crbegin() const noexcept;
Return const_reverse_iterator to reverse beginning 
crend 
const_reverse_iterator crend() const noexcept;
Return const_reverse_iterator to reverse end 

     　　迭代器示例：
    

    #include <iostream>
#include <list>
int main ()
  int myints[] = {75,23,65,42,13};
  std::list<int> mylist (myints,myints+5);
  std::cout << "mylist contains:";
  for (std::list<int>::iterator it=mylist.begin(); it != mylist.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';
  return 0;
Output:
mylist contains: 75 23 65 42 13
    
迭代器示例

  •  容器大小或容量相关
    • 
  mylist.front() -= mylist.back();
  std::cout << "mylist.front() is now " << mylist.front() << '\n';
  return 0;
Output:
mylist.front() is now 55
-------------------------------------------------------------------------------
// list::back
#include <iostream>
#include <list>
int main ()
  std::list<int> mylist;
  mylist.push_back(10);
  while (mylist.back() != 0)
    mylist.push_back ( mylist.back() -1 );
  std::cout << "mylist contains:";
  for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end() ; ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';
  return 0;
Output:
mylist contains: 10 9 8 7 6 5 4 3 2 1 0
    成员访问示例
  • 添加、删除等修改相关操作
    • assign template <class InputIterator>
    void assign (InputIterator first, InputIterator last); Assign new content to container emplace template <class...   Args>
    iterator emplace (const_iterator position, Args&&... args); Construct and insert element first.assign ( 7 , 100 ); // 7 ints with value 100 second.assign (first.begin(),first.end()); // a copy of first int myints[]={ 1776 , 7 , 4 }; first.assign (myints,myints + 3 ); // assigning from array std::cout << " Size of first: " << int (first.size()) << ' \n ' ; std::cout << " Size of second: " << int (second.size()) << ' \n ' ; return 0 ; Output: Size of first: 3 Size of second: 7 ------------------------------------------------------------------------------ // list::emplace_front #include <iostream> #include <list> int main () std::list < std::pair< int , char > > mylist; mylist.emplace_front( 10 , ' a ' ); mylist.emplace_front( 20 , ' b ' ); mylist.emplace_front( 30 , ' c ' ); std::cout << " mylist contains: " ; for (auto& x: mylist) std::cout << " ( " << x.first << " , " << x.second << " ) " ; std::cout << std::endl; return 0 ; Output: mylist contains: ( 30 ,c) ( 20 ,b) ( 10 ,a) ------------------------------------------------------------------------------ // list::emplace_back #include <iostream> #include <list> int main () std::list < std::pair< int , char > > mylist; mylist.emplace_back( 10 , ' a ' ); mylist.emplace_back( 20 , ' b ' ); mylist.emplace_back( 30 , ' c ' ); std::cout << " mylist contains: " ; for (auto& x: mylist) std::cout << " ( " << x.first << " , " << x.second << " ) " ; std::cout << std::endl; return 0 ; Output: mylist contains: ( 10 ,a) ( 20 ,b) ( 30 ,c) ------------------------------------------------------------------------------ // list::push_front #include <iostream> #include <list> int main () std::list < int > mylist ( 2 , 100 ); // two ints with a value of 100 mylist.push_front ( 200 ); mylist.push_front ( 300 ); std::cout << " mylist contains: " ; for (std::list< int >::iterator it=mylist.begin(); it!=mylist.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; Output: 300 200 100 100 ------------------------------------------------------------------------------ // list::pop_front #include <iostream> #include <list> int main () std::list < int > mylist; mylist.push_back ( 100 ); mylist.push_back ( 200 ); mylist.push_back ( 300 ); std::cout << " Popping out the elements in mylist: " ; while (! mylist.empty()) std::cout << ' ' << mylist.front(); mylist.pop_front(); std::cout << " \nFinal size of mylist is " << mylist.size() << ' \n ' ; return 0 ; Output: Popping out the elements in mylist: 100 200 300 Final size of mylist is 0 ------------------------------------------------------------------------------ // list::push_back #include <iostream> #include <list> int main () std::list < int > mylist; int myint; std::cout << " Please enter some integers (enter 0 to end):\n " ; std::cin >> myint; mylist.push_back (myint); } while (myint); std::cout << " mylist stores " << mylist.size() << " numbers.\n " ; return 0 ; ------------------------------------------------------------------------------ // list::pop_back #include <iostream> #include <list> int main () std::list < int > mylist; int sum ( 0 ); mylist.push_back ( 100 ); mylist.push_back ( 200 ); mylist.push_back ( 300 ); while (! mylist.empty()) sum += mylist.back(); mylist.pop_back(); std::cout << " The elements of mylist summed " << sum << ' \n ' ; return 0 ; Output: The elements of mylist summed 600 ------------------------------------------------------------------------------ // list::emplace #include <iostream> #include <list> int main () std::list < std::pair< int , char > > mylist; mylist.emplace ( mylist.begin(), 100 , ' x ' ); mylist.emplace ( mylist.begin(), 200 , ' y ' ); std::cout << " mylist contains: " ; for (auto& x: mylist) std::cout << " ( " << x.first << " , " << x.second << " ) " ; std::cout << ' \n ' ; return 0 ; Output: mylist contains: ( 200 ,y) ( 100 ,x) ------------------------------------------------------------------------------ // inserting into a list #include <iostream> #include <list> #include <vector> int main () std::list < int > mylist; std::list < int > ::iterator it; // set some initial values: for ( int i= 1 ; i<= 5 ; ++i) mylist.push_back(i); // 1 2 3 4 5 it = mylist.begin(); ++it; // it points now to number 2 ^ mylist.insert (it, 10 ); // 1 10 2 3 4 5 // "it" still points to number 2 ^ mylist.insert (it, 2 , 20 ); // 1 10 20 20 2 3 4 5 --it; // it points now to the second 20 ^ std::vector< int > myvector ( 2 , 30 ); mylist.insert (it,myvector.begin(),myvector.end()); // 1 10 20 30 30 20 2 3 4 5 std::cout << " mylist contains: " ; for (it=mylist.begin(); it!=mylist.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; Output: mylist contains: 1 10 20 30 30 20 2 3 4 5 ------------------------------------------------------------------------------ // erasing from list #include <iostream> #include <list> int main () std::list < int > mylist; std::list < int > ::iterator it1,it2; // set some values: for ( int i= 1 ; i< 10 ; ++i) mylist.push_back(i* 10 ); // 10 20 30 40 50 60 70 80 90 it1 = it2 = mylist.begin(); // ^^ advance (it2, 6 ); // ^ ^ ++it1; // ^ ^ it1 = mylist.erase (it1); // 10 30 40 50 60 70 80 90 // ^ ^ it2 = mylist.erase (it2); // 10 30 40 50 60 80 90 // ^ ^ ++it1; // ^ ^ --it2; // ^ ^ mylist.erase (it1,it2); // 10 30 60 80 90 std::cout << " mylist contains: " ; for (it1=mylist.begin(); it1!=mylist.end(); ++ it1) std::cout << ' ' << * it1; std::cout << ' \n ' ; return 0 ; Output: mylist contains: 10 30 60 80 90 ------------------------------------------------------------------------------ // swap lists #include <iostream> #include <list> int main () std::list < int > first ( 3 , 100 ); // three ints with a value of 100 std::list< int > second ( 5 , 200 ); // five ints with a value of 200 first.swap(second); std::cout << " first contains: " ; for (std::list< int >::iterator it=first.begin(); it!=first.end(); it++ ) std::cout << ' ' << * it; std::cout << ' \n ' ; std::cout << " second contains: " ; for (std::list< int >::iterator it=second.begin(); it!=second.end(); it++ ) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; Output: first contains: 200 200 200 200 200 second contains: 100 100 100 ------------------------------------------------------------------------------ // resizing list #include <iostream> #include <list> int main () std::list < int > mylist; // set some initial content: for ( int i= 1 ; i< 10 ; ++ i) mylist.push_back(i); mylist.resize( 5 ); mylist.resize( 8 , 100 ); mylist.resize( 12 ); std::cout << " mylist contains: " ; for (std::list< int >::iterator it=mylist.begin(); it!=mylist.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; The code sets a sequence of 9 numbers as an initial content for mylist. It then uses resize first to set the container size to 5 , then to extend its size to 8 with values of 100 for its new elements, and finally it extends its size to 12 with their default values ( for int elements this is zero). Output: mylist contains: 1 2 3 4 5 100 100 100 0 0 0 0 ------------------------------------------------------------------------------ // clearing lists #include <iostream> #include <list> int main () std::list < int > mylist; std::list < int > ::iterator it; mylist.push_back ( 100 ); mylist.push_back ( 200 ); mylist.push_back ( 300 ); std::cout << " mylist contains: " ; for (it=mylist.begin(); it!=mylist.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; mylist.clear(); mylist.push_back ( 1101 ); mylist.push_back ( 2202 ); std::cout << " mylist contains: " ; for (it=mylist.begin(); it!=mylist.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; Output: mylist contains: 100 200 300 mylist contains: 1101 2202 splice void splice (const_iterator position, list& x);
    void splice (const_iterator position, list&& x); Transfer elements from list to list

    void splice (const_iterator position, list& x,
    const_iterator first,   const_iterator last);

    void splice (const_iterator position, list&& x,
    const_iterator first,   const_iterator last);

    template <class Predicate>
    void remove_if (Predicate pred);

    Remove elements fulfilling condition.

    Removes from the container all the elements for which Predicate pred returns true . This calls the destructor of these objects and reduces the container size by the number of elements removed.

    The function calls pred(*i) for each element (where i is an iterator to that element). Any of the elements in the list for which this returns true , are removed from the container.

    Remove duplicate values.

    The version with no parameters (1) , removes all but the first element from every consecutive group of equal elements in the container.

    Notice that an element is only removed from the list container if it compares equal to the element immediately preceding it. Thus, this function is especially useful for sorted lists.

    The second version (2) , takes as argument a specific comparison function that determine the "uniqueness" of an element. In fact, any behavior can be implemented (and not only an equality comparison), but notice that the function will call binary_pred(*i,*(i-1)) for all pairs of elements (where i is an iterator to an element, starting from the second) and remove i from the list if the predicate returns true .

    The elements removed are destroyed.

    Merge sorted lists.

    Merges x into the list by transferring all of its elements at their respective ordered positions into the container (both containers shall already be ordered).

    This function requires that the list containers have their elements already ordered by value (or by comp ) before the call.

    Assuming such ordering, each element of x is inserted at the position that corresponds to its value according to the strict weak ordering defined by operator< or comp . The resulting order of equivalent elements is stable (i.e., equivalent elements preserve the relative order they had before the call, and existing elements precede those equivalent inserted from x ).

    // set some initial values: for ( int i= 1 ; i<= 4 ; ++ i) mylist1.push_back(i); // mylist1: 1 2 3 4 for ( int i= 1 ; i<= 3 ; ++ i) mylist2.push_back(i * 10 ); // mylist2: 10 20 30 it = mylist1.begin(); ++it; // points to 2 mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4 // mylist2 (empty) // "it" still points to 2 (the 5th element) mylist2.splice (mylist2.begin(),mylist1, it); // mylist1: 1 10 20 30 3 4 // mylist2: 2 // "it" is now invalid. it = mylist1.begin(); std::advance(it, 3 ); // "it" points now to 30 mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end()); // mylist1: 30 3 4 1 10 20 std::cout << " mylist1 contains: " ; for (it=mylist1.begin(); it!=mylist1.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; std::cout << " mylist2 contains: " ; for (it=mylist2.begin(); it!=mylist2.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; Output: mylist1 contains: 30 3 4 1 10 20 mylist2 contains: 2 ------------------------------------------------------------------------------- // remove from list #include <iostream> #include <list> int main () int myints[]= { 17 , 89 , 7 , 14 }; std::list < int > mylist (myints,myints+ 4 ); mylist.remove( 89 ); std::cout << " mylist contains: " ; for (std::list< int >::iterator it=mylist.begin(); it!=mylist.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; Output: mylist contains: 17 7 14 ------------------------------------------------------------------------------- // list::remove_if #include <iostream> #include <list> // a predicate implemented as a function: bool single_digit ( const int & value) { return (value< 10 ); } // a predicate implemented as a class: struct is_odd { bool operator () ( const int & value) { return (value% 2 )== 1 ; } int main () int myints[]= { 15 , 36 , 7 , 17 , 20 , 39 , 4 , 1 }; std::list < int > mylist (myints,myints+ 8 ); // 15 36 7 17 20 39 4 1 mylist.remove_if (single_digit); // 15 36 17 20 39 mylist.remove_if (is_odd()); // 36 20 std::cout << " mylist contains: " ; for (std::list< int >::iterator it=mylist.begin(); it!=mylist.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; Output: mylist contains: 36 20 ------------------------------------------------------------------------------- // list::unique #include <iostream> #include <cmath> #include <list> // a binary predicate implemented as a function: bool same_integral_part ( double first, double second) { return ( int (first)== int (second) ); } // a binary predicate implemented as a class: struct is_near { bool operator () ( double first, double second) { return (fabs(first-second)< 5.0 ); } int main () double mydoubles[]={ 12.15 , 2.72 , 73.0 , 12.77 , 3.14 , 12.77 , 73.35 , 72.25 , 15.3 , 72.25 }; std::list < double > mylist (mydoubles,mydoubles+ 10 ); mylist.sort(); // 2.72, 3.14, 12.15, 12.77, 12.77, // 15.3, 72.25, 72.25, 73.0, 73.35 mylist.unique(); // 2.72, 3.14, 12.15, 12.77 // 15.3, 72.25, 73.0, 73.35 mylist.unique (same_integral_part); // 2.72, 3.14, 12.15 // 15.3, 72.25, 73.0 mylist.unique (is_near()); // 2.72, 12.15, 72.25 std::cout << " mylist contains: " ; for (std::list< double >::iterator it=mylist.begin(); it!=mylist.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; Output: mylist contains: 2.72 12.15 72.25 ------------------------------------------------------------------------------- // list::merge #include <iostream> #include <list> // compare only integral part: bool mycomparison ( double first, double second) { return ( int (first)< int (second) ); } int main () std::list < double > first, second; first.push_back ( 3.1 ); first.push_back ( 2.2 ); first.push_back ( 2.9 ); second.push_back ( 3.7 ); second.push_back ( 7.1 ); second.push_back ( 1.4 ); first.sort(); second.sort(); first.merge(second); // (second is now empty) second.push_back ( 2.1 ); first.merge(second,mycomparison); std::cout << " first contains: " ; for (std::list< double >::iterator it=first.begin(); it!=first.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; Output: first contains: 1.4 2.2 2.9 2.1 3.1 3.7 7.1 *Notice how in the second merger, the function mycomparison (which only compares the integral parts) did not consider 2.1 lower than 2.2 or 2.9 , so it was inserted right after them, before 3.1 . ------------------------------------------------------------------------------- // list::sort #include <iostream> #include <list> #include < string > #include <cctype> // comparison, not case sensitive. bool compare_nocase ( const std:: string & first, const std:: string & second) unsigned int i= 0 ; while ( (i<first.length()) && (i< second.length()) ) if (tolower(first[i])<tolower(second[i])) return true ; else if (tolower(first[i])>tolower(second[i])) return false ; ++ i; return ( first.length() < second.length() ); int main () std::list <std:: string > mylist; std::list <std:: string > ::iterator it; mylist.push_back ( " one " ); mylist.push_back ( " two " ); mylist.push_back ( " Three " ); mylist.sort(); std::cout << " mylist contains: " ; for (it=mylist.begin(); it!=mylist.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; mylist.sort(compare_nocase); std::cout << " mylist contains: " ; for (it=mylist.begin(); it!=mylist.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; Output: mylist contains: Three one two mylist contains: one Three two ------------------------------------------------------------------------------- // reversing list #include <iostream> #include <list> int main () std::list < int > mylist; for ( int i= 1 ; i< 10 ; ++ i) mylist.push_back(i); mylist.reverse(); std::cout << " mylist contains: " ; for (std::list< int >::iterator it=mylist.begin(); it!=mylist.end(); ++ it) std::cout << ' ' << * it; std::cout << ' \n ' ; return 0 ; Output: mylist contains: 9 8 7 6 5 4 3 2 1
  • allocator
    • relational operators (list) template <class T, class   Alloc>
    bool operator== (const   list<T,Alloc>& lhs, const list<T,Alloc>& rhs); Relational operators for list swap(list) template <class T, class   Alloc>
    void swap (list<T,Alloc>&   x, list<T,Alloc>& y); Exchanges the contents of two lists
     
    推荐文章
    Link管理   ·   Sov5搜索   ·   小百科
    小百科 - 百科知识指南