当前位置：首页 > news >正文

cpp c++面试常考算法题汇总

news 2025/7/31 9:25:23

THE LAST TIME

❝
The last time, I have learned

希望看到的人，能够对他的学习、工作有帮助，同时也希望有能力的人可以一起来完善此文档，让它可以发挥出更大的价值。

手写c++的unique_ptr

实际的 std::unique_ptr 还包括更多的功能，例如自定义删除器、数组支持等

template <typename T>
class unique_ptr {
public:
explicit unique_ptr(T* ptr = nullptr) : ptr_(ptr) {}
~unique_ptr() { delete ptr_; }
// 删除复制构造函数和复制赋值运算符
unique_ptr(const unique_ptr&) = delete;
unique_ptr& operator=(const unique_ptr&) =
delete;  // 提供移动构造函数和移动赋值运算符unique_ptr(unique_ptr&&
// other) noexcept : ptr_(other.ptr_) { other.ptr_ = nullptr; }
unique_ptr& operator=(unique_ptr&& other) noexcept {
    if (this != &other) {
        delete ptr_;
        ptr_ = other.ptr_;
        other.ptr_ = nullptr;
    }
    return *this;
}

T* operator->() { return ptr_; }
T& operator*() { return *ptr_; }

private:
T* ptr_;
};

手写c++的shared_ptr

template <typename T>
class tiny_shared_ptr {
public:
tiny_shared_ptr(T* ptr = nullptr) : _ptr(ptr), _count(new size_t(1)) {
    if (_ptr == nullptr) {
        *_count = 0;
    }
}

tiny_shared_ptr(const tiny_shared_ptr<T>& other) : _ptr(other._ptr), _count(other._count) {
    if (_ptr) {
        (*_count)++;
    }
}

tiny_shared_ptr<T>& operator=(const tiny_shared_ptr<T>& other) {
    if (this != &other) {
        release_source();
        _ptr = other._ptr;
        _count = other._count;
        if (_ptr) {
            (*_count)++;
        }
    }

    return *this;
}

T* operator->() const {
    return _ptr;
}

int use_count() const {
    return (_count ? *_count : 0);
}

~tiny_shared_ptr() {
    release_source();
}

private:
void release_source() {
    if (_count) {
        (*_count)--;
        if (*_count == 0) {
            delete _ptr;
            delete _count;
        }
    }
}

T* _ptr;
size_t* _count;
};

手写c++的string

#include <iostream>
#include <cstring>
using namespace std;

class MyString {
public:
MyString() : m_data(nullptr), m_size(0) {}
MyString(const char* str) {
    m_size = strlen(str);
    m_data = new char[m_size + 1];
    strcpy(m_data, str);
}

// 拷贝构造函数
MyString(const MyString& other) {
    m_size = other.m_size;
    m_data = new char[m_size + 1];
    strcpy(m_data, other.m_data);
}

// 移动构造函数
MyString(MyString&& other) {
    m_size = other.m_size;
    m_data = other.m_data;
    other.m_size = 0;
    other.m_data = nullptr;
}

~MyString() {
    if (m_data != nullptr) {
        delete[] m_data;
        m_data = nullptr;
        m_size = 0;
    }
}

MyString& operator=(const MyString& other) {
    if (this != &other) {
        if (m_data != nullptr) {
            delete[] m_data;
        }
        m_size = other.m_size;
        m_data = new char[m_size + 1];
        strcpy(m_data, other.m_data);
    }
    return *this;
}

const char* c_str() const {
    return m_data;
}

private:
char* m_data;
size_t m_size;
};

手撕完美转发

/**
   *  @brief  Forward an lvalue.
   *  @return The parameter cast to the specified type.
   *
   *  This function is used to implement "perfect forwarding".
   */
template<typename _Tp>
constexpr _Tp&&
forward(typename std::remove_reference<_Tp>::type& __t) noexcept
{ return static_cast<_Tp&&>(__t); }

/**
   *  @brief  Forward an rvalue.
   *  @return The parameter cast to the specified type.
   *
   *  This function is used to implement "perfect forwarding".
   */
template<typename _Tp>
constexpr _Tp&&
forward(typename std::remove_reference<_Tp>::type&& __t) noexcept
{
    static_assert(!std::is_lvalue_reference<_Tp>::value, "template argument"
    " substituting _Tp is an lvalue reference type");
    return static_cast<_Tp&&>(__t);
}

如何用c实现多态

定义基类的成员是函数指针，用于实现多态
派生类通过组合的方式（非继承）
派生类定义函数，构造时初始化对应函数到函数指针是上
通过同名的函数指针调用

#include <stdio.h>
// 基类结构体
struct Shape {
void (*draw)(struct Shape *);  // 1. 成员是函数指针，用于实现多态
};                                 // 派生类结构体 Circle
struct Circle {
struct Shape base;  // 基类 2. 通过组合的方式
int radius;
};
// 派生类结构体 Square
struct Square {
struct Shape base;  // 基类
int side;
};
// 基类的 draw 函数实现
void drawShape(struct Shape *shape) { printf("Drawing a shape\\n"); }
// 派生类 Circle 的 draw 函数实现
void drawCircle(struct Shape *shape) {
    struct Circle *circle = (struct Circle *)shape;
    printf("Drawing a circle with radius %d\\n", circle->radius);
}
// 派生类 Square 的 draw 函数实现
void drawSquare(struct Shape *shape) {
    struct Square *square = (struct Square *)shape;
    printf("Drawing a square with side %d\\n", square->side);
}
int main() {
    struct Circle circle = {{drawCircle}, 5};  // 3.定义并在类中初始化函数指针
    struct Square square = {{drawSquare}, 4};
    // 拿到各个结构体里的基类（作为一个成员变量）
    struct Shape *shapes[] = {(struct Shape *)&circle,
    (struct Shape *)&square};  // 4.通过指针调用
    for (int i = 0; i < 2; i++) {
        shapes[i]->draw(shapes[i]);
    }
    return 0;
}

