Introduction to STL Containers

Introduction to STL Containers

• STL containers are collections of objects.
• Template classes define containers, separating the container from the data type inside.
• Each container type is optimized for specific uses (access/modification).
• Main containers include list, vector, stack, queue, and map.

Vector Operations

• Insert: v.push_back() adds an element.
• Remove: v.pop_back() removes an element from the end.
• Clear: v.clear() removes all elements.
• First Element: v.begin() returns an iterator to the first element.
• Last Element: v.end() returns an iterator to one position after the last element.
• Specific Element: v[i] returns the element at position i (0-based index).
• Size: v.size() returns the number of elements.
• Empty Check: v.empty() returns true if the vector is empty.

Container Types

• List: Inserts and removes elements anywhere in constant time; uses automatic memory management.
• Vector: General purpose, fast access by index (constant time); removes elements from the end in constant time; other inserts and removes take linear time.
• Set/Map: Accesses elements by a key in constant time; provides fast search.

Container Constructors

• Example using list and vector:
  • list<int> one_list; creates an empty list.
  • list<double> second_list(10, 4.22); creates a list of 10 doubles, all initialized to 4.22.
  • list<double> third_list(second_list); creates a copy of second_list.
  • vector<string> one_vector; creates an empty vector of strings.
  • vector<int> two_vector(4); creates a vector of 4 integers with undefined values.

Container Properties

• Containers have their own elements.
• Elements must support copy and assignment instructions.
• All containers have empty() and size() methods in constant time.
• All containers have begin() and end() methods.

Choosing a Container

• Consider the purpose of accessing elements (randomly, sequentially).
• Consider the needed modifications (add, delete, sort, etc.)
• Factors affecting performance include access time, modification time, number of elements, and memory usage. (e.g. linear, log, exponential time).

Iterators and their Purpose

• Iterators: Pointer generalization, used for sequential element access, and optimizing operations based on the container type.
• Iterator Definition: Identifies a container and an element; lets you examine the stored value; provides operations between elements; restricts operations to those handled efficiently by the type of container.

Using Iterators

• In the example code using iterators, looping through vector elements
• Iterators for containers are used to loop and access the elements of a container

Standard Library Algorithms

• STL algorithms are functions designed for use with containers, requiring iterators/pointers for element access; they do not affect container structure.
• for_each, find, copy, replace, rotate, set_union, and min_elements are example functions.

Associative Containers

• Needed when finding a value in a sequential container quickly.
• Advantage: arrange elements and exploit order to locate quicker.
• They are stored in a particular order based on the key value

Associative Array (map)

• The key is associated with a value.
• Keys don't need to be integers, any comparable values can be used.
• Keys must be unique.
• Containers are self-ordering: the program shouldn't change the element order.

Map Operations

• Operations include begin(), end(), empty(), and size(); operator[] to access elements; insert and erase methods affect elements; and find, lower_bound, and upper_bound for iterators and returning specified values.

Using Associative Functions

• Examples use maps for counting word occurrences in a sentence or for decomposing a list of names into groups based on first letters.