Sequence Containers

Lists with std::list and std::forward_list

A list is a sequence optimized for insertion and deletion of elements. When you insert into a list or delete an element from a list , the locations of other elements of the list are not affected. In particular, iterators referring to other elements are not affected.

The main drawback of std::list and std::forward_list compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list, one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

Artificial Intelligence lists are basically weakly-typed or untyped lists. Such lists may contain elements of any type, even sublists... Just like lists in C++, they are not index-addressable.

The STL provides two linked-list types:

  1. list: a doubly-linked list, and
  2. forward_list: a singly-linked list introduced in recent revisions (C++11)

These are implemented in container std::list<>.

With the exception of subscripting, capacity management, and size() for forward_list, the STL lists provide the member types and operations offered by vector<>. In addition, list<> and forward_list<> provide specific list member functions:

Doubly-Linked Lists with std::list

st.push_front(x) Add x to lst (using copy or move) before the first element
lst.pop_front() Remove the first element from lst
lst.emplace_front(args) Add T{args} to lst before the first element
lst.remove(v) Remove all elements of lst with value v
lst.remove_if(f) Remove all elements of lst for which f(x)==true
lst.unique() Remove adjacent duplicate elements of lst
lst.unique(f) Remove adjacent duplicate elements of lst using f for equality
lst.merge(lst2) Merge the ordered lists lst and lst2 using < as the order; lst2 is merged into lst and emptied in the process
lst.merge(lst2,f) Merge the ordered lists lst and lst2 using f as the order; lst2 is merged into lst and emptied in the process
lst.sort() Sort lst using < as the order
lst.sort(f) Sort lst using f as the order
lst.reverse() Reverse the order of the elements of lst ; noexcept

Singly-Linked Lists with std::forward_list*

std::forward_list objects are single-linked lists, and thus they can only be iterated forwards, in exchange for being somewhat smaller and more efficient than doubly-linked std::list's.

Vectors

std::vectors are automatic arrays which keep track of their size, that is how many places have been occupied (pressumably in an integer variable), as well as their capacity, which is the total number of objects of the given type that they can accomodate. Further, when they have filled up, they reallocate their sequence of objects in a larger chunk of memory, the start of this run of memory is updated (in a pointer variable), and the new, larger capacity is updated, too. This means that indeces into the array-like structure remain valid, but pointers are invalidated, so they must never be taken in the first place.

Unlike with linked lists, insertions (or deletions) are either meaningless or demand that all objects after the one inserted be shifted one place, which is done in linear time, whereas lists perform insertions and deletions in constant time. Furthermore, insertions and deletions would invalidate all subsequent indeces...

Deques

A deque (pronounced "deck") is very similar to a vector. It manages its elements with a dynamic array, provides random access, and has almost the same interface as a vector. The difference is that with a deque the dynamic array is open at both ends. Thus, a deque is fast for insertions and deletions at both the end and the beginning.

Deques have the following differences compared with the abilities of vectors:

  1. Inserting and removing elements is fast both at the beginning and at the end (for vectors it is only fast at the end). These operations are done in amortized constant time.
  2. The internal structure has one more indirection to access the elements, so element access and iterator movement of deque's are usually a bit slower.
  3. Iterators must be smart pointers of a special type rather than ordinary pointers because they must jump between different blocks.
  4. In systems that have size limitations for blocks of memory (for example, some PC systems), a deque might contain more elements because it uses more than one block of memory. Thus, max_size() might be larger for deque's.
  5. Deques provide no support to control the capacity and the moment of reallocation. In particular, any insertion or deletion of elements other than at the beginning or end invalidates all pointers, references, and iterators that refer to elements of the deque.
  6. However, reallocation may perform better than for vectors, because according to their typical internal structure, deque's don't have to copy all elements on reallocation.
  7. Blocks of memory might get freed when they are no longer used, so the memory size of a deque might shrink (however, whether and how this happens is implementation specific).

Bitmap's*

Random Access Returning Reference

Sequence containers based on an array offer access through indexes. They will declare:

reference operator[](size_type idx);
const_reference operator[](size_type idx) const;

These are fast but do not perform bound checking. Trying to access beyond the end of the underlying array may, well, crash the program or yield the wrong result. If unsure, use:

      reference at(size_type idx);
const_reference at(size_type idx) const;

Member function at(size_type idx) returns a reference or const_reference all right, but will throw an out_of_range exception. Use at(size_type idx) inside a try {...} block.

If you write a container in the STL tradition that returns references to elements of an array, write the body of your at(size_type idx) like this:

if(idx >= size())
  throw out_of_range("Container::at() used with idx past the end");
else
  return the_array[idx];

Find and Replace Operations

Functions find(...) returns a size_type variable, actually an integer representing an index to the element found. A string's find() operation may return npos, for no position, which should be defined as -1.