手撕vector

#include<bits/stdc++.h>
using namespace std;
template<typename T>
class Allocator{
public :
//开辟释放内存
T* allocate(int size){
    return (T*)malloc(sizeof(T)*size);
}
T*deallocate(T* p){
    free(p);
}
//构造析构
void construct(T*p,const T &val){
    new (p)T(val);//定位new
}
void destory(T*p){
    p->~T();//调用析构函数
}
};
template<typename T,typename Alloc=Allocator<T> >
class vvecotr{
public :
//构造函数
vvecotr(int size=20){//多少个元素。
    alloc = new Allocator<T>();
    _begin = alloc->allocate(size);//开辟多少个内存
    _end = _begin+size;
    _now = _begin; 
}
//析构函数
~vvecotr(){
    free(_begin);
    delete alloc;
}
//拷贝构造函数
vvecotr(const vvecotr<T>&vec){//拷贝构造函数
    alloc = new Allocator<T>();
    int size = vec._end-vec._begin;
    _begin = alloc->allocate(size);
    _end = _begin+size;
    _now=_begin;

    T *p=vec._begin;
    for(;p!=vec._now;p++,_now++){
        alloc->construct(_now,*p);
    }
}
//拷贝赋值构造函数
vvecotr& operator=(const vvecotr<T>&vec){
    if(this==&vec)return *this;

    alloc->deallocate(_begin);

    alloc = new Allocator<T>();
    int size = vec._end-vec._begin;
    _begin = alloc->allocate(size);
    _end = _begin+size;
    _now=_begin;

    T *p=vec._begin;
    for(;p!=vec._now;p++,_now++){
        alloc->construct(_now,*p);
    }

    return *this;
}

vvecotr( vvecotr<T>&&vec){
    cout<<"vvecotr( vvecotr<T>&&vec){"<<endl;
    alloc = vec.alloc;
    _begin=vec._begin;
    _now = vec._now;
    _end = vec._end;
    vec._begin=vec._end=vec._now=nullptr;
    vec.alloc=nullptr;
}
vvecotr & operator=( vvecotr<T>&&vec){
    //不会出现自赋值
    alloc = vec.alloc;
    _begin=vec._begin;
    _now = vec._now;
    _end = vec._end;
    vec._begin=vec._end=vec._now=nullptr;
    vec.alloc=nullptr;

    return *this;
}

void push_back(const T&val){
    if(_now==_end){
        resize();
    }
    alloc->construct(_now,val);
    _now++;
}
void pop_back(){
    if(_now != _begin){
        alloc->destory(_now--);
    }
}
T& operator[](int index){

    return _begin[index];
}
bool empty(){
    return _now==_begin;
}
int size(){
    return _now-_begin;
}
void show(){
    T*p =_begin;
    while(p!=_now){
        cout<< *p <<" ";
        p++;
    }
    cout<<endl;
}
private:
T* _begin ;
T* _now;
T* _end;
Alloc *alloc;

void resize(){
    int size=_end-_begin;
    T *p=alloc->allocate(size*2);
    for(int i=0;i<size;i++){
        p[i]=_begin[i];
    }
    alloc->deallocate(_begin);
    _begin = p;
    _now=p+size;
    _end=p+size*2;
}
};

vvecotr<int> get(){
    vvecotr<int>vec(50);
    for(int i=0;i<=5;i++)vec.push_back(i);
    return vec;   
}
int main(){
    vvecotr<int>vec(50);
    for(int i=0;i<=15;i++)vec.push_back(i);
    vec.show();
   
    

    //测试右值拷贝构造
    // vvecotr<int> a = std::move(vec);
    // cout<<a.size()<<endl;

    //测试右值拷贝赋值
    // vvecotr<int>a;
    // a=get();
    // a.show();
    return 0;
}

手撕线程池

#include <iostream>
#include <unistd.h>
#include <queue>
#include <vector>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <functional>

using namespace std;

class ThreadPool {
public:
ThreadPool(size_t numThreads) : stop(false) {
    for (size_t i = 0; i < numThreads; ++i) {
        threads.emplace_back([this] {
            while (true) {
                std::function<void()> task;
                {
                    std::unique_lock<std::mutex> lock(queueMutex);  // lock
                    condition.wait(lock, [this] { return stop || !tasks.empty(); });
                    if (stop && tasks.empty()) {
                        return;
                    }
                    task = std::move(tasks.front());
                    tasks.pop();
                }
                task();
            }
        });
    }
}

template <class F, class... Args>
void enqueue(F&& f, Args&&... args) {
    {
        std::unique_lock<std::mutex> lock(queueMutex);
        tasks.emplace([f, args...] { f(args...); });
    }
    condition.notify_one();  // wake up thread
}

~ThreadPool() {
    {
        std::unique_lock<std::mutex> lock(queueMutex);
        stop = true;
    }
    condition.notify_all();
    for (std::thread& thread : threads) {
        thread.join();
    }
}

private:
std::vector<std::thread> threads;
std::queue<std::function<void()>> tasks;
std::mutex queueMutex;
std::condition_variable condition;
bool stop;
};

void printNumber(int num) {
    sleep(5);  // ssimulate operational implementation
    std::cout << num << std::endl;
}

int main() {
    ThreadPool pool(4);

    // submit tasks to thread pool
    for (int i = 0; i < 10; ++i) {
        pool.enqueue(printNumber, i);
    }

    // wait for all tasks to be completed
    std::this_thread::sleep_for(std::chrono::seconds(1));

    return 0;
}