Programming

STL

String

strcmp() is case-sensitive.
Example: "Hello" and "hello" are considered different.
strcat() modifies the first character array by appending the second string to it.
The first array must have enough allocated space to hold the result.
You cannot assign to a character array after declaration.
Example (invalid):
```
char a[10];
a = "Hello";   // ❌ not allowed
```
- But you can initialize a character array during declaration:
```
char a[10] = "Hello";   // ✅ allowed
```
- You can assign a std::string after declaration:
```
std::string s;
s = "Hello";   // ✅ allowed
```
- strlen() take $O(n)$ time, where size() take $O(1)$ time.
- 100 > 99 as number, but "99" > "100" as string

String Buffer (Input Safety)

When taking input after cin >>, leftover newline can break getline().

cin >> x;
cin.ignore();          // clears leftover '\n'
getline(cin, s);       // safe input into string buffer

`cin.ignore()`

Removes leftover characters from input buffer (usually '\n').
Commonly used before getline().

cin.ignore(1000, '\n');   // ignores up to 1000 chars or until newline

`find_if()`

Used to find the first element that satisfies a condition.

vector<int> v = {1, 3, 5, 8, 10};

auto it = find_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;   // find first even number
});

if (it != v.end()) {
    cout << "Found: " << *it << endl;
}

Pair

Pair Destructuring (Structured Binding)

Used to unpack pair values easily.

pair<int, string> p = {1, "Hello"};
auto [id, name] = p;   // destructuring
cout << id << " " << name << endl;

Stack & Queue

A stack/queue is not a standalone container; it is a container adapter built on top of another underlying container.

stack<int>                    s1;  // default: uses deque
stack<int, vector<int>>       s2;  // uses vector
stack<int, list<int>>         s3;  // uses list

Underlying Container Comparison

deque
- O(1) push/pop from both ends
- Ideal for stack (this is the default)
vector
- O(1) push/pop from the back
- But resizing can take O(n), so sometimes slower
list
- O(1) insertion/removal
- But higher memory overhead (extra pointer per node)

top()/front() returns a reference (T&), So you can read and write the top/front element.

Why `pop()` doesn't return a value

In C++ STL stack, pop() does not return the removed element. Because
- Avoids unnecessary copying. You only copy when you explicitly need it
- Keeps the interface simple and efficient

Why iterating using `size()` doesn't work properly

Wrong approach:

for (int i = 0; i < s.size(); i++) {
    cout << s.top() << endl;
    s.pop();
}

Problem:
- s.size() decreases every time you call pop()
- So the loop condition becomes inconsistent
- Some elements may be skipped

Correct approach:

Option 1: Store initial size

int n = s.size();
for (int i = 0; i < n; i++) {
    cout << s.top() << endl;
    s.pop();
}

Option 2: Use while loop (best)

while (!s.empty()) {
    cout << s.top() << endl;
    s.pop();
}

This works correctly because it continues until the stack is empty.

Vector

The vector object itself (the control structure) is stored:
- On the stack if it’s a local variable
- On the heap if you used new
But the elements it manages are stored on the heap (dynamic memory)
Vector object usuallay contains 3 pointers([start_ptr, end_ptr, capacity_ptr]), which stores in stack, the element of the vector stores in heap

[] vs .at()

Feature	`[]`	`.at()`
Bounds check	❌ No	✅ Yes
Performance	Faster	Slightly slower
Safety	Unsafe	Safe (throws error)

How STL handles vector size

A std::vector internally tracks:

size → number of actual elements
capacity → allocated memory space

When you add elements (push_back):

If there is space:

Just adds element → O(1)

If full:

Allocates new memory (usually 2× capacity)
Copies/moves elements
Frees old memory → O(n)

reserve(n)

Pre-allocates memory for at least n elements
Does NOT change size

vector<int> v;
v.reserve(100);  // capacity becomes ≥ 100

It increases memory allocation

Differences between `+xx` and `x++`

`++x` Pre-Increment

First increments the value
Then returns the updated value

int x = 5;
int y = ++x;
cout<<x<<endl; // 6
cout<<y<<endl; // 6

`x++` Post-Increment

First returns the current value
Then increments the value

int x = 5;
int y = x++;
cout<<x<<endl; // 6
cout<<y<<endl; // 5

If used alone, both behave same, difference only matters inside expressions.

Character Array vs String

Character Array

A character array is simply an array that holds characters. It is a collection of char elements stored in contiguous memory.

char arr[5] = {'H', 'e', 'l', 'l', 'o'};

Can store individual characters.
Does not automatically include a null terminator ('\0'), unless explicitly added.
Example with null terminator:

