C++ Algorithms Example
This snippet demonstrates common algorithms and data structures in C++.
CPP
1
2 #include <iostream>
3 #include <vector>
4 #include <algorithm>
5 #include <string>
6 #include <map>
7 #include <set>
8 #include <queue>
9 #include <memory>
10
11 // Template function for binary search
12 template <typename T>
13 int binarySearch(const std::vector<T>& arr, const T& target) {
14 int left = 0;
15 int right = arr.size() - 1;
16
17 while (left <= right) {
18 int mid = left + (right - left) / 2;
19
20 if (arr[mid] == target) {
21 return mid;
22 } else if (arr[mid] < target) {
23 left = mid + 1;
24 } else {
25 right = mid - 1;
26 }
27 }
28
29 return -1; // Not found
30 }
31
32 // Tree node structure
33 struct TreeNode {
34 int val;
35 std::unique_ptr<TreeNode> left;
36 std::unique_ptr<TreeNode> right;
37
38 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
39 };
40
41 // Insert into BST
42 std::unique_ptr<TreeNode> insertIntoBST(
43 std::unique_ptr<TreeNode> root,
44 int val
45 ) {
46 if (!root) {
47 return std::make_unique<TreeNode>(val);
48 }
49
50 if (val < root->val) {
51 root->left = insertIntoBST(std::move(root->left), val);
52 } else {
53 root->right = insertIntoBST(std::move(root->right), val);
54 }
55
56 return root;
57 }
58
59 // Inorder traversal
60 void inorderTraversal(const TreeNode* root, std::vector<int>& result) {
61 if (!root) return;
62
63 inorderTraversal(root->left.get(), result);
64 result.push_back(root->val);
65 inorderTraversal(root->right.get(), result);
66 }
67
68 // Graph class using adjacency list
69 class Graph {
70 private:
71 std::map<int, std::vector<int>> adjList;
72 bool directed;
73
74 public:
75 Graph(bool isDirected = false) : directed(isDirected) {}
76
77 void addEdge(int u, int v) {
78 adjList[u].push_back(v);
79 if (!directed) {
80 adjList[v].push_back(u);
81 }
82 }
83
84 // BFS traversal
85 std::vector<int> bfs(int start) {
86 std::vector<int> result;
87 std::queue<int> q;
88 std::set<int> visited;
89
90 q.push(start);
91 visited.insert(start);
92
93 while (!q.empty()) {
94 int current = q.front();
95 q.pop();
96 result.push_back(current);
97
98 for (int neighbor : adjList[current]) {
99 if (visited.find(neighbor) == visited.end()) {
100 visited.insert(neighbor);
101 q.push(neighbor);
102 }
103 }
104 }
105
106 return result;
107 }
108
109 // DFS traversal
110 void dfsUtil(int node, std::set<int>& visited, std::vector<int>& result) {
111 visited.insert(node);
112 result.push_back(node);
113
114 for (int neighbor : adjList[node]) {
115 if (visited.find(neighbor) == visited.end()) {
116 dfsUtil(neighbor, visited, result);
117 }
118 }
119 }
120
121 std::vector<int> dfs(int start) {
122 std::vector<int> result;
123 std::set<int> visited;
124 dfsUtil(start, visited, result);
125 return result;
126 }
127 };
128
129 int main() {
130 std::cout << "=== C++ Algorithms Demo ===\n\n";
131
132 // 1. Binary Search
133 std::vector<int> sortedArray = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
134 int target = 7;
135 int index = binarySearch(sortedArray, target);
136 std::cout << "Binary Search: Found " << target << " at index " << index << "\n\n";
137
138 // 2. BST operations
139 std::unique_ptr<TreeNode> bstRoot;
140 std::vector<int> values = {5, 3, 7, 2, 4, 6, 8};
141
142 for (int val : values) {
143 bstRoot = insertIntoBST(std::move(bstRoot), val);
144 }
145
146 std::vector<int> inorderResult;
147 inorderTraversal(bstRoot.get(), inorderResult);
148
149 std::cout << "BST Inorder Traversal: ";
150 for (int val : inorderResult) {
151 std::cout << val << " ";
152 }
153 std::cout << "\n\n";
154
155 // 3. Graph traversal
156 Graph graph(false); // Undirected graph
157 graph.addEdge(0, 1);
158 graph.addEdge(0, 2);
159 graph.addEdge(1, 3);
160 graph.addEdge(2, 4);
161 graph.addEdge(3, 5);
162 graph.addEdge(4, 5);
163
164 std::vector<int> bfsResult = graph.bfs(0);
165 std::cout << "Graph BFS from node 0: ";
166 for (int node : bfsResult) {
167 std::cout << node << " ";
168 }
169 std::cout << "\n";
170
171 std::vector<int> dfsResult = graph.dfs(0);
172 std::cout << "Graph DFS from node 0: ";
173 for (int node : dfsResult) {
174 std::cout << node << " ";
175 }
176 std::cout << "\n";
177
178 // 4. STL algorithms
179 std::vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};
180
181 // Sort
182 std::sort(numbers.begin(), numbers.end());
183 std::cout << "\nSorted numbers: ";
184 for (int num : numbers) {
185 std::cout << num << " ";
186 }
187 std::cout << "\n";
188
189 // Find
190 auto it = std::find(numbers.begin(), numbers.end(), 7);
191 if (it != numbers.end()) {
192 std::cout << "Found 7 in the vector\n";
193 }
194
195 // Count
196 int count = std::count(numbers.begin(), numbers.end(), 5);
197 std::cout << "Count of 5: " << count << "\n";
198
199 // Accumulate
200 int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
201 std::cout << "Sum of all numbers: " << sum << "\n";
202
203 return 0;
204 }