文章目錄

一. list介紹
二. list使用
- constructor
- iterator
- capacity
- - empty
  - size
- Element access
- - front/back
- Modifiers
- - assign
  - push_front/pop_front
  - push_back/pop_back
  - insert
  - erase
  - swap
  - resize
  - clear
- operations
- - splice
  - remove
  - remove_if
  - unique
  - sort
  - reverse

一. list介紹

list檔案介紹

1). list是可以在常數范圍內在任意位置進行插入和洗掉的序列式容器，并且該容器可以前后雙向迭代，
2). list的底層是雙向鏈表結構，雙向鏈表中每個元素存盤在互不相關的獨立節點中，在節點中通過指標指向其前一個元素和后一個元素，
3). list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝后迭代，已讓其更簡單高效，
4).與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進行插入、移除元素的執行效率更好，
5). 與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機訪問，比如：要訪問list的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時間開銷；list還需要一些額外的空間，以保存每個節點的相關聯資訊(對于存盤型別較小元素的大list來說這可能是一個重要的因素)

二. list使用

constructor

1).構造一個空容器

list<int> lt;

2).構造一個含有n個值為val的容器

list<int> lt(10,5);

3).拷貝構造

list<int> lt2(lt);

4). 迭代器區間構造

	int a[] = { 16,2,77,29 };
	list<int> lt2(a,a + 4);
	/*  while(first != last)
	*  {
	*		push_back(*first);
	*		++first;
	*  }
	*/
	print(lt2);
	// swap,find,reverse,sort 常用的演算法 <algorithm>
	// 原生指標可以看作天然的迭代器
	sort(a,a + 4);
	sort(a, a + 4, greater<int>());
	// sort排序底層是快速排序，迭代器型別只能是隨機迭代器
	// 比如三數取中優化，lt不支持隨機訪問
	sort(lt.begin(),lt.end());

在這里插入圖片描述

list迭代器是雙向迭代器，不支持 - 操作，因此報錯

這里順便介紹一下迭代器的型別 :
單向迭代器 : 只能向后依次遍歷(只支持++操作) (如 forward_list)
雙向迭代器 : 可以向前向后依次遍歷(支持++和–操作) (如 list)
隨機迭代器 : 可以向前向后隨機遍歷(支持++ /- - / + / - / += / -= 操作) (如 vector/string)

在這里插入圖片描述

iterator

在這里插入圖片描述

iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;

#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> lt(10, 5);
	//正向迭代器遍歷容器
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	// 反向迭代器遍歷容器
	list<int>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
	return 0;
}

capacity

empty

判斷容器是否為空

#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> lt; 
	cout << lt.empty() << endl; //1
	return 0;
}

size

獲取容器中的元素個數

#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	cout << lt.size() << endl; //4
	return 0;
}

Element access

front/back

front函式用于獲取list容器當中的第一個元素的參考，back函式用于獲取list容器當中的最后一個元素的參考

#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	cout << lt.front() << endl; //1
	cout << lt.back() << endl; //4
	return 0;
}

Modifiers

assign

將新內容賦值給list容器，替換其當前內容，并相應地修改其大小

1). 將n個值為val的資料分配給容器，
2). 將所給迭代器區間當中的內容分配給容器，

// list::assign
#include <iostream>
#include <list>
using namespace std;
int main ()
{
  	list<int> first;
  	list<int> second;
  	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

  	cout << "Size of first: " << int (first.size()) << endl; // 3
  	cout << "Size of second: " << int (second.size()) << endl; // 7
  	return 0;
}

push_front/pop_front

頭插，頭刪容器中的資料

#include <iostream>
#include <list>
using namespace std;
int main ()
{
  	list<int> mylist (2,100);         // two ints with a value of 100
  	mylist.push_front (200);
  	mylist.push_front (300);

 	cout << "mylist contains:";
  for (list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
    	cout << ' ' << *it;
  cout << endl;
  return 0;
  // output 
  // 300 200 100 100
}

#include <iostream>
#include <list>
using namespace std;
int main ()
{
  	list<int> mylist;
  	mylist.push_back (100);
  	mylist.push_back (200);
  	mylist.push_back (300);

  cout << "Popping out the elements in mylist:";
  while (!mylist.empty())
  {
    	cout << ' ' << mylist.front();
    	mylist.pop_front();
  }

  cout << "\nFinal size of mylist is " << mylist.size() << endl;

  return 0;
  // output
  // Popping out the elements in mylist: 100 200 300
  // Final size of mylist is 0
}

push_back/pop_back

尾插，尾刪容器中的資料

// 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";

  do {
    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
}

insert

1).在指定迭代器位置插入一個數，
2). 在指定迭代器位置插入n個值為val的數，
3).在指定迭代器位置插入一段迭代器區間（左閉右開），

// 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
}

#include <iostream>
#include <list>
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list<int>::iterator pos = find(lt.begin(),lt.end(),3);
	lt.insert(pos,30);
	print(lt);
	cout << *pos << endl; // 3
}

insert 不會導致迭代器失效，因為鏈表的插入并不會影響 it/pos 所指向的位置

erase

1).洗掉指定迭代器位置的元素，
2). 洗掉指定迭代器區間（左閉右開）的所有元素，

// 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
                             //        ^
// it1 已經失效
  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
}

#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list<int>::iterator pos = find(lt.begin(), lt.end(), 3);
	// pos迭代器失效
	lt.erase(pos);
	print(lt);
	cout << *pos << endl;
}

erase 會導致迭代器失效，因為鏈表的洗掉會使 pos 所指向的位置被釋放，從而 pos 成為野指標

swap

swap用于交換兩個容器的內容

// 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 
}

resize

1). 若 n 小于當前容器的 size ，size 減少到 n
2). 若 n 大于當前容器的 size，尾插入資料直到 n，值用 val 來填充

// 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;
  // output
  // mylist contains: 1 2 3 4 5 100 100 100 0 0 0 0
}

clear

清空容器，使容器的 size 成為 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
}

operations

splice

splice函式用于兩個list容器資料之間的轉移，其有三種拼接方式：

1).將整個容器拼接到另一個容器的指定迭代器位置，
2).將容器當中的某一個資料拼接到另一個容器的指定迭代器位置，
3).將容器指定迭代器區間的資料拼接到另一個容器的指定迭代器位置，

// splicing lists
#include <iostream>
#include <list>
int main ()
{
  std::list<int> mylist1, mylist2;
  std::list<int>::iterator it;

  // 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

remove函式用于洗掉容器當中被指定的元素，和erase不同，erase是洗掉迭代器位置的值

// 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
}

remove_if

remove_if函式用于洗掉容器當中滿足條件的元素，

// 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
}

unique

unique函式用于洗掉容器當中連續的重復元素(配合sort使用)，

// 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;
  // mylist contains: 2.72 12.15 72.25
}

sort

sort 默認將容器中的資料排成升序，排降序可以用 greater<>

// 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;
 // mylist contains: Three one two
//  mylist contains: one Three two
}

reverse

reverse函式用于將容器當中元素的位置進行逆置，

// 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;
  // mylist contains: 9 8 7 6 5 4 3 2 1
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/293729.html

標籤：其他

上一篇：資料結構鏈表曲二，曲三

下一篇：??快到七夕了，某小學妹找我聊天，原因竟然因為這，趕快收藏加一手關注??

list介紹和基本使用

文章目錄

一. list介紹

二. list使用

constructor

iterator

capacity

empty

size

Element access

front/back

Modifiers

assign

push_front/pop_front

push_back/pop_back

insert

erase

swap

resize

clear

operations

splice

remove

remove_if

unique

sort

reverse