Using std::list

CSCI 362: Data Structures

Prof. William Killian

List

list overcomes some limitations of vector

• Order is (still) important
• $O(1)$ insertion time at arbitrary location (given iterator)
• Nodes are stored non-contiguously
• No subscript operator -- why?

std::list API

Defined in header <list>

namespace std {
  template <
    typename T,                            // value type to store
    typename Allocator = std::allocator<T> // how to allocate data
  > class list;
}

std::list Special Member Datatypes

Name	Description
T	template parameter for value type to store
value_type	alias to T
size_type	unsigned integer type (usually std::size_t)
difference_type	signed integer type (usually std::ptrdiff_t)
reference	alias to value_type&
const_reference	alias to value_type const&
pointer	usually just value_type*
const_pointer	usually just value_type const*
iterator	implementation-defined type
const_iterator	implementation-defined type
reverse_iterator	std::reverse_iterator<iterator>
const_reverse_iterator	std::reverse_iterator<const_iterator>

std::list Contructors

list ();
list (size_type n);
list (size_type n, T const& value);

template <typename InputIterator>
list (InputIterator first, InputIterator last);

list (std::initializer_list<T>);

list()

• create an empty list

std::list<int>()

{}

list(size_type n)

• create a list with $n$ elements (default-constructed)

std::list<int>(5)

{ 0, 0, 0, 0, 0 }

list(size_type n, T const& value)

• create a list with $n$ elements initialized to value

std::list<int>(5, 2)

{ 2, 2, 2, 2, 2 }

template <typename InputIterator>
list(InputIterator first, InputIterator last);

• initialize the list using the range [first, last)
• first and last are input iterators

list(std::initializer_list<T> list);

• initialize the list using the initializer list

std::list<int> l = {5, 4, 3, 2, 1};
l

{ 5, 4, 3, 2, 1 }

std::list Access Operations

const_reference back ()  const;
const_reference front () const;
      reference back ();
      reference front ();

reference back ();

• return the value of the item at the rear (or back) of the list
• Precondition: the vector must contain at least one element

 

const_reference back() const;

• const version of back()

[] () -> int& {
    static std::list<int> a = {1, 2, 3};
    return a.back();
}()

3

[] () -> int const& {
    const static std::list<int> a = {1, 2, 3};
    return a.back();
}()

3

reference front ();

• return the value of the item at the beginning (or front) of the list
• Precondition: the vector must contain at least one element

 

const_reference front() const;

• const version of front()

[] () -> int& {
    static std::list<int> a = {1, 2, 3};
    return a.front();
}()

1

[] () -> int const& {
    const static std::list<int> a = {1, 2, 3};
    return a.front();
}()

1

std::list Capacity Operations

bool      empty ()    const;
size_type size ()     const;
size_type max_size () const;

bool empty() const;

• returns true IFF the vector's size is zero  

size_type size () const

• returns the current size of the vector  

size_type max_size() const;

• returns the maximum number of elements the list can hold (implementation dependent)

std::list Iterator Operations

iterator               begin ()  noexcept;
iterator               end ()    noexcept;
reverse_iterator       rbegin () noexcept;
reverse_iterator       rend ()   noexcept;
const_iterator         begin ()  const noexcept; // and cbegin()
const_iterator         end ()    const noexcept; // and cend()
const_reverse_iterator rbegin () const noexcept; // and crbegin()
const_reverse_iterator rend ()   const noexcept; // and crend()

std::list Modifying Operations

Similar to std::vector!

void      clear();
void      pop_back ();
iterator  erase (...);  // 2 versions

iterator  insert (...); // 5 versions
void      push_back (const_reference value); // and "move" variant

template <typename ... Args>
iterator  emplace (const_iterator pos, Args&& ... value);

template <typename ... Args>
reference emplace_back (Args&& ... value);

std::list Modifying Operations

void      pop_front ();

void      push_front (const_reference value); // and "move" variant

template <typename ... Args>
reference emplace_front (Args&& ... value);

