C++/Linux 面试小抄

Posted on Edited on

Linux 面试

C++ 面试

new features

C++11

1
2
3
4
5
6
7
8
9
10
Core language features

    auto and decltype
    rvalue references
    move constructors and move assignment operators
    attributes
    lambda expressions
    range-for (based on a Boost library)
    static_assert (based on a Boost library) 
    smart pointers

语法

new vs malloc

1
2
3
4
5
6
7
8
9
10
11
12
class A{...}
A * ptr = new A;
A * ptr = (A *)malloc(sizeof(A)); //需要显式指定所需内存大小sizeof(A); 需要将void * cast 为 A* type
// new/delete would call the constructor of class A

// For array
A * ptr = new A[10];//分配10个A对象
// 使用new[]分配的内存必须使用delete[]进行释放
delete [] ptr;

int * ptr = (int *) malloc( sizeof(int)* 10 );//分配一个10个int元素的数组
free(ptr)

STL 非官方实现

实现一个unique_ptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
template<typename T>
class MyUniquePtr
{
public:
   explicit MyUniquePtr(T* ptr = nullptr)
        :mPtr(ptr)
    {}

    ~MyUniquePtr()
    {
        if(mPtr)
            delete mPtr;
    }

    MyUniquePtr(MyUniquePtr &&p) noexcept;
    MyUniquePtr& operator=(MyUniquePtr &&p) noexcept;

    MyUniquePtr(const MyUniquePtr &p) = delete;
    MyUniquePtr& operator=(const MyUniquePtr &p) = delete;

    T* operator*() const noexcept {return mPtr;}
    T& operator->()const noexcept {return *mPtr;}
    explicit operator bool() const noexcept{return mPtr;}

    void reset(T* q = nullptr) noexcept
    {
        if(q != mPtr){
            if(mPtr)
                delete mPtr;
            mPtr = q;
        }
    }

    T* release() noexcept
    {
        T* res = mPtr;
        mPtr = nullptr;
        return res;
    }
    T* get() const noexcept {return mPtr;}
    void swap(MyUniquePtr &p) noexcept
    {
        using std::swap;
        swap(mPtr, p.mPtr);
    }
private:
    T* mPtr;
};

template<typename T>
MyUniquePtr<T>& MyUniquePtr<T>::operator=(MyUniquePtr &&p) noexcept
{
    swap(*this, p);
    return *this;
}

template<typename T>
MyUniquePtr<T> :: MyUniquePtr(MyUniquePtr &&p) noexcept : mPtr(p.mPtr)
{
    p.mPtr == NULL;
}

实现一个shared_ptr

这件事情主要在于实现一个带有引用计数的指针, 并支持父类子类的转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
template <typename T>
class mySmartPtr
{
public:
    // 构造函数 默认为空
    mySmartPtr(): pointer(0), counter(0)
    {
    } 
 
    // 形参为指针的构造函数
    mySmartPtr(T* p): pointer(0), counter(0){
        *this = p;
    }
 
    // 复制构造函数
    mySmartPtr(const mySmartPtr<T> &p): 
    pointer(p.pointer), counter(p.counter){
        Increase();
    }
 
    ~mySmartPtr(){
        Decrease();
    }
 
    // 指针的赋值操作符，类型不同，不是自赋值
    mySmartPtr operator=(T* p){
        Decrease();
        if (p){
            pointer = p;
            counter = new int(1);
        }
        else {
            pointer = 0;
            counter = 0;
        }
        return *this;
    }
 
    // 智能指针赋值操作符
    mySmartPtr operator=(mySmartPtr<T> &p){
        // 处理自赋值
        if (this != &p){
            Decrease();
            pointer = p.pointer;
            counter = p.counter;
            Increase();
        }
        return *this;
    }
 
    operator bool() const{
        return counter != 0;
    }
 
    // ×操作符重载
    T* operator*() const{
        return this;
    }
 
    // ->操作符重载
    T* operator->() const{
        return pointer;
    }
 
    // 返回底层指针
    int getPtrPointer() const{
        return *pointer;
    }
 
    // 返回引用计数
    int getPtrCounter() const{
        return *counter;
    }
 
