简介

  • 记录2024年求职面试遇到的C++面试问题

STL分为哪几类

STL (Standard Template Library) 主要由以下几类组件构成：

  1. 容器（Containers）：
    • 序列式容器（Sequence Containers）：vector, deque, list, array
    • 关联式容器（Associative Containers）：set, map, multiset, multimap
    • 无序容器（Unordered Containers）：unordered_set, unordered_map, unordered_multiset, unordered_multimap
  2. 迭代器（Iterators）：
    • 输入迭代器（Input Iterator）
    • 输出迭代器（Output Iterator）
    • 前向迭代器（Forward Iterator）
    • 双向迭代器（Bidirectional Iterator）
    • 随机访问迭代器（Random Access Iterator）
  3. 算法（Algorithms）：
    • 非修改算法（Non-modifying algorithms）：find, count, for_each, 等
    • 修改算法（Modifying algorithms）：copy, swap, transform, 等
    • 排序算法（Sorting algorithms）：sort, partial_sort, nth_element, 等
    • 其他算法：search, merge, includes, 等

  4. 函数对象（Function Objects）：如 less, greater, plus, minus, 等

  5. 适配器（Adapters）：
    • 容器适配器（Container Adapters）：stack, queue, priority_queue
    • 迭代器适配器（Iterator Adapters）：reverse_iterator, back_insert_iterator, front_insert_iterator, 等
    • 函数适配器（Function Adapters）：bind, function, mem_fn, 等

这些组件共同构成了STL，使其能够提供高效且灵活的操作来处理各种数据结构和算法。

STL常用的几个容器有哪些？用时间复杂度，空间复杂度对比一下

STL中常用的容器主要包括：vector, deque, list, set, map, unordered_set, unordered_map。下面是这些容器的时间复杂度和空间复杂度对比：

1. vector

  • 时间复杂度：
    • 访问元素：O(1)
    • 插入/删除（末尾）：O(1) 均摊
    • 插入/删除（中间或开头）：O(n)
  • 空间复杂度：
    • 动态数组，空间效率较高，但可能有一些额外的空间用于容器增长。

2. deque

  • 时间复杂度：
    • 访问元素：O(1)
    • 插入/删除（两端）：O(1)
    • 插入/删除（中间）：O(n)
  • 空间复杂度：
    • 双端队列，通常比 vector 多一些空间开销，但仍然是较为紧凑的。

3. list

  • 时间复杂度：
    • 访问元素：O(n)
    • 插入/删除（任意位置）：O(1)
  • 空间复杂度：
    • 链表，每个元素需要额外的指针空间，相较于 vector 和 deque 更高。

4. set

  • 时间复杂度：
    • 插入/删除/查找：O(log n)
  • 空间复杂度：
    • 平衡二叉搜索树，空间开销较高，需要额外的指针。

5. map

  • 时间复杂度：
    • 插入/删除/查找：O(log n)
  • 空间复杂度：
    • 平衡二叉搜索树，与 set 类似，空间开销较高。

6. unordered_set

  • 时间复杂度：
    • 插入/删除/查找：O(1) 均摊
  • 空间复杂度：
    • 哈希表，需要额外的空间用于哈希桶。

7. unordered_map

  • 时间复杂度：
    • 插入/删除/查找：O(1) 均摊
  • 空间复杂度：
    • 哈希表，与 unordered_set 类似，空间开销较高。

对比总结

  • 访问元素：vector 和 deque 的随机访问效率最高，list 最低。
  • 插入/删除：list 在任意位置插入/删除效率最高，vector 和 deque 末尾插入/删除效率高，但在中间位置操作效率低。
  • 查找：有序容器（如 set 和 map）和无序容器（如 unordered_set 和 unordered_map）均提供高效的查找，但有序容器的查找是O(log n)，无序容器为O(1)均摊。
  • 空间效率：vector 和 deque 空间效率较高，list 和基于树结构的 set/map 空间开销较高，无序容器（哈希表）则需要额外空间用于哈希桶。

单例模式怎么实现

单例模式（Singleton Pattern）是一种设计模式，确保一个类只有一个实例，并提供一个全局访问点。实现单例模式的方式有很多种，以下是几种常见的实现方法：

1. 懒汉式（线程不安全）

懒汉式单例模式在第一次使用时创建实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Singleton {
private:
    static Singleton* instance;
    Singleton() {} // 私有构造函数

public:
    static Singleton* getInstance() {
        if (instance == nullptr) {
            instance = new Singleton();
        }
        return instance;
    }
};

// 初始化静态成员
Singleton* Singleton::instance = nullptr;

2. 懒汉式（线程安全，使用互斥锁）

使用互斥锁确保线程安全，但会影响性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <mutex>

class Singleton {
private:
    static Singleton* instance;
    static std::mutex mtx;
    Singleton() {} // 私有构造函数

public:
    static Singleton* getInstance() {
        std::lock_guard<std::mutex> lock(mtx);
        if (instance == nullptr) {
            instance = new Singleton();
        }
        return instance;
    }
};

