# 12/18 questions
1. Does stl's iterator only support forward access?
Input Iterator: istream's iterator
only forward
**Output Iterator:**
only forward
```
std::ostream_iterator<int> out_it (std::cout, " ");
*out_it = 10; // Output iterator for standard output
out_it++;
*out_it = 20;
// Using output iterator with an algorithm
std::vector<int> vec = {1, 2, 3, 4, 5};
std::copy(vec.begin(), vec.end(), out_it);
print result: 10 20 1 2 3 4 5
```
**Bidirectional Iterators:**
for list<>, set<>
**Random Access Iterator:**
support for vector<>, deque<>
Each higher-level iterator (for example, a random access iterator) supports all the operations of the lower-level iterators. For example, random access iterators support all the features of input, output, forward, and bidirectional iterators simultaneously.
2. Does std::mutex support synchonization between **processes**?
**No,** std::mutex and other synchronization primitives such as std::condition_variable in the C++ standard library are designed for multi-thread synchronization within the same process, not for multi-process synchronization.
For multi-process synchronization, you need to use the inter-process communication (IPC) mechanism provided by the operating system, such as:
**Named Pipes:** Allow unrelated processes to communicate.
**Shared Memory:** Different processes can access the same memory area. When using shared memory, you may need to use semaphores or mutexes, but these locks must be able to work across processes, such as POSIX sem_t or Windows' CreateMutex.
**Message Queues:** Allow processes to communicate in the form of messages.
**Semaphores:** Mainly used to limit access to resources. They can be POSIX semaphores or system-specific implementations.
**Sockets: **widely used for network communication and can also be used for inter-process communication on the same machine.
3. implementation of container **find** function
```
template <typename Iterator, typename T>
Iterator find(Iterator begin, Iterator end, const T& value) {
while (begin != end) {
if (*begin == value) {
return begin;
}
++begin;
}
return end;
}
```
# Design of shared pointer
```
#include <iostream>
template <typename T>
class SharedPtr {
private:
T* ptr; // Actual pointer to the resource
unsigned* count; // Reference count
public:
// Constructor
explicit SharedPtr(T* p = nullptr) : ptr(p) {
count = new unsigned(1); // Initialize reference count
}
// Copy Constructor
SharedPtr(const SharedPtr<T>& other) : ptr(other.ptr), count(other.count) {
(*count)++; // Increment reference count
}
// Assignment Operator
SharedPtr<T>& operator=(const SharedPtr<T>& other) {
if (this != &other) { // Avoid self-assignment
// Decrement the old reference count
// If reference becomes zero, delete the old data
if (--(*count) == 0) {
delete ptr;
delete count;
}
// Copy data from the other shared pointer
ptr = other.ptr;
count = other.count;
(*count)++; // Increment the new reference count
}
return *this;
}
// Destructor
~SharedPtr() {
// Decrement the reference count
// If reference becomes zero, delete the data
if (--(*count) == 0) {
delete ptr;
delete count;
}
}
// Dereference operator
T& operator*() const {
return *ptr;
}
// Arrow operator
T* operator->() const {
return ptr;
}
};
int main() {
SharedPtr<int> sp1(new int(10));
std::cout << "sp1: " << *sp1 << std::endl;
{
SharedPtr<int> sp2 = sp1; // Copy constructor
std::cout << "sp2: " << *sp2 << std::endl;
} // sp2 goes out of scope
std::cout << "sp1: " << *sp1 << std::endl; // sp1 is still valid
return 0;
}
```
note: "function const" means this function cannot modify **any member data**
note: "explicit contructor" means contructor can't be called without explicityly mentioning the type.
e.g.
```
SharePointer<int> sp = 10; // implicit conversion
```
# Difference between C and C++
1. Language Paradigm:
C: procedural language, focusing on function-driven approach.
C++: Supports both procedural and object-oriented programming (OOP).
2. Data Abstraction and Encapsulation:
C: Offers limited support for data abstraction and does not support encapsulation. It uses structures (struct) for data grouping but cannot bundle data and functions together.
C++: Provides extensive support for data abstraction and encapsulation through classes and objects, allowing data and the functions that operate on that data to be bundled.
3. Standard Template Library (STL)
4. Function Overloading and Operator Overloading:
C: Does **not support** **function overloading** or **operator overloading**.
C++: Supports both
5. Memory Management:
C: Provides manual memory management, using functions like malloc(), calloc(), realloc()(for resize a previously allocated memory block), and free().
C++: new/delete and smart pointers
6. References:
C: Only supports pointers.
C++: both **pointers** and **references**
7. Namespace:
C: Does not have namespaces, which can lead to name collisions in large projects.
C++: Supports namespaces, preventing **name collisions**.
8. Exception Handling:
C: **Lacks built-in exception handling**; errors are typically handled using other mechanisms like return codes.
C++: Provides robust exception handling using try, catch, and throw.
9. Templates:
C: Does not support templates.
C++: Supports templates, allowing generic programming (functions and classes can be defined with a placeholder for data types to be **specified later**).
**C struct v.s. C++ struct:**
**C Struct:**
1. Used for grouping different data types into a single unit.
2. C structs cannot have functions as members. They are purely used for data storage.
3. Access Modifiers: By default, all members of a C struct are public, and C does **not support** explicit access modifiers like **private** or **protected**.
4. C structs do not support inheritance or polymorphism, which are key features of object-oriented programming.
**C++ Struct:**
1. In C++, a struct can do everything it can in C, such as grouping different data types.
2. Unlike C, C++ structs can have both data members and **function members**.
3. Access Modifiers: C++ structs support access modifiers (public, private, protected).
4. The default struct access modifier for member variables and methods is **public** (which is the key **difference from C++ classes**, where the default is **private**).
5. In **C++**, **structs can inherit** from other structs or classes, and they can also be used as base structures for inheritance. They support polymorphism, which means you can use pointers and references to a struct to achieve dynamic polymorphism **(virtual function)**.
6. Constructors and Destructors: C++ structs can have **constructors** and **destructors**, which are not possible in C structs.
# VTable
```
class Base {
public:
virtual void foo() { std::cout << "Base::foo" << std::endl; }
};
class Derived : public Base {
public:
void foo() override { std::cout << "Derived::foo" << std::endl; }
};
```
The compiler creates a vtable for both Base and Derived.
Base's vtable points to Base::foo,
while Derived's vtable points to Derived::foo.
When a Derived object is created, its vptr points to the vtable of Derived.
If a Base pointer points to a Derived object and calls foo, the call will be resolved to Derived::foo at runtime using the vtable.
# Smart Pointers
`std::unique_ptr:`
Allows exactly **one owner** of the underlying pointer.
It **cannot be copied** to another unique_ptr, **passed by** value to a function, or **used** in any **standard container** that requires **copying**.
`std::shared_ptr:`
Allows **multiple owners** of the same pointer (**reference counting** is used).
The memory is deallocated when the last shared_ptr owning the resource is destroyed or reset.
`std::weak_ptr`
A **non-owning** smart pointer that references **an object managed by std::shared_ptr.**
It is used to **break circular references** of shared_ptr objects.
It does **not contribute to** the **reference count** of shared_ptr. To use the object it points to, a weak_ptr must be converted to a shared_ptr using lock().
# New Features after C++ 11
**Auto type deduction:**
Allows the compiler to automatically deduce the type of a variable from its initializer.
`auto x = 3;`
___
**Lambda Expressions:**
Enable defining anonymous functions (lambdas) directly in the code.
```
auto add = [](int a, int b) { return a + b; };
int sum = add(5, 3); // sum = 8
```
___
**Range-based for Loop:**
Simplifies iterating over elements of a container.
```
std::vector<int> v = {1, 2, 3, 4, 5};
for (auto i : v) {
std::cout << i << " ";
}
```
___
**nullptr:**
more type-safe than NULL.
For example, a function overloaded for both **int** and **pointer** types could be called with **NULL** and it would resolve to the int overload
___
**Strongly Typed Enums (enum class):**
Strongly typed and scoped enumerations, providing better type safety.
`enum class Color { Red, Green, Blue };
Color c = Color::Red;`
Traditional enums in C++ can implicitly convert to **int**, leading to errors if wrongly used. Also, the enumerator names leak into the enclosing scope, which can cause **name clashes**.
-enum class creates enums that are strongly-typed and scoped. They do not implicitly convert to int.
-The enumerator names are local to the enum and do not pollute the enclosing scope.
___
**Rvalue References and Move Semantics:**
Allows resources from temporary objects (rvalues) to be moved rather than copied.
`std::vector<int> vec1 = {1, 2, 3};`
`std::vector<int> vec2 = std::move(vec1); // move vec1's resources to vec2`
In C++, an rvalue is an expression that does **not have a memory address** in the program. It's a temporary value that is typically used in a read-only context.
rvalue sample:
```
int getValue() {
return 5;
}
int main() {
int a = getValue(); // 'getValue()' returns an rvalue
int b = a + 2; // 'a + 2' is an rvalue
int c = 42; // '42' is an rvalue
The above rvalues are used to initialize or assign values to lvalues (variables a, b, and c)
return 0;
}
```
move semantics sample:
```
class DynamicArray {
int* data;
public:
DynamicArray(const DynamicArray& other) { // Copy constructor
data = new int[...]; // Allocates memory and copies data from 'other'
}
DynamicArray(DynamicArray&& other) : data(other.data) { // Move constructor
other.data = nullptr; // Leaves 'other' in a safely destructible state
}
~DynamicArray() {
delete[] data;
}
};
```
This is particularly useful for temporary objects (rvalues), where deep copying is often unnecessary and inefficient.
LValue:
1. Addressable: The memory address of an lvalue can be obtained using the address-of operator (&).
2. Assignable: If an lvalue is not const, you can assign a value to it. For example, if x is an int variable (and thus an lvalue), you can assign a value to it like x = 5.
3. Persistence: Lvalues correspond to memory locations that persist beyond the expression that uses them.
___
**Uniform Initialization and Initializer Lists:**
A uniform syntax for initialization and initializer lists for containers.
`std::vector<int> v {1, 2, 3, 4, 5}; // uniform initialization`
___
**Smart Pointers**
___
**Concurrency Support:**
New features to support multi-threading.
`#include <thread>`
`void hello() {
std::cout << "Hello, Concurrency!" << std::endl;
}
`
`
std::thread t(hello); // create a thread to execute
`
`
t.join();//wait for the thread to continue
`
___
**Static Assertions (static_assert Compile-time assertions.**
`static_assert(sizeof(int) == 4, "Integers are not 4 bytes");
`
___
**Explicitly Deleted and Defaulted Functions:**
Allows explicitly defining default and deleted special member functions.
```class MyClass {
public:
MyClass() = default;//ensure existence of contructor
MyClass(const MyClass&) = delete;//mean class cannot be copied
};
```
___
**New String Literals:**
New ways to represent string literals, like raw string literals.
```
auto raw_string = R"(Line1
Line2
Line3)";
```
old:
`std::string traditional_path = "C:\\Program Files\\MyApp\\config.txt";
std::string traditional_multi_line = "First Line\nSecond Line\nThird Line";`
`\\` represent single backslash, `\n` means a new line
new:
std::string raw_path = R"(C:\Program Files\MyApp\config.txt)";
std::string raw_multi_line = R"(First Line
Second Line
Third Line)";
# General Questions
**Why virtual destructor**
It allows deletion hierarchically. If no virtual detructor in base class and when a base class pointer points to derived class, calling base class' destructor is default.
**Can we call a virtual method in a class constructor**
When a base class constructor is called, the derived class's constructor has not yet executed, so the derived class's virtual method may lead to undefined behavior.
**When vtable is ready**
During runtime, when a virtual function is called on an object, the vtable is consulted to determine which specific version of the virtual function to execute.
The virtual table (vtable) for a C++ class is typically ready at compile time.
Each class that contains at least one virtual function has its own vtable.
In summary, the vtable is **ready at compile time** and **is associated with each clas**s that has virtual functions, allowing dynamic dispatch of these functions **at runtime.**
**Why map choose red-black tree over other self balance tree**
1. Red-black trees provide predictable and consistent performance
2. Red-black trees are well-suited for both **insertions** and **deletions**
**General Ways to handle collision in hash table**
1. **Chaining** (Separate Chaining):
<ins>Description</ins>:
Each slot of the hash table contains a pointer to **a linked list** that stores all the elements mapped to the same hash value.
<ins>Advantages</ins>:
Simple to implement, and the hash table can never fill up (except for the limits of memory).
Disadvantages:
The performance can degrade if the linked lists become too long (i.e., if the hash function does not distribute elements well).
2. **Open Addressing**:
**Linear Probing:**
The algorithm checks the next slot, and so on, until an empty slot is found.
Advantages: Easy to implement and saves space over chaining.
Disadvantages: Can lead to "clustering" where a number of consecutive elements get filled up, reducing efficiency.
**Quadratic Probing:**
Similar to linear probing but the interval between probes increases quadratically.
Reduces clustering problem but does not eliminate it.
**Double Hashing:**
Uses a second hash function to calculate the probe interval.
More **effective** at reducing clustering **than linear** or **quadratic probing**.
3. **Rehashing**:
When the **load factor** of the table exceeds a certain threshold, a new, larger hash table is created, and all elements are rehashed to the new table.
**Is it possible to cause the memory leak with smart pointers**
1. Circle reference
```
struct Node {
std::shared_ptr<Node> next;
};
std::shared_ptr<Node> node1 = std::make_shared<Node>();
std::shared_ptr<Node> node2 = std::make_shared<Node>();
node1->next = node2;
node2->next = node1; // Circular reference
```
2. Raw pointer conversion
```
std::shared_ptr<int> smartPtr = std::make_shared<int>(42);
int* rawPtr = smartPtr.get(); // Raw pointer without ownership
```
**In file 1 we have a static variable defined, can we use this in file 2?**
No, static is in file scope.
`extern` identifier can be used for this purpose.
**Find top 10 integers in a large list that can not be loadded into memory**
Separate into sections, sort separately
**For multithreading and multiprocessing, how do you debug a random crash**
1. Reproduce the Issue if Possible
2. Thread safe check/datastructure
3. log output
4. Thread Isolation
5. tests using tools like ThreadSanitizer
**What is pure virtual in C++**
```
class Shape {
public:
virtual void draw() const = 0;
};
```
Purpose: Abstraction and Encapsulation
Impact: A function that should be implemented by **all** it's derived classes
**What is core dump in C**
What: a file generated when programs crash
How: ```ulimit -c unlimited```
sets the size limit of core dumps to unlimited, ensuring it generated for **any crash**.
The file can be analyze by GDB.
**What is segmentation fault**
Happen when
1. Illegal Memory Access
```
int a[2];
a[2] = 1;
```
2. Buffer Overflows and Pointer Errors:
```
int* a;
int *b=nullptr;
delete a;
delete b;
```
3. Debugging Segmentation Faults: Tools like debuggers (e.g., **GDB** in Unix/Linux) and memory checkers (e.g., **Valgrind**) can be very helpful in identifying where and why a segmentation fault occurs.
Sign in with Wallet
Connect another wallet