    // 处理父类子类的情况， ptr<derived>不能访问 ptr<based>的内部对象
    template<typename C> friend class mySmartPtr;
 
    template<typename C> 
    mySmartPtr(const mySmartPtr<C> &p): 
        pointer(p.pointer), counter(p.counter){
            Increase();
        }
 
    template<typename C>
    mySmartPtr<T> & operator=(const mySmartPtr<C> &p){
        Decrease();
        pointer = p.pointer;
        counter = p.counter;
        Increase();
        return *this;
    }
 
    // 处理内部使用 dynamic_cast做判断的转换，失败则空指针
    template<typename C>
    mySmartPtr<C> Cast() const{
        C* converted = dynamic_cast<C*>(pointer);
        mySmartPtr<C> result;
        if (converted){
            result.pointer = converted;
            result.counter = counter;
            result.Increase();
        }
        return result;
    }
 
private:
    T*      pointer;
    int*    counter;
 
    void Increase(){
        if (counter) 
            ++*counter;
    }
 
    void Decrease(){
        if (counter && --*counter == 0){
            delete pointer;
            delete counter;
            counter = 0;
            pointer = 0;
        }
    }
 
};

C style 多态

内存池和alloc 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#ifndef _MEMORY_POOL_H_
#define _MEMORY_POOL_H_

#include <stdint.h>
#include <mutex>

template<size_t BlockSize, size_t BlockNum = 10>
class MemoryPool
{
public:
	MemoryPool()
	{
		std::lock_guard<std::mutex> lk(mtx); // avoid race condition

		// init empty memory pointer
		free_block_head = NULL;
		mem_chunk_head = NULL;
	}

	~MemoryPool()
	{
		std::lock_guard<std::mutex> lk(mtx); // avoid race condition

		// destruct automatically
		MemChunk* p;
		while (mem_chunk_head)
		{
			p = mem_chunk_head->next;
			delete mem_chunk_head;
			mem_chunk_head = p;
		}
	}

	void* allocate()
	{
		std::lock_guard<std::mutex> lk(mtx); // avoid race condition

		// allocate one object memory

		// if no free block in current chunk, should create new chunk
		if (!free_block_head)
		{
			// malloc mem chunk
			MemChunk* new_chunk = new MemChunk;
			new_chunk->next = NULL;

			// set this chunk's first block as free block head
			free_block_head = &(new_chunk->blocks[0]);

			// link the new chunk's all blocks
			for (int i = 1; i < BlockNum; i++)
				new_chunk->blocks[i - 1].next = &(new_chunk->blocks[i]);
			new_chunk->blocks[BlockNum - 1].next = NULL; // final block next is NULL
			
			if (!mem_chunk_head)
				mem_chunk_head = new_chunk;
			else
			{
				// add new chunk to chunk list
				mem_chunk_head->next = new_chunk;
				mem_chunk_head = new_chunk;
			}
		}

		// allocate the current free block to the object
		void* object_block = free_block_head;
		free_block_head = free_block_head->next; 

		return object_block;
	}

	void* allocate(size_t size)
	{
		std::lock_guard<std::mutex> lk(array_mtx); // avoid race condition for continuous memory

		// calculate objects num
		int n = size / BlockSize;

		// allocate n objects in continuous memory
		
		// FIXME: make sure n > 0
		void* p = allocate();

		for (int i = 1; i < n; i++)
			allocate();

		return p;
	}

	void deallocate(void* p)
	{
		std::lock_guard<std::mutex> lk(mtx); // avoid race condition

		// free object memory
		FreeBlock* block = static_cast<FreeBlock*>(p);
		block->next = free_block_head; // insert the free block to head
		free_block_head = block;
	}

private:
	// free node block, every block size exactly can contain one object
	struct FreeBlock
	{
		unsigned char data[BlockSize];
		FreeBlock* next;
	};

	FreeBlock* free_block_head;

	// memory chunk, every chunk contains blocks number with fixed BlockNum
	struct MemChunk
	{
		FreeBlock blocks[BlockNum];
		MemChunk* next;
	};

	MemChunk* mem_chunk_head;

	// thread safe related
	std::mutex mtx;
	std::mutex array_mtx;
};

#endif // !_MEMORY_POOL_H_