13-STL Container list

[Pin-Jiun]

List串列

為使用雙鍊結串列(double linked list)資料結構設計而成的容器。(They are very similar to forward_list) 每個元素有其相對應的Node，節點之中儲存元素的值，還有兩個指標：指向上一個節點的記憶位址、下一個節點的記憶位址。 在呼叫串列的某元素時，是從串列的第一個節點開始，一個節點一個節點的連接，因此無法用 串列名稱[n] 來呼叫序數為n的元素。 使用前預先 #include 即可 insert and erase operations O(1)

---

Member Function- Method

Iterator

begin() end() 回傳一個 iterator，它指向 vector 最尾端元素的下一個位置（請注意：它不是最末元素） rbegin() rend() cbegin() cend() crbegin() crend()

---

Capacity

empty() size() max_size

---

Element access

front() Returns a reference to the first element in the list container back() Returns a reference to the last element in the list container

 std::list<int> mylist;

  mylist.push_back(77);
  mylist.push_back(22);

  // now front equals 77, and back 22

  mylist.front() -= mylist.back();

  std::cout << "mylist.front() is now " << mylist.front() << '\n';      //55

---

Modifiers

assign()

  std::list<int> first;
  std::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

  std::cout << "Size of first: " << int (first.size()) << '\n';         //3
  std::cout << "Size of second: " << int (second.size()) << '\n';       //7
  return 0;

push_front() Inserts a new element at the beginning of the list

  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;    //300 200 100 100 

以及其他相關的pop_front() push_back() pop_back()

insert()

  list<int> mylist;
  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            ^

  vector<int> myvector (2,30);
  mylist.insert (it,myvector.begin(),myvector.end());
                                                // 1 10 20 30 30 20 2 3 4 5
                                                //               ^
  cout << "mylist contains:";
  for (it=mylist.begin(); it!=mylist.end(); ++it)
    cout << ' ' << *it;
  cout << '\n';

erase() Removes from the list container either a single element (position) or a range of elements ([first,last))

  list<int> mylist;
  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
                              //        ^

resize() 如果擴大,default是補0

  for (int i=1; i<10; ++i) mylist.push_back(i);

  mylist.resize(5);
  mylist.resize(8,100);
  mylist.resize(12);
//mylist contains: 1 2 3 4 5 100 100 100 0 0 0 0

clear()

---

Operations

splice() Transfer elements from list to list Transfers elements from x into the container, inserting them at position.

1. entire list void splice (const_iterator position, list& x)
2. single element void splice (const_iterator position, list& x, const_iterator i)
3. element range void splice (const_iterator position, list& x, const_iterator first, const_iterator last)

  list<int> mylist1, mylist2;
  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();
  advance(it,3);           // "it" points now to 30

  mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
                                // mylist1: 30 3 4 1 10 20

remove() Removes from the container all the elements that compare equal to val. void remove (const value_type& val);

  int myints[]= {17,89,7,14,89};
  list<int> mylist (myints,myints+5);

  mylist.remove(89); //mylist contains: 17 7 14

remove_if() removes from the container all the elements for which Predicate pred returns true template <class Predicate> void remove_if (Predicate pred); Parameters pred can either be a function pointer or a function object.

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

unique() Remove duplicate values

// remove from list
#include <iostream>
#include <cmath>
#include <list>

using namespace std;

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

merge() 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). void merge (list& x); template <class Compare> void merge (list& x, Compare comp);

// compare only integral part:
bool mycomparison (double first, double second)
{ return ( int(first)<int(second) ); }

int main ()
{
  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);              //first contains: 1.4 2.2 2.9 3.1 3.7 7.1
  // (second is now empty)

  second.push_back (2.1);

  first.merge(second,mycomparison); //first contains: 1.4 2.2 2.9 2.1 3.1 3.7 7.1
  return 0;

reverse() sort()

---

https://cplusplus.com/reference/list/list/ https://crmne0707.pixnet.net/blog/post/318559280-c%2B%2B-list