C++_STL — list (and forward_list)

Reference: list forward_list

Class template

template < class T.class Alloc = allocator<T> > class list;
Copy the code

1.1 Container Properties

Container attribute
The sequence	The elements in a sequence container are sorted in a strict linear order. Individual elements are accessed by their position in the sequence.
Two-way linked list	Each element retains information about how to position the next and previous elements, allowing constant time inserts and erases before or after a particular element (or even the entire range), but no direct random access.
The allocator allocates memory dynamically	Containers use allocator objects to handle their storage needs dynamically.

1.2 Template Parameters

Template parameter
T	The type of the contained element.
Alloc	distributor

1.3 example

std::list<int> mylist;
Copy the code

constructors

C + + 11:

C + + 11:
default	explicit list (const allocator_type& alloc = allocator_type());
fill	explicit list (size_type n); list (size_type n, const value_type& val, const allocator_type& alloc = allocator_type());
range	template <class InputIterator> list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
copy	list (const list& x); list (const list& x, const allocator_type& alloc);
move	list (list&& x); list (list&& x, const allocator_type& alloc);
initializer list	list (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

Example:

// constructing lists
#include <iostream>
#include <list>

int main (a)
{
  // 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(a); it ! = fifth.end(a); it++) std::cout << *it <<' ';

  std::cout << '\n';

  return 0;
}
Copy the code

STD ::list:: Assign, back, begin, Cbegin, End, CEND, CRbegin, CREnd, Empty, clear, Rbegin, rend, size, emplace, POP_back, POP_front, PUS H_back, push_front, resize, swap, emplace_back, emplace_front, erase, front, INSERT, max_size, operator=

C++_STL — deque (C++11)

And this C++_ variadic template to emplace_back to construct to forward

Note that inserts are slightly different from deques in that iterators pointing to elements do not point to the newly inserted location as the element moves back, but to the previous element. Unlike other standard sequence containers, list and forward_list objects are designed to efficiently insert and delete elements anywhere, even in the middle of a sequence.

// inserting into a list
#include <iostream>
#include <list>
#include <vector>

int main (a)
{
  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(a); ++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
                                                / / ^
  std::cout << "mylist contains:";
  for (it=mylist.begin(a); it! =mylist.end(a); ++it) std::cout <<' ' << *it;
  std::cout << '\n';

  return 0;
}
Copy the code

4, STD: : list: : get_allocator

allocator_type get_allocator(a) const noexcept;
Copy the code

4.1 features

Returns a copy of the allocator object type associated with the list container.

4.2 the return value

The dispatcher. The member type allocator_type is the type of the allocator used by the container. It is the same type as the allocator used in the second argument, and does not affect the original container.

// list::get_allocator
#include <iostream>
#include <list>

int main (a)
{
  std::list<int> mylist;
  int * p;

  // allocate an array of 5 elements using mylist's allocator:
  p=mylist.get_allocator().allocate(5);

  // assign some values to array
  for (int i=0; i<5; ++i) p[i]=i;

  std::cout << "The allocated array contains:";
  for (int i=0; i<5; ++i) std::cout << ' ' << p[i];
  std::cout << '\n';
  
  std::cout <<mylist.size() < <'\n';

  mylist.get_allocator().deallocate(p,5);

  return 0;
}
Copy the code

5, STD: : array: : the merge

/ / (1)
  void merge (list& x);
  void merge (list&& x);
/ / (2)
template <class Compare>
  void merge (list& x, Compare comp);
template <class Compare>
  void merge (list&& x, Compare comp);
Copy the code

5.1 features

Merge X into the list by transferring all elements in their respective ordered positions into the container (both containers should already be sorted). According to strict weak sorting defined by operator< or COMp.

5.2 parameter

X: list object of the same type, both lvalue reference and rvalue reference

Comp: comparison function

// list::merge
#include <iostream>
#include <list>

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

int main (a)
{
  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(a); second.sort(a); first.merge(second);// The memory of second is transferred to first, and second is empty
std::cout <<second.size() < <'\n';
  // (second is now empty)

  second.push_back (2.1);

  first.merge(second,mycomparison);//mycomparison is an integer comparison, so 2.1 is played back at the end of the 2 part

  std::cout << "first contains:";
  for (std::list<double>::iterator it=first.begin(a); it! =first.end(a); ++it) std::cout <<' ' << *it;
  std::cout << '\n';

  return 0;
}
Copy the code

6, STD: : list: : remove

void remove (const value_type& val);
Copy the code

6.1 features

Removes all elements from the container that compare to val. This calls the destructor for these objects and reduces the container size by removing the number of elements. Unlike list::erase, which erases elements by their position (using iterators), list::remove removes elements by their value. A similar function list::remove_if exists, which allows conditions other than equality comparisons to determine whether an element has been removed.

6.2 parameter

Val element value

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

int main (a)
{
  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(a); it! =mylist.end(a); ++it) std::cout <<' ' << *it;
  std::cout << '\n';

  return 0;
}
Copy the code