// 初始化静态成员
Singleton* Singleton::instance = nullptr;
std::mutex Singleton::mtx;

3. 饿汉式

饿汉式单例模式在类加载时就创建实例。

1
2
3
4
5
6
7
8
9
10
11
12
13

class Singleton {
private:
    static Singleton* instance;
    Singleton() {} // 私有构造函数

public:
    static Singleton* getInstance() {
        return instance;
    }
};

// 初始化静态成员
Singleton* Singleton::instance = new Singleton();

4. 双重检查锁（Double-Checked Locking）

双重检查锁在提高性能的同时确保线程安全。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <mutex>

class Singleton {
private:
    static Singleton* instance;
    static std::mutex mtx;
    Singleton() {} // 私有构造函数

public:
    static Singleton* getInstance() {
        if (instance == nullptr) {
            std::lock_guard<std::mutex> lock(mtx);
            if (instance == nullptr) {
                instance = new Singleton();
            }
        }
        return instance;
    }
};

// 初始化静态成员
Singleton* Singleton::instance = nullptr;
std::mutex Singleton::mtx;

5. 使用局部静态变量（C++11及以上）

C++11标准保证了静态局部变量的线程安全性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Singleton {
private:
    Singleton() {} // 私有构造函数

public:
    static Singleton& getInstance() {
        static Singleton instance;
        return instance;
    }

    // 禁用拷贝构造函数和赋值运算符
    Singleton(const Singleton&) = delete;
    Singleton& operator=(const Singleton&) = delete;
};

6. 使用 call_once（C++11及以上）

std::call_once 保证了一次性初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <mutex>

class Singleton {
private:
    Singleton() {} // 私有构造函数
    static Singleton* instance;
    static std::once_flag initFlag;

public:
    static Singleton* getInstance() {
        std::call_once(initFlag, []() {
            instance = new Singleton();
        });
        return instance;
    }

    // 禁用拷贝构造函数和赋值运算符
    Singleton(const Singleton&) = delete;
    Singleton& operator=(const Singleton&) = delete;
};

// 初始化静态成员
Singleton* Singleton::instance = nullptr;
std::once_flag Singleton::initFlag;

这几种方法各有优缺点，选择哪种实现方式取决于具体的需求和场景。

手动实现一个栈或队列

下面是手动实现一个栈（Stack）和一个队列（Queue）的示例代码，分别使用C++语言：

栈的实现

一个简单的栈可以使用数组或链表来实现。这里我们使用链表来实现一个栈。

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

#include <iostream>

// 节点结构体
struct Node {
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

class Stack {
private:
    Node* top;

public:
    Stack() : top(nullptr) {}

    // 入栈
    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = top;
        top = newNode;
    }

    // 出栈
    void pop() {
        if (top == nullptr) {
            std::cerr << "Stack is empty." << std::endl;
            return;
        }
        Node* temp = top;
        top = top->next;
        delete temp;
    }

    // 获取栈顶元素
    int peek() {
        if (top == nullptr) {
            std::cerr << "Stack is empty." << std::endl;
            return -1;
        }
        return top->data;
    }

    // 检查栈是否为空
    bool isEmpty() {
        return top == nullptr;
    }

    ~Stack() {
        while (top != nullptr) {
            pop();
        }
    }
};

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);

    std::cout << "Top element is " << stack.peek() << std::endl;

    stack.pop();
    std::cout << "Top element is " << stack.peek() << std::endl;

    return 0;
}

队列的实现

一个简单的队列可以使用数组或链表来实现。这里我们使用链表来实现一个队列。

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

#include <iostream>

// 节点结构体
struct Node {
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

class Queue {
private:
    Node* front;
    Node* rear;

public:
    Queue() : front(nullptr), rear(nullptr) {}

    // 入队
    void enqueue(int value) {
        Node* newNode = new Node(value);
        if (rear == nullptr) {
            front = rear = newNode;
            return;
        }
        rear->next = newNode;
        rear = newNode;
    }

    // 出队
    void dequeue() {
        if (front == nullptr) {
            std::cerr << "Queue is empty." << std::endl;
            return;
        }
        Node* temp = front;
        front = front->next;
        if (front == nullptr) {
            rear = nullptr;
        }
        delete temp;
    }

    // 获取队首元素
    int peek() {
        if (front == nullptr) {
            std::cerr << "Queue is empty." << std::endl;
            return -1;
        }
        return front->data;
    }

    // 检查队列是否为空
    bool isEmpty() {
        return front == nullptr;
    }

    ~Queue() {
        while (front != nullptr) {
            dequeue();
        }
    }
};

int main() {
    Queue queue;
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    std::cout << "Front element is " << queue.peek() << std::endl;

    queue.dequeue();
    std::cout << "Front element is " << queue.peek() << std::endl;

    return 0;
}

这两个示例展示了如何使用链表来实现栈和队列的基本操作，包括入栈/入队、出栈/出队、获取栈顶/队首元素，以及检查栈/队列是否为空。