Understanding STL: Vectors, Lists, Iterators, and Container Implementations

The Standard Template Library (STL) offers template classes and functions that implement a wide range of data structures and algorithms, giving programmers significant benefits in code size, execution time, and development efficiency.

STL can be roughly divided into three categories: algorithms, containers, and iterators.

Vector vs. List – Vectors store elements in contiguous memory like arrays, providing O(1) random access but O(n) insertion/deletion due to possible memory copying. Lists use a doubly‑linked structure, offering O(1) insertion/deletion at any position but no efficient random access.

Example of accessing the second‑last element in a vector:

int mySize = vec.size(); vec.at(mySize - 2);

Vectors dynamically grow: when the current capacity is insufficient, a new larger block (often double the size) is allocated, elements are moved, and the old block is freed. This reallocation incurs O(n) copying cost.

Implementation of vector capacity expansion:

void vector::expandCapacity() { size_t newCapacity = capacity * 2; // double the capacity T* newElements = new T[newCapacity]; // allocate new space for (size_t i = 0; i < size; i++) { newElements[i] = elements[i]; // move data } delete[] elements; // free old space elements = newElements; // update pointer capacity = newCapacity; // update capacity }

Deletion operations: pop_back() removes the last element, while erase() can remove a single element or a range. The generic algorithm remove() only shifts elements and returns a new logical end iterator; it does not change the container size and must be combined with erase() to actually delete elements.

Example of using pointers and references with a vector:

#include int main() { std::vector vec = {1, 2, 3, 4, 5}; std::vector * ptr = &vec // pointer (*ptr)[0] = 10; // modify via pointer ptr->push_back(6); // call member function return 0; } #include int main() { std::vector vec = {1, 2, 3, 4, 5}; std::vector & ref = vec; // reference ref[0] = 10; // modify via reference ref.push_back(6); return 0; }

Iterator validity: after inserting or erasing elements in a vector, iterators may become invalid and need to be re‑located; in a list, iterators remain valid after insertion or deletion. Reserving capacity with reserve(n) can pre‑allocate memory to avoid frequent reallocations.

Common iterator properties include value type, difference type, pointer, reference, and iterator category (input, output, forward, bidirectional, random‑access).

Maps and sets are implemented with red‑black trees, providing O(log n) insertion, deletion, and lookup while maintaining ordered elements.

Using STL containers in shared memory allows inter‑process communication without designing custom data structures, but care must be taken to avoid heap allocations inside the shared segment.

Map insertion methods include insert(pair) , insert(value_type) , insert(make_pair(...)) , and the subscript operator operator[] .

Vector out‑of‑bounds access via the subscript operator does not perform bounds checking; the at() method throws an exception on invalid indices. For maps, operator[] inserts a default‑constructed value if the key does not exist.

Lists differ from queues: lists are doubly‑linked, allowing constant‑time insertion/deletion anywhere, while queues are typically built on deque or list adapters and provide FIFO semantics.

Summary of common container characteristics: vectors use contiguous arrays, lists use doubly‑linked nodes, deques combine multiple buffers, stacks and queues are adapters, priority queues use a heap, sets and maps use red‑black trees, unordered containers use hash tables.

Ordered containers maintain element order according to a comparison function (default ascending). Unordered containers provide no ordering but offer average O(1) access.

Iterator types per container: vectors and deques use random‑access iterators; lists, sets, maps, and multiset use bidirectional iterators; unordered containers use forward iterators.

slist (single‑linked list) uses forward iterators; insertion and removal are efficient at the front, while other positions require traversal.

Implementation sketch of slist :

template class slist { ... private: static list_node* create_node(const value_type& x) {} // allocate and construct static void destroy_node(list_node* node) {} // destruct and free list_node_base head; // head node public: iterator begin() {} iterator end() {} size_type size() {} bool empty() {} void swap(slist& L) {} // swap heads reference front() {} void push_front(const value& x) {} void pop_front() {} ... };

Example usage of forward_list (C++11):

#include #include #include using namespace std; int main() { forward_list fl; fl.push_front(1); fl.push_front(3); fl.push_front(2); fl.push_front(6); fl.push_front(5); for (auto it = fl.begin(); it != fl.end(); ++it) { cout << *it << " "; // 5 6 2 3 1 } cout << endl; auto it = find(fl.begin(), fl.end(), 2); if (it != fl.end()) fl.insert_after(it, 99); for (auto v : fl) cout << v << " "; // 5 6 2 99 3 1 cout << endl; it = find(fl.begin(), fl.end(), 6); if (it != fl.end()) fl.erase_after(it); for (auto v : fl) cout << v << " "; // 5 6 99 3 1 cout << endl; return 0; }

Implementation of list node (simplified):

template struct list_node { typedef void* void_pointer; void_pointer prev; void_pointer next; T data; };

Implementation sketch of deque :

class deque { // ... protected: typedef pointer* map_pointer; // pointer to map array map_pointer map; // points to map size_type map_size; // size of map public: // ... iterator begin(); iterator end(); // ... };