C++11实现自定义STL vector与航空订票系统-嵌云网-嵌入式AI开发资源站

C++11实现自定义STL vector与航空订票系统

北京海淀区一女的

1. 项目概述

这个项目主要包含两个部分：一是实现一个具备C++11现代特性的简化版STL vector容器，二是基于这个自定义vector实现一个简单的航空订票系统。项目的核心目标是练习C++11的各种现代特性，包括智能指针、万能引用、完美转发、可变参数模板等，同时复习vector迭代器的实现原理。

我选择这个项目是因为在实际开发中，STL容器是最基础也是最重要的组件之一。通过自己实现一个简化版的vector，可以深入理解其内部工作原理，这对提升C++编程能力和调试技巧都大有裨益。而航空订票系统则提供了一个实际应用场景，可以验证我们实现的vector是否真正可用。

2. 核心设计思路

2.1 自定义vector的整体架构

我设计的MyVector类模板采用了与标准库vector类似的三指针结构，但使用了智能指针来管理内存：

cpp复制template<class T>
class MyVector {
private:
    std::unique_ptr<T[]> _start = nullptr;  // 指向数组起始位置
    T* _finish = nullptr;                   // 指向最后一个元素的下一个位置
    T* _end_of_storage = nullptr;           // 指向存储空间末尾
};

这里有几个关键设计决策：

只对_start使用unique_ptr，其他两个指针保持原始指针。这是因为多个智能指针指向同一内存的不同位置会导致重复释放问题。
使用unique_ptr而不是shared_ptr，因为vector不需要共享所有权语义，且unique_ptr的性能开销更小。
将迭代器实现为独立的类模板，支持const和非const两种版本，这与标准库的设计一致。

2.2 迭代器实现

迭代器是STL容器的核心概念之一。我实现的迭代器类模板支持完整的随机访问迭代器操作：

cpp复制template<class T, class Ref, class Ptr>
class Iterator {
public:
    // 各种运算符重载
    Iterator& operator++();
    Iterator operator++(int);
    Iterator& operator--();
    Iterator operator--(int);
    bool operator==(const Iterator& other) const;
    bool operator!=(const Iterator& other) const;
    Ptr operator->() const;
    Ref operator*() const;
    Ref operator[](size_t pos) const;
    Iterator operator-(size_t n) const;
    Iterator operator+(size_t n) const;
    
private:
    T* _ptr = nullptr;
    T* _begin = nullptr;
    T* _end = nullptr;
};

这种设计使得我们的MyVector可以无缝兼容STL算法，如std::sort、std::find等。

3. 关键实现细节

3.1 内存管理与扩容策略

vector的核心功能之一就是动态扩容。我实现的reserve方法采用了常见的1.5倍扩容策略：

cpp复制void reserve(size_t capacity) {
    capacity = capacity <= (_end_of_storage - _start.get()) ? 
        (_end_of_storage - _start.get()) * 1.5 : capacity;
    
    MyVector newVector(capacity);
    newVector._finish = newVector._start.get() + (_finish - _start.get());
    
    for(int i = 0; i < _finish - _start.get(); ++i) {
        newVector[i] = _start[i];
    }
    
    swap(newVector);
}

这里有几个值得注意的点：

使用swap惯用法来实现异常安全的扩容操作
1.5倍扩容是STL常见的策略，平衡了空间和时间效率
移动语义优化将在后面讨论

3.2 插入操作的实现

insert和emplace是vector最常用的操作之一。我实现了支持完美转发的版本：

cpp复制template<class ...Args>
iterator emplace(iterator pos, Args&& ...args) {
    size_t mid = pos._ptr - _start.get();
    if(_finish == _end_of_storage) {
        reserve((_end_of_storage - _start.get()) * 1.5);
    }
    
    ++_finish;
    iterator newPos(_start.get() + mid, _start.get(), _finish);
    
    for(iterator it = --end(); it != newPos; --it) {
        *it = std::move(*(it - 1));
    }
    
    *newPos = T(std::forward<Args>(args)...);
    return newPos;
}

这个实现展示了几个C++11特性：