7, STD: : list: : remove_if

template <class Predicate>
  void remove_if (Predicate pred);
Copy the code

7.1 features

Removes all elements that Predicate Pred returns true from the container. This calls the destructor for these objects and reduces the container size by removing the number of elements. This function calls pred(* I) for each element (where I is the iterator for that element). Any element in the list that returns true is removed from the container.

7.2 parameter

Pred: comparison function

// 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(a) (const int& value) { return (value%2) = =1; }};int main (a)
{
  int myints[]= {15.36.7.17.20.39.4.1};
  std::list<int> mylist (myints,myints+8);   // 15 36 7 17 20 39 4

  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(a); it! =mylist.end(a); ++it) std::cout <<' ' << *it;
  std::cout << '\n';

  return 0;
}
Copy the code

8, STD: : list: : sort

(1)	
  void sort(a);
(2)	
template <class Compare>
  void sort (Compare comp);xxxxxxxxxx (1)   void sort(a); (2) template <class Compare>  void sort (Compare comp);value_type* data(a) noexcept;const value_type* data(a) const noexcept;
Copy the code

8.1 features

Same as the sort function in the algorithm, but faster than the algorithm

9, STD: : list: : splice

entire list (1)	
void splice (const_iterator position, list& x);
void splice (const_iterator position, list&& x);
single element (2)	
void splice (const_iterator position, list& x, const_iterator i);
void splice (const_iterator position, list&& x, const_iterator i);
element range (3)	
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);
Copy the code

9.1 features

Move elements from X to the container and insert them into position. This effectively inserts these elements into the container and removes them from x, changing the size of both containers. This operation does not involve building or destroying any elements. Whether x is an lvalue or an rvalue, or whether value_type supports move constructs, they are migrated. The first version (1) transfers all elements of X into the container. The second version (2) only transfers the element I points to from X to the container. The third version (3) transfers the scope [first,last] from X to the container.

// splicing lists
#include <iostream>
#include <list>

int main (a)
{
  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(a); ++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(a); 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(a); it! =mylist1.end(a); ++it) std::cout <<' ' << *it;
  std::cout << '\n';

  std::cout << "mylist2 contains:";
  for (it=mylist2.begin(a); it! =mylist2.end(a); ++it) std::cout <<' ' << *it;
  std::cout << '\n';

  return 0;
}
Copy the code

10, STD: : list: : unique

(1)	void unique();
(2)	template <class BinaryPredicate> void unique (BinaryPredicate binary_pred);

10.1 features

Uniqueness, delete duplicate elements, must be sorted before deletion

10.2 parameter

Duplicate elements are deleted with no default parameter

BinaryPredicate: Removes elements that satisfy BinaryPredicate

// 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(a) (double first, double second)
  { return (fabs(first-second)<5.0); }};int main (a)
{
  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(a);// 2.72, 3.14, 12.15, 12.77, 12.77,
                             // 15.3, 72.25, 72.25, 73.0, 73.35

  mylist.unique(a);// 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(a); it! =mylist.end(a); ++it) std::cout <<' ' << *it;
  std::cout << '\n';

  return 0;
}
Copy the code

forward_list

1, STD: : forward_list: : before_begin

iterator before_begin(a) noexcept;
const_iterator before_begin(a) const noexcept;
Copy the code

1.1 features

Returns an iterator that refers to the position before the first element in the container.

