Data stru structures ctures n’ containers in C++ ARRAY: #include push_back( ) pop_back( ) operator [ ] O(1) begin( ) end( ) insert( ) erase( ) size() empty() O(n) LIST: #include push_front( ) push_back( ) pop_back( ) pop_front( ) O(1) begin( ) end( ) insert( ) erase( ) size() empty() O(n) STACK: #include push( ) pop( ) top( ) size() empty() O(1) QUEUE: #include push( ) pop( ) front( ) back( ) size() empty() O(1) MAX BINARY HEAP: #include push( ) pop( ) O(log n) top() size() empty() O(1) BINARY SEARCH TREE: #include or insert( ) O(log erase( ) operator [ ] (map only) n) begin( ) end( ) find( ) count( ) size() empty() O(log n) return iterator or set::end return 0 or 1 Nota: if you want to insert several times the same value prefer to use or but operator [] will be not available anymore. HASH TABLE: #include or insert( ) O(1) erase( ) operator [ ] (unordered_map only) begin( ) end( ) find( ) count( ) reserve( ) O(1) Nota: hash_table is a very efficient data structure but elements can not be ordered. - - size() empty() return iterator or set::end return 0 or 1 set the number of buckets For the following data structures there is no base container implemented in C++ so you have to do by hand. MIN BINARY HEAP: the package contains a function make_heap() to make a binary heap and by default this is a max binary heap. std::vector minHeap; std::make_heap(minHeap.begin(), minHeap.end(), std::greater()); // to add a value minHeap.push_back(x); push_heap(minHeap.begin(), minHeap.end(), std::greater()); // to remove pop_heap(minHeap.begin(), minHeap.end(), std::greater()); minHeap.pop_back(); BINARY TREE: a simple binary tree is not very useful because you often need some properties (ordered, max value at root) which force you to use a or or . If however you still want to implement one the easiest way is maybe to use a simple (like binary heaps) and to move through the tree using i *2 to get the left child and i *2 + 1 to get the right child. To insert an element you can perform a push_back() so your tree will be balanced. If you don’t want this behavior we can use a struct node with pointers and implement a function to insert and delete an element: class Node { int key_value; node *left; node *right; }; GRAPH/N-ARIES TREE: are nodes identified using index from 0 to N? YES => the node index (vertex) will match the vector index vector > > graph; or vector > > graph; //edges have weight NO => you have to create dedicated classes class Edge; class Vertex { int id; vector ptr_edges; } class Edge { Vertex *from; Vertex *to; int cost; } class Graph { vector vertices; }

Data Structures n’ Сontainers in C++

Related Documents

Recommended Documents

Description

Related Documents

Want to Download This Document?

Free up your schedule!

Take 5 seconds to unlock