可变参数模板(Args&& ...args)
万能引用和完美转发(std::forward)
移动语义优化(std::move)

3.3 移动语义优化

在insert和erase操作中，我大量使用了移动语义来优化性能：

cpp复制for(iterator it = --end(); it != newPos; --it) {
    *it = std::move(*(it - 1));
}

这里使用std::move的原因是：在插入/删除元素时，我们需要移动一系列元素。这些元素原来的位置将被覆盖，所以可以安全地将它们视为右值，调用移动赋值运算符而不是拷贝赋值运算符。

4. 航空订票系统实现

4.1 核心数据结构

航空订票系统主要包含两个核心数据结构：

cpp复制struct Flight {
    std::string _flightId;      // 航班号
    std::string _departureCity; // 出发城市
    std::string _arrivalCity;   // 抵达城市
    std::string _departureTime; // 起飞时间
    std::string _arrivalTime;   // 降落时间
    int _totalSeats;            // 总座位数
    int _availableSeats;        // 剩余座位数
    MyVector<STATUS> _seatStatus; // 座位状态数组
};

struct Passenger {
    std::string _passengerName;    // 乘客姓名
    std::string _bookedrFlightId;  // 已订航班号
    int _seatNumber;               // 座位号
};

4.2 座位分配算法

为了实现高效的座位分配和释放，我采用了混合策略：

cpp复制int Flight::assignSeat() {
    assert(_availableSeats);
    int nextSeat = 0;
    
    if(_refundedSeats.empty()) {
        if(_nextNormalSeat == _totalSeats) {
            return -1;
        }
        nextSeat = _nextNormalSeat;
        ++_nextNormalSeat;
    }
    else {
        nextSeat = _refundedSeats.top();
        _refundedSeats.pop();
    }
    
    _seatStatus[nextSeat] = FILL;
    --_availableSeats;
    return nextSeat;
}

这个算法结合了：

顺序分配(_nextNormalSeat)
优先队列(_refundedSeats)

这样可以在O(1)时间复杂度内完成座位分配，同时保证总是分配编号最小的可用座位。

5. 经验总结与避坑指南

在实现过程中，我遇到了不少问题，也积累了一些宝贵经验：

5.1 智能指针的使用陷阱

不要对同一内存使用多个unique_ptr：我最初尝试将三个指针都定义为unique_ptr，这会导致重复释放问题。正确的做法是只有_start使用unique_ptr，其他两个保持原始指针。
unique_ptr不支持指针算术：需要通过get()获取原始指针后才能进行指针运算。
移动语义是必须的：因为unique_ptr不支持拷贝，所以在vector的拷贝构造函数和赋值运算符中必须使用移动语义。

5.2 模板编程的注意事项

友元声明要小心：在类模板中声明友元时，要注意模板参数遮蔽问题。正确的做法是：

cpp复制template<class U> 
friend std::ostream& operator<<(std::ostream& os, const MyVector<U>& v);

const迭代器的实现：容易忘记给迭代器类模板中的函数添加const修饰，这会导致const版本的vector无法调用这些方法。

5.3 性能优化技巧

移动语义的应用：在insert/erase操作中，使用std::move可以显著提升性能，特别是对于自定义类型。
避免不必要的拷贝：find函数返回迭代器而不是元素本身，避免了深拷贝开销。
内存分配的优化：1.5倍扩容策略平衡了空间和时间效率，是经过实践检验的方案。

6. 扩展思考

虽然这个实现已经具备了基本功能，但还有不少可以改进的地方：

异常安全性：可以进一步强化异常安全性，确保在发生异常时资源不会泄漏。
分配器支持：可以添加分配器支持，让用户能够自定义内存分配策略。
更完善的迭代器特性：可以定义迭代器特性(iterator traits)，使我们的迭代器更加符合STL规范。
并行操作支持：可以考虑添加线程安全版本，支持多线程环境下的安全操作。

这个项目让我深刻理解了STL容器的内部实现原理，也让我对C++11的现代特性有了更深入的认识。特别是移动语义和完美转发这些概念，在实际编码中才能真正体会到它们的价值。