C++ Lists

Lists are sequences of elements stored in a linked list. Compared to vectors, they allow fast insertions and deletions, but slower random access as we need to traverse all the elements to finding any element.




Lists Operators
  • assign - assign an element to list
  • back - returns a reference to the last element of a list
  • begin - returns a reference iterator to the beginning of the list
  • clear - deletes all elements from the list
  • empty - returns true(1) if the list has no elements else return false(0).
  • end - return a reference iterator just past the last element of a list
  • erase - deletes elements from a list
  • front - returns a reference iterator to the first element of a list
  • insert - inserts elements into the list
  • max_size - outputs the number of the maximum number of elements that the list can hold
  • merge - merge two list
  • pop_back - removes the last element from the list
  • pop_front - removers the first element from the list
  • push_back - add an element to the end of the list
  • push_front - add an element to the front of the list
  • rbegin - returns a reverse_iterator to the end of the  list
  • remove - removes elements from a list
  • remove_if - removes element if the given condition is fulfilled.
  • rend - returns a reverse_iterator to the beginning of the list
  • resize - used to change the size of the list
  • reverse - reverse the list.
  • size - outputs the number of items in the list
  • sort - sorts a list into ascending order
  • splice - merge two lists in constant time
  • swap - swap the contents of this list with another list.
  • unique - removes consecution duplicate element
Now we will be taking look at the implementation of the list. We will be implementing some of the uncommon functions here. For common function please go through vectors STL article.

assign()
  • This function assign value(s) to the list having some count of value(s). for eg: assign 3 elements with value 10 will be like 10 10 10.  
  • This can also be used to copy an element from one vector to another.
  • This function will destroy the previous contents of the list.

back()
  • The back() function returns a reference(not an iterator) to the last element in the list.
begin()
  • The function begin() returns an iterator to the first element of the list.
  • It runs in constant time.
clear()
  • The function clear() deletes all of the elements in the list.
  • It runs in linear time.
empty()
  • The empty() function returns true if the list has no elements, false otherwise.
end()
  • The end() function returns an iterator just past the end of the list.
  • Note that before you can access the last element of the list using an iterator that you get from a call to end(), you'll have to decrement the iterator first.

erase()
  • The erase() function either deletes the element at given location , or deletes the elements between start and end (including start but not including end). The return value is the element after the last element erased.
  • The first version of erase (the version that deletes a single element at given location) runs in constant time for lists and linear time for vectors, dequeues, and strings. The multiple element version of erase always takes linear time.

front()
  • The front() function returns a reference(not an iterator) to the first element of the list.
  • It runs in constant time.
insert()
      The insert function either:
  • inserts value before location, returning an iterator to the element inserted,
  • inserts num copies of value before location, or
  • inserts the elements from start to end before location

max_size()
  • The max_size() function returns the maximum number of elements that the list can hold. The max_size() function should not be confused with the size() or (C++ Strings) capacity() functions, which return the number of elements currently in the list and the the number of elements that the list will be able to hold before more memory will have to be allocated, respectively.
merge()
  • The function merge() merges the list with lst, producing a combined list that is ordered with respect to the < operator. If compare function is specified, then it is used as the comparison function for the lists instead of <.
  • merge() runs in linear time.
  • Note that the list which is merged will become empty after merging

pop_back()
  • The pop_back() function removes the last element of the list
  • pop_back() runs in constant time
pop_front()
  • The function pop_front() removes the first element of the list.
  • The pop_front() function runs in constant time.
push_back()
  • The push_back() function appends value to the end of the list
  • The push_back() function runs in constant time.
push_front()
  • The push_front() function inserts val at the beginning of list.
  • push_front() runs in constant time.
rbegin()
  • The rbegin() function returns a reverse_iterator to the end of the current list.
  • rbegin() runs in constant time.
remove()
  • The function remove() removes all elements that are equal to val from the list.
  • remove() runs in linear time.
remove_if()
  • The remove_if() function removes all elements from the list for which the unary predicate is true.
  • remove_if() runs in linear time .

rend()
  • The function rend() returns a reverse_iterator to the beginning of the current list.
  • rend() runs in constant time
resize()
  • The function resize() changes the size of the list to size. If val is specified then any newly created elements will be initialized to have a value of val.
  • This function runs in linear time.
reverse()
  • The function reverse() reverses the list, and takes linear time
size()
  • The size() function returns the number of elements in the current list.
sort()
  • The sort() function is used to sort lists into ascending order. Ordering is done via the < operator, unless p is specified, in which case it is used to determine if an element is less than another.
  • Sorting takes N log N time.
splice()
  • The splice() function inserts lst at location pos. If specified, the element(s) at del or from start to end are removed.
  • splice() simply moves elements from one list to another, and doesn't actually do any copying or
    deleting. Because of this, splice() runs in constant time


swap()
  • The swap() function exchanges the elements of the current list with those of other. This
    function operates in constant time
  • Note that 2 lists to be swapped should be of same size and having same data type.

unique()
  • The function unique() removes all consecutive duplicate elements from the list. 
  • Note that only consecutive duplicates are removed, which may require that you sort() the list first. 
  • unique() runs in linear time.
If you have some content OR material OR something is missing related to this then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by CODELABS3277

Comments