char arr[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

Size must be defined (static arrays) or managed dynamically (dynamic arrays).
Can be modified element by element.

Use cases: Useful for low-level manipulation of characters, buffer storage, or embedded systems.

String

A string is a sequence of characters terminated by a null character ('\0') in languages like C. In higher-level languages (e.g., C++, Java, Python), a string is an object with built-in methods for manipulation.

Key points in C:

Declared as a character array with null termination:

char str[] = "Hello";  // Compiler automatically adds '\0'

Functions like strlen(), strcpy(), strcmp() can be used for manipulation.
The null character ('\0') marks the end of the string, not just the array size(in character array). It is very usefull when you don't know the size of the string. In memory, it stored like:
```
H e l l o \0
0 1 2 3 4 5
```
More convenient than character arrays for text processing because standard library functions recognize the null terminator.

In higher-level languages:

Strings are objects or types with many built-in methods:
- C++: std::string
- Python: str
- Java: String
They often manage memory automatically and provide easy concatenation, slicing, and searching.

Differences at a glance

danger

char arr[5] = {'H', 'e', 'l', 'l', 'o'}; // size is 5
char str[] = "Hello";  // size is 6
string str2 = "Hello";  // size is 5

strlen only count charecter.

strlen(str) // size is 5
sizeof(str) // size is 6

Feature	Character Array	String
Definition	Array of chars	Sequence of chars ending with `'\0'` (C) or string object (high-level languages)
Null terminator	Optional	Mandatory in C
Memory	Fixed size unless dynamic	Managed by language (dynamic in high-level languages)
Manipulation	Manual (loop-based)	Built-in functions or methods
Example	`char arr[5] = {'H','e','l','l','o'};`	`char str[] = "Hello";`

Implementation of `strcpy()`

int i = 0;
while (src[i] != '\0') {
    dest[i] = src[i];
    i++;
}
dest[i] = '\0';

Don't forget to assign \0 at the end.

Loop

Use reference to modify array item in foreach

for (int& x : v) { 
  x = x * 2;      
}

end() refer addresses of the item appear after last item.

for (auto it = v.begin(); it != v.end(); it++) {
  cout << *it << " ";
}

Similarly rbegin() refer the address of item appear befor first item.

When you keep adding elements to a vector, it may repeatedly reallocate(twice its capacity) memory and copy/move elements. Using reserve(n) avoids that if you know the approximate size in advance.

reserve()
- Allocates memory for at least 5 elements
- But does NOT create any elements
- With index, you're writing directly into that memory. The data happens to stay there. But the vector does not know these elements exist, no constructors were called, so indexing wont' work, use push_back()
shrink_to_fit reduce the capacity
To clear the memory completly use both clear() and shrink_to_fit() method.

Question

What happen if \0 is inside string/characeter array?

Case 1: char arr[] = "hel\0lo";

It is stored in memory like:

h e l \0 l o \0
0 1 2  3 4 5 6

"hel\0lo" has an implicit null terminator added by the compiler, so the total size becomes 7.
If you print it using:

cout << arr;

it prints:

hel

because cout treats char* as a C-string and stops at the first \0.

Memory size:

sizeof(arr) // 7

String length (until first null):

strlen(arr) // 3

Case 2: string str = "hel\0lo";

It is stored in memory like:

h e l
0 1 2

The constructor used is:

string(const char* s)

This constructor determines the length using strlen(), which stops at the first \0.
So only "hel" is copied into the std::string.

Memory:

h e l
0 1 2

Size:

str.size() // 3

Printing:

cout << str;

Output:

hel

Extra (Important Trick)

If you explicitly give the length:

string str("hel\0lo", 6);

Then the string actually stores the null character:

h e l \0 l o
0 1 2  3 4 5

Now:

str.size() // 6

and printing shows:

hello

(The \0 exists but is invisible.)

Summary

Code	Stored Size	Printed Output
`char arr[] = "hel\0lo"`	7 bytes	`hel`
`string str = "hel\0lo"`	3 chars	`hel`
`string str("hel\0lo",6)`	6 chars	`hello`

What's the problem with fgets?

Problem

fgets() reads the newline character \n as part of the input when the user presses Enter.

Example:

char str[100];
fgets(str, sizeof(str), stdin);
printf("%s", str);

If the user inputs:

hello

The actual content stored in memory becomes:

h e l l o \n \0
0 1 2 3 4  5  6

So the string is:

"hello\n"

This can cause problems when:

comparing strings
formatting output
processing text

Example:

strcmp(str, "hello")  // ❌ not equal

because the string is actually "hello\n".

If input size is bigger than the defined array size, it will ignore the \n.

How to Resolve It

Remove the newline character after reading input.

Method 1 (Recommended)

str[strcspn(str, "\n")] = '\0';

Explanation:

strcspn(str, "\n") finds the index of \n
It replaces it with \0.

Example:

char str[100];
fgets(str, sizeof(str), stdin);
str[strcspn(str, "\n")] = '\0';

Method 2

int len = strlen(str);
if (len > 0 && str[len - 1] == '\n')
    str[len - 1] = '\0';

Summary

Function	Behavior
`gets()`	❌ unsafe (removed from C)
`scanf("%s")`	stops at whitespace
`fgets()`	reads the newline `\n`
Solution	remove `\n` manually

Why Node* head, current; behave differently

This is a common mistake.

Node* head, current;

This means:

head → pointer to Node (Node*)
current → actual Node object (Node)

Because * applies only to the variable it’s attached to.

Correct way if both should be pointers:

Node *head, *current;

Now:

head → pointer
current → pointer

Why this matters

If you do:

current = head;

Works only if both are pointers
Otherwise → type mismatch error

STL​

String​

String Buffer (Input Safety)​

cin.ignore()​

find_if()​

Pair​

Stack & Queue​

Underlying Container Comparison​

Why pop() doesn't return a value​

Why iterating using size() doesn't work properly​

Vector​

Differences between +xx and x++​

++x Pre-Increment​

x++ Post-Increment​

Character Array vs String​

Character Array​

String​

Differences at a glance​

Implementation of strcpy()​

Loop​

Question​

STL

String

String Buffer (Input Safety)

`cin.ignore()`

`find_if()`

Pair

Stack & Queue

Underlying Container Comparison

Why `pop()` doesn't return a value

Why iterating using `size()` doesn't work properly

Vector

Differences between `+xx` and `x++`

`++x` Pre-Increment

`x++` Post-Increment

Character Array vs String

Character Array

String

Differences at a glance

Implementation of `strcpy()`

Loop

Question