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. std::list: a doubly-linked list, and
2. std::forward_list: a singly-linked list introduced in recent revisions (C++11)

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:

void merge (list& x);
void merge (list&& x);
template <class Compare>
void merge (list& x, Compare comp);
template <class Compare> void merge (list&& x, Compare comp);

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

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

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

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

  return 0;
}

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

// forward_list::sort
#include <iostream>
#include <forward_list>
#include <functional>

int main ()
{
  std::forward_list<int> mylist = {22, 13, 5, 40, 90, 62, 31};

  mylist.sort();

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

  mylist.sort(std::greater<int>());

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

  return 0;
}

default sort (operator<): 5 13 22 31 40 62 90
sort with std::greater(): 90 62 40 31 22 13 5

// list::sort
#include <iostream>
#include <list>
#include <string>
#include <cctype>

// comparison, not case sensitive.
bool compare_nocase (const std::string& first, const std::string& second)
{
  unsigned int i=0;
  while ( (i<first.length()) && (i<second.length()) )
  {
    if (tolower(first[i])<tolower(second[i])) return true;
    else if (tolower(first[i]) > tolower(second[i])) return false;
    ++i;
  }
  return ( first.length() < second.length() );
}

int main ()
{
  std::list<std::string> mylist;
  std::list<std::string>::iterator it;
  mylist.push_back ("one");
  mylist.push_back ("two");
  mylist.push_back ("Three");

  mylist.sort();

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

  mylist.sort(compare_nocase);

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

  return 0;
}

Dynamic Arrays with Class std::vector

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...

Only vectors have a capacity() member, which returns the size of the storage space currently allocated for the vector, expressed in terms of elements, that is, how many elements it can accomodate without reallocation. This capacity is not necessarily equal to the vector size but can be equal or greater, with the extra space allowing to accommodate for growth without the need to reallocate on each insertion.

Notice that this capacity does not suppose a limit on the size of the vector. When this capacity is exhausted and more is needed, it is automatically expanded by the container (reallocating it storage space). The theoretical limit on the size of a vector is given by member max_size().

Double-Ended Queues with std::deque

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, only the block (out of several blocks) targeted by the insertion/deletion.
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).

Fixed-sized Arrays with std::array

std::array is a fixed-sized array, kind of a paired-down std::vector.

std::array is defined in <array>.

The size of an std::array object is passed in as a template parameter.

Synopsis:

template <typename T, size_t N> class array;

where T is the type of the elements contained and is aliased as member type array::value_type.

It is as efficient in terms of storage size as an ordinary array declared with the language's bracket syntax ([]). This class merely adds a layer of member and global functions to it, so that arrays can be used as standard containers.

Unlike with the other containers in the Standard Library, swapping two array containers is a linear operation that involves swapping all the elements in the ranges individually, which generally is a considerably less efficient operation. On the other side, this allows the iterators to elements in both containers to keep their original container association.

Another unique feature of array containers is that they can be treated as tuple objects: The <array> header overloads the global std::get function to access the elements of the array as if it was a tuple, as well as specialized tuple_size and tuple_element types.

std::array has the full set of iterator member functions: begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), and crend()

The capacity interface has three these constant member functions: size(), max_size(), and emply(). Both size() and max_size are always equal to the second template parameter used to instantiate the array template class. empty() only return true if the array size is 0, that is, if the second template parameter is 0.

Member fill(const value_type& value) fills array with value.

Member data() returns a pointer to the first element in the std::array object.

value_type* data() noexcept;
const value_type* data() const noexcept;

Bitmap's*

Random Access Returning Reference with operator[](index)

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.

Changing Capacity with CONTAINER::resize(new_size) and CONTAINER::shrink_to_fit() (only std::vector and std::queue)

void resize (size_type n);void resize (size_type n, const value_type& val);