The returned iterator should not be dereferenced: it is intended to be used as a parameter to the member functions emplace_after, insert_AFTER, erase_after, or splice_after, specifying the beginning of the sequence as the place to perform the operation.

1.2 the return value

An iterator that points to the position before the sequence begins. If the forward_list object is const qualified, this function returns a const_iterator. Otherwise, it returns an iterator.

// forward_list::before_begin
#include <iostream>
#include <forward_list>

int main (a)
{
  std::forward_list<int> mylist = {20.30.40.50};

  mylist.insert_after ( mylist.before_begin(), 11 );

  std::cout << "mylist contains:";
  for ( int& x: mylist ) std::cout << ' ' << x;
  std::cout << '\n';

  return 0;
}
Copy the code

2, STD: : forward_list: : cbefore_begin

const_iterator cbefore_begin(a) const noexcept;
Copy the code

2.1 features

Return a const_iterator to the point before a const_iterator refers to the first element in the container. Const_iterator is an iterator that refers to const content. This iterator can be incremented (unless it is also const), just like the iterator returned by forward_list:: before_BEGIN, but cannot be used to modify what it points to.

2.2 the return value

A const_iterator to the position before the start of the sequence. The member type const_iterator is a forward iterator type that refers to const elements.

// forward_list::cbefore_begin
#include <iostream>
#include <forward_list>

int main (a)
{
  std::forward_list<int> mylist = {77.2.16};

  mylist.insert_after ( mylist.cbefore_begin(), 19 );

  std::cout << "mylist contains:";
  for ( int& x: mylist ) std::cout << ' ' << x;
  std::cout << '\n';

  return 0;
}
Copy the code

3, STD: : forward_list: : emplace_after

No emplace and emplace_back (because it is one-way linked list)

template <class... Args>
  iterator emplace_after (const_iterator position, Args&&... args);
Copy the code

3.1 features

Extend the container by inserting a new element after the location element. This new element is constructed in place using args as the construction parameter. This effectively increases the container size by 1. Unlike other standard sequence containers, list and forward_list objects are specifically designed to efficiently insert and delete elements anywhere, even in the middle of a sequence. To place elements at the beginning of forward_list, use the member function emplace_front, or call this function at position before_BEGIN. This element is constructed in-place by calling allocator_traits::construct and forwarding args. A similar member function, insert_after, copies or moves an existing object into a container.

3.2 parameter

Position: iterator position

Args: list of constructors

// forward_list::emplace_after
#include <iostream>
#include <forward_list>

int main (a)
{
  std::forward_list< std::pair<int.char> > mylist;
  auto it = mylist.before_begin(a); it = mylist.emplace_after ( it, 100.'x' );
  it = mylist.emplace_after ( it, 200.'y' );
  it = mylist.emplace_after ( it, 300.'z' );

  std::cout << "mylist contains:";
  for (auto& x: mylist)
    std::cout << "(" << x.first << "," << x.second << ")";

  std::cout << '\n';
  return 0;
}
Copy the code

4, STD: : forward_list: : emplace_front

No emplace and emplace_back (because it is one-way linked list)

template <class... Args>
  void emplace_front (Args&&... args);
Copy the code

4.1 features

Inserts a new element at the beginning of the forward_list, just before its current first element. This new element is constructed in place using args as the construction parameter. This effectively increases the container size by 1. There is a similar member function called PUSH_front, which copies or moves an existing object into a container.

4.2 parameter

Constructor list

// forward_list::emplace_front
#include <iostream>
#include <forward_list>

int main (a)
{
  std::forward_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;
}
Copy the code

5, STD: : forward_list: : erase_after

There is no erase

iterator erase_after (const_iterator position);
iterator erase_after (const_iterator position, const_iterator last);
Copy the code

5.1 features

Removes a single element (the element after position) or a series of elements ((position,last)) from the forward_list container.

This effectively reduces the size of the container by removing the number of elements that are destroyed.

Unlike other standard sequence containers, list and forward_list objects are specifically designed to efficiently insert and delete elements anywhere, even in the middle of a sequence.

5.2 parameter

Position: iterator position that deletes the following element

Last: Iterator to the element after the last element to delete. The range of elements removed is the open range (position,last), which includes all elements between position and last, but not position or last itself. The member type const_iterator is a forward iterator type that refers to an element.

