Grade 12 · 9 algorithmsCitește în română

Data structures and the STLStructuri de date și STL

Every data structures and the stl algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

9algorithms
6chapters
1grade

Data structures and the STL

Structuri de date și STL · 9 algorithms

deque: sliding window minimum of length kdeque — minimul pe ferestre de lungime kFor every run of k consecutive elements we want the minimum. We keep the 'candidate' positions in a deque, with values increasing from front to…O(n)
queue: elimination in a circle (Josephus)queue — eliminarea din cercn children, numbered from 1 to n, stand in a circle. We count k at a time, and the child where the count stops leaves the game; counting continues…O(n²)
pair: union of intervalspair — reuniunea intervalelorpair<int, int> groups two values (first, second) and compares lexicographically: first by first, then by second. So sort on an array of pairs orders…O(n log n)
stack: checking bracketsstack — verificarea parantezelorA string with the brackets (), [] and {} is correct if every closing bracket matches the last opening bracket still left open. 'Last opened, first…O(n)
priority_queue: the k largest valuespriority_queue — cele mai mari k valoripriority_queue is a heap: top() gives the 'most important' element, and push and pop cost O(log size). By default the top is the maximum; with…O(n log n)
set and map: word frequencyset și map — frecvența cuvintelorWe read words (lowercase letters) until the end of the input. A set<string> keeps every word once, in alphabetical order, so size() gives the number…O(n log n)
Sorting with a comparatorSortare cu comparatorsort(begin, end, cmp) orders by our own rule: cmp(x, y) returns true if x must come before y. Here we sort the contestants of a competition by score…O(n log n)
Disjoint-set forests (union-find)Păduri de mulțimi disjuncte (union-find)We have n elements, each initially in its own set. Operation 1 x y joins the sets of x and y, and operation 2 x y asks whether x and y are in the…O(n)
The STL vector containerContainerul vector din STLvector<int> is an array that manages its own memory: push_back adds at the end (O(1) on average), size() gives the number of elements, and v[i]…O(n log n)