void      resize(...);  // 2 versions

void push_back (const_reference value);

• Adds a value at the rear of the list
• Postcondition: The list has a new element at the rear; size is increased by 1

 

void pop_back ();

• Removes a value from the rear of the list
• Precondition: The list is not empty
• Postcondition: The list's last element has been removed or is empty; size decreases by 1

void push_front (const_reference value);

• Adds a value at the front of the list
• Postcondition: The list has a new element at its front; size is increased by 1

 

void pop_front ();

• Removes a value from the front of the list
• Precondition: The list is not empty
• Postcondition: The list's last element has been removed or is empty; size decreases by 1

iterator insert (const_iterator pos, const_reference value);

• inserts $value$ before $pos$ and returns an iterator pointing to the position of the new value in the list
• NOTE: this operation will NEVER invalidate any existing iterators
• Postcondition: The list has a new element; size is increased by 1

 

iterator erase (const_iterator pos);

• Erase the element pointed to by $pos$
• NOTE: only the passed iterator is invalidated
• Precondition: The list is not empty
• Postcondition: The list has one less element; size is decreased by 1

iterator erase (const_iterator first, const_iterator last);

• Erases the range of all elements in [first, last)
• NOTE: Only iterators within the range [first, last) are invalidated
• Precondition: The list is not empty
• Postcondition: Size decreases by std::distance(first, last); the same number of elements are removed

 

void resize(size_type n);

• Modify the size of the vector. If the size is increased, the default value T() is filled for the increase in elements at the end. If the size is decreased, the original values at the front are retained.
• Postcondition: The vector has size $n$

Additional std::list Modifying Operations

Merge

merge two sorted lists. The passed list becomes empty

void merge (list& other);
void merge (list&& other);
template <typename Compare>
void merge (list& other, Compare comp);
template <typename Compare>
void merge (list&& other, Compare comp);

Splice

Transfer elements from one list to another in constant time

void splice (const_iterator pos, list& other);
void splice (const_iterator pos, list&& other);

void splice (const_iterator pos, list& other, const_iterator it);
void splice (const_iterator pos, list&& other, const_iterator it);

void splice (const_iterator pos, list& other, const_iterator first, const_iterator last);
void splice (const_iterator pos, list&& other, const_iterator first, const_iterator last);

1. transfers all elements from $other$ into *this at location $pos$, causing $other$ to be empty
2. transfer the element from $other$ pointed to by $it$ into *this at location $pos$
3. transfers the elements from $other$ in the range $[ first, last )$ into *this at location $pos$

Remove / Remove If

Removes all elements satisfying specific criteria. The first version removes all elements that are equal to $value$, the second version removes all elements for which predicate $p$ returns true.

size_type remove (T const& value);

template <typename UnaryPredicate>
size_type remove_if (UnaryPredicate p);

Reverse, Unique, and Sort

void      reverse ();

size_type unique();

template <typename BinaryPredicate>
size_type unique (BinaryPredicate p);

void      sort();

template <typename Compare>
void      sort (Compare comp);

• reverse -- reverses the order of the elements
• unique -- removes consecutive duplicate elements
• sort -- Sorts the elements in ascending order. Stable. $O(N lg N)$

List iterators

• List has bidirectional iterators (which are not random access)
• Declaration

  list<int>::iterator li;
  

• Iterator movement:

  #include <iterator>
  std::advance (li, 2);    // li += 2
  li2 = std::next (li, 2); // li2 = li + 2;
  li3 = std::prev (li, 3); // li2 = li - 3;
  

• How do we implement a list iterator?

template <typename T>
class list {
public:
  class iterator {
  public:
    T&        operator*();
    T const&  operator*();
    T*        operator->();
    T const*  operator->();
    iterator& operator++();
    iterator  operator++(int) const;
    iterator& operator--();
    iterator  operator--(int) const;
    bool      operator==(iterator const& other) const;
    bool      operator!=(iterator const& other) const;
  };
  ...  
};

// Using std::list

Examples to follow...