VECTOR

  • Dynamic Size
  • Direct Element Acess (constant time)
  • Rapid insertion and deletion at the back
  • All the algorithms are availabe and may become invalid

If we create a vector of objects then we can use

  • Copy constructor like copying the object
  • Move semantics by directly calling the constructor in the push_back function
  • Efficient way is by directly passing the parameters required by the constructor

emplace_back

v1.emplace_back("Larry", 28)

Efficient

INSERT

First we will pass the iterator pointing to the element before which the element or range of elements needs to be inserted.


Then pass the value or the range of values to be inserted

DEQUE

  • Dynamic Size
  • Direct Element Access
  • Elements are not stored in contiguous memory
  • Rapid insertion and deletion at the front and at the back (constant time)

All iterators available and may invalidate

Behind the scenes deque is stored in memory blocks which are linked to each other, the elements inside the block are contiguous but the blocks themselves are not in contiguous memory

  • If an element is to be added in the deque at the back, if the block is full then a new memory block will be allocated and will be linked to this previous block and the element will be stored

NOTE

iota

iota(start_iterator, end_iterator, start_value)

It will go through the container and assign values in increasing order till the size of the container

front_inserter

click to edit

it returns front_insert_iterator to the container

Can be used with the copy function
copy(vec.begin(), vec.end(), front_inserter(v2)

This copy function will take as input the range of elements from which the copy is to be made and then will insert elements at the front

Palindrome identification using deque

  • The size must be > 1 can't use begin and end operators cause it may be some another memory block

LIST

  • Sequence containers
  • Non Contiguous in Memory
  • No Direct Access to elements
  • Very efficient for inserting and deleting elements once an element is found
  • Dynamic Size
  • Bidirectional (doubly linked)
  • Rapid insertion and deletion of elements (constant time) anywhere in the container
  • All iterators available and invalidate when corresponding element is deleted

An element in the list has a reference to the element after it as well as before it, if they exist

  • There is some overhead involved in maintaining the list of elements
  • the list has a front and a back
  • Insert
  • Erase -> deletes the element iterator is pointing to
  • Resize -> Resizes the list to the specified size and deletes all the other elements, if the size is greater than the current size, then it will fill the values of the new elements with the default values

TRAVERSAL - Possible in both the directions ,
we can use a Range based for loop or iterators, incrementing and decrementing the iterator both are possible in list

Forward List

  • Uni - Directional (Singly Linked List)
  • Reverse iterators not available, iterators invalidate when corresponding element is deleted
  • Less overhead than the list
  • Doesn't support size() method
  • Doesn't have back()

why

Because it was seen that the if we included the count of the elements then it was taking more space as well as time creating more overhead so the size was not included in the forward list

  • front()
  • push_front()
  • pop_front()
  • emplace_front()
  • resize()

Since it's a singly linked list it makes sense to insert elements into the forward list after an iterator reference

  • insert_after
  • emplace_after
  • erase_after

Whenever we use our own class templates with the STL it is a good practise to overload the less than and equality operators ❤