5.3 the return value

Iterator that points to the element next to the deleted element

// erasing from forward_list
#include <iostream>
#include <forward_list>

int main (a)
{
  std::forward_list<int> mylist = {10.20.30.40.50};

                                            // 10 20 30 40 50
  auto it = mylist.begin(a);/ / ^

  it = mylist.erase_after(it);              // 10 30 40 50
                                            / / ^
  it = mylist.erase_after(it,mylist.end()); / / 10 to 30
                                            / / ^

  std::cout << "mylist contains:";
  for (int& x: mylist) std::cout << ' ' << x;
  std::cout << '\n';

  return 0;
}
Copy the code

7, STD: : forward_list: : insert_after

There is no insert

(1)	iterator insert_after ( const_iterator position, const value_type& val );
(2)	iterator insert_after ( const_iterator position, value_type&& val );
(3)	iterator insert_after ( const_iterator position, size_type n, const value_type& val );
(4)	template <class InputIterator> iterator insert_after ( const_iterator position, InputIterator first, InputIterator last );
(5)	iterator insert_after ( const_iterator position, initializer_list<value_type> il );

7.1 features

Extend the container by inserting new elements after positional elements. This effectively increases the container size by the number of inserted elements. Unlike other standard sequence containers, list and forward_list objects are specifically designed to efficiently insert and delete elements anywhere, even in the middle of a sequence. A similar member function exists, emplace_after, which constructs an insert element object directly in place without any copy or move. Parameters determine the number of elements to be inserted and the values to which they are initialized:

7.2 Parameter insert with other containers

7.3 the return value

Point to the newly inserted element (end of sequence)

// forward_list::insert_after
#include <iostream>
#include <array>
#include <forward_list>

int main (a)
{
  std::array<int,3> myarray = { 11.22.33 };
  std::forward_list<int> mylist;
  std::forward_list<int>::iterator it;

  it = mylist.insert_after ( mylist.before_begin(), 10 );          / / 10
                                                                   // ^ <- it
  it = mylist.insert_after ( it, 2.20 );                          / / 10 20 20
                                                                   / / ^
  it = mylist.insert_after ( it, myarray.begin(), myarray.end());// 10 20 20 11 22 33
                                                                   / / ^
  it = mylist.begin(a);//  ^
  it = mylist.insert_after ( it, {1.2.3});1 2 3 20 20 11 22 33
                                                                   / / ^

  std::cout << "mylist contains:";
  for (int& x: mylist) std::cout << ' ' << x;
  std::cout << '\n';
  return 0;
}
Copy the code

8, STD: : forward_list: : splice_after

Slightly different from STD :: List ::splice

Transfer elements from FWDLST to the container, inserting them after the element indicated by the position. This effectively inserts these elements into the container and removes them from FWDLST, changing the size of both containers. This operation does not involve building or destroying any elements. Whether FWDLST is an lvalue or an rvalue, or whether value_Type supports move constructs, they are all transferred. The first version (1) transfers all elements of FWDLST to the container. The second version (2) only transfers the element I points to from FWDLST to the container. The third version (3) transfers the scope (first,last) from FWDLST to the container.

// forward_list::splice_after
#include <iostream>
#include <forward_list>

int main (a)
{
  std::forward_list<int> first = { 1.2.3 };
  std::forward_list<int> second = { 10.20.30 };

  auto it = first.begin(a);// points to the 1

  first.splice_after ( first.before_begin(), second );
                          // first: 10 20 30 1 2 3
                          // second: (empty)
                          // "it" still points to the 1 (now first's 4th element)

  second.splice_after ( second.before_begin(), first, first.begin(), it);
                          // first: 10 1 2 3
                          // second: 20 30

  first.splice_after ( first.before_begin(), second, second.begin());// first: 30 10 1 2 3
                          // second: 20
                          // * notice that what is moved is AFTER the iterator

  std::cout << "first contains:";
  for (int& x: first) std::cout << "" << x;
  std::cout << std::endl;

  std::cout << "second contains:";
  for (int& x: second) std::cout << "" << x;
  std::cout << std::endl;

  return 0;
}
Copy the code

Reference: list forward_list