Step 00
起步：不打开仓库，也能把工程搭起来
教学正文、作业纸、测试、CMake 和参考答案都在这个网站上。新建一个空目录，下载压缩包或按下面逐文件保存即可。 你不需要克隆本教程的 Git 仓库。
本课默认走作业纸：-DMINI_VECTOR_USE_STUDENT=ON。 作业纸下半的函数体是 TODO，测试一开始会失败，这是预期。 想先看全绿：展开本页最后的参考答案，存成 include/mini_vector/vector.hpp，配置时不要打开 STUDENT 开关。
你需要准备的（和仓库无关）
- CMake ≥ 3.20
- C++20 编译器（GCC 13 / Clang 16 / MSVC 19.3x）
- 第一次配置时能访问 GitHub，以便下载公开的 GoogleTest v1.15.2 源码包。这不是本教程仓库；CMake 用 HTTPS 拉 tar.gz，不需要 git。
目录
diy-vector/
├── CMakeLists.txt
├── README.md
├── student/mini_vector/vector.hpp ← 你要填的作业纸
├── include/mini_vector/vector.hpp ← 可选参考答案
├── examples/demo.cpp
└── tests/
├── test_helpers.hpp
├── test_basic.cpp
├── test_no_default_ctor.cpp
├── test_custom_allocator.cpp
├── test_exception_safety.cpp
└── test_move_only.cpp
解压后第一次编译
如果默认的 c++ 链不上 libstdc++，指定 g++：
cmake -B build -DCMAKE_BUILD_TYPE=Debug -DCMAKE_CXX_COMPILER=g++ -DMINI_VECTOR_USE_STUDENT=ON
cmake --build build
# 此时除了空 vector 那条，其它测试失败是正常的：作业纸还没填。
./build/vector_tests --gtest_filter='Step01.EmptyVectorHasZeroSizeAndCapacity'怎么往作业纸里贴代码
- 打开
student/mini_vector/vector.hpp。上半是class Vector的声明，已经写好，后面七步几乎不用动它。 - 下半是
template <typename T, typename Allocator>开头的类外定义，每个函数带TODO(step N)。 - 打开对应章节，复制「可粘贴代码」里的整段（含两层
template，直到函数最后的}），覆盖那个 TODO 函数。 - 不要把代码塞进 class 体内，不要在类外定义里写
= Allocator()。细节见 常见问题。
逐文件复制
不想下压缩包也可以：点开文件，复制全部内容，按路径保存到空目录。CMake 和作业纸建议先展开。
README.md起步包说明。压缩包解压后就是这份。
# diy-vector 起步包
这个压缩包包含手搓 C++20 vector 教程的全部工程文件。**不需要访问 Git 仓库**。教学正文在配套网站上，本包只提供能编译的工程。
## 目录
| 路径 | 作用 |
|------|------|
| `student/mini_vector/vector.hpp` | 作业纸。按网站各章把 TODO 换成可粘贴代码 |
| `include/mini_vector/vector.hpp` | 参考答案。先别看 |
| `tests/` | GoogleTest |
| `examples/demo.cpp` | 小演示 |
| `CMakeLists.txt` | C++20 + 下载 GoogleTest v1.15.2（HTTPS，不需要 git clone） |
## 环境
- CMake ≥ 3.20
- C++20 编译器（GCC 13 / Clang 16 / MSVC 19.3x）
- 第一次配置时需要能访问 GitHub，用来下载 GoogleTest 源码包（不是这个教程仓库）
## 按教程抄（推荐）
```bash
cmake -B build -DCMAKE_BUILD_TYPE=Debug -DCMAKE_CXX_COMPILER=g++ -DMINI_VECTOR_USE_STUDENT=ON
cmake --build build
./build/vector_tests --gtest_filter='Step01.EmptyVectorHasZeroSizeAndCapacity'
```
打开教学站 Step 01。作业纸上半是声明，下半是 TODO：用网站上的整段类外定义替换，不要贴进 `class` 里面。
## 先看全绿再拆
```bash
cmake -B build -DCMAKE_BUILD_TYPE=Debug -DCMAKE_CXX_COMPILER=g++
cmake --build build
ctest --test-dir build --output-on-failure
```
这条编译的是 `include/` 里的参考实现。
## 常见问题
默认的 `c++` 若链不上 `libstdc++`，加上 `-DCMAKE_CXX_COMPILER=g++`。
不想开 AddressSanitizer：
```bash
cmake -B build -DMINI_VECTOR_SANITIZE=OFF -DCMAKE_CXX_COMPILER=g++
```
CMakeLists.txtC++20 工程、GoogleTest（HTTPS 下载，不需要 git）、作业纸开关。
cmake_minimum_required(VERSION 3.20)
project(mini_vector
VERSION 1.0.0
DESCRIPTION "A from-scratch C++20 vector with custom allocator support"
LANGUAGES CXX
)
set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)
option(MINI_VECTOR_BUILD_TESTS "Build GoogleTest suite" ON)
option(MINI_VECTOR_BUILD_DEMO "Build the demo executable" ON)
option(MINI_VECTOR_SANITIZE "Enable AddressSanitizer and UndefinedSanitizer" ON)
option(MINI_VECTOR_USE_STUDENT
"Compile tests/demo against student/vector.hpp instead of the reference implementation"
OFF
)
function(mini_vector_apply_warnings target)
if(MSVC)
target_compile_options(${target} PRIVATE /W4 /WX)
else()
target_compile_options(${target} PRIVATE -Wall -Wextra -Wpedantic -Werror)
endif()
endfunction()
function(mini_vector_apply_sanitizers target)
if(MINI_VECTOR_SANITIZE AND NOT MSVC)
target_compile_options(${target} PRIVATE -fsanitize=address,undefined)
target_link_options(${target} PRIVATE -fsanitize=address,undefined)
endif()
endfunction()
add_library(mini_vector INTERFACE)
add_library(mini::vector ALIAS mini_vector)
if(MINI_VECTOR_USE_STUDENT)
target_include_directories(mini_vector INTERFACE
${CMAKE_CURRENT_SOURCE_DIR}/student
)
else()
target_include_directories(mini_vector INTERFACE
${CMAKE_CURRENT_SOURCE_DIR}/include
)
endif()
if(MINI_VECTOR_BUILD_DEMO)
add_executable(mini_vector_demo examples/demo.cpp)
target_link_libraries(mini_vector_demo PRIVATE mini::vector)
mini_vector_apply_warnings(mini_vector_demo)
mini_vector_apply_sanitizers(mini_vector_demo)
endif()
if(MINI_VECTOR_BUILD_TESTS)
include(FetchContent)
FetchContent_Declare(
googletest
URL https://github.com/google/googletest/archive/refs/tags/v1.15.2.tar.gz
URL_HASH SHA256=7b42b4d6ed48810c5362c265a17faebe90dc2373c885e5216439d37927f02926
DOWNLOAD_EXTRACT_TIMESTAMP TRUE
)
set(gtest_force_shared_crt ON CACHE BOOL "" FORCE)
FetchContent_MakeAvailable(googletest)
enable_testing()
add_executable(vector_tests
tests/test_basic.cpp
tests/test_no_default_ctor.cpp
tests/test_custom_allocator.cpp
tests/test_exception_safety.cpp
tests/test_move_only.cpp
)
target_include_directories(vector_tests PRIVATE ${CMAKE_CURRENT_SOURCE_DIR}/tests)
target_link_libraries(vector_tests PRIVATE mini::vector GTest::gtest_main)
mini_vector_apply_warnings(vector_tests)
mini_vector_apply_sanitizers(vector_tests)
include(GoogleTest)
gtest_discover_tests(vector_tests)
endif()
student/mini_vector/vector.hpp作业纸。后面 8 步都往这个文件底部的 TODO 里整段替换。
#pragma once
// =============================================================================
// 抄写作业纸（worksheet）
// 对照教学站各章「可粘贴代码」：用整段类外定义替换对应的 TODO 函数。
// 不要把代码再贴进上面的 class 体内。
//
// cmake -B build -DMINI_VECTOR_USE_STUDENT=ON -DCMAKE_CXX_COMPILER=g++
// cmake --build build
// ctest --test-dir build --output-on-failure
//
// 卡住时打开教学站「参考答案」页，对照同一个函数。
// =============================================================================
#include <concepts>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <memory>
#include <stdexcept>
#include <type_traits>
#include <utility>
namespace mini {
template <typename T, typename Allocator = std::allocator<T>>
class Vector {
public:
using value_type = T;
using allocator_type = Allocator;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using reference = T&;
using const_reference = const T&;
using pointer = typename std::allocator_traits<Allocator>::pointer;
using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;
using iterator = T*;
using const_iterator = const T*;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
private:
using AllocTraits = std::allocator_traits<Allocator>;
// Step 01
T* data_{nullptr};
size_type size_{0};
size_type capacity_{0};
// Step 02
[[no_unique_address]] Allocator alloc_{};
public:
Vector() noexcept(std::is_nothrow_default_constructible_v<Allocator>) = default;
explicit Vector(const Allocator& alloc) noexcept : alloc_(alloc) {}
explicit Vector(size_type count, const Allocator& alloc = Allocator())
requires std::default_initializable<T>;
Vector(size_type count, const T& value, const Allocator& alloc = Allocator())
requires std::copy_constructible<T>;
Vector(std::initializer_list<T> init, const Allocator& alloc = Allocator())
requires std::copy_constructible<T>;
Vector(const Vector& other)
requires std::copy_constructible<T>;
Vector(const Vector& other, const Allocator& alloc)
requires std::copy_constructible<T>;
Vector(Vector&& other) noexcept;
Vector(Vector&& other, const Allocator& alloc);
~Vector();
Vector& operator=(const Vector& other)
requires std::copy_constructible<T>;
Vector& operator=(Vector&& other) noexcept(
AllocTraits::propagate_on_container_move_assignment::value ||
AllocTraits::is_always_equal::value);
Vector& operator=(std::initializer_list<T> init)
requires std::copy_constructible<T>;
allocator_type get_allocator() const noexcept { return alloc_; }
reference at(size_type index);
const_reference at(size_type index) const;
reference operator[](size_type index) noexcept { return data_[index]; }
const_reference operator[](size_type index) const noexcept { return data_[index]; }
reference front() noexcept { return data_[0]; }
const_reference front() const noexcept { return data_[0]; }
reference back() noexcept { return data_[size_ - 1]; }
const_reference back() const noexcept { return data_[size_ - 1]; }
T* data() noexcept { return data_; }
const T* data() const noexcept { return data_; }
iterator begin() noexcept { return data_; }
const_iterator begin() const noexcept { return data_; }
const_iterator cbegin() const noexcept { return data_; }
iterator end() noexcept { return data_ + size_; }
const_iterator end() const noexcept { return data_ + size_; }
const_iterator cend() const noexcept { return data_ + size_; }
reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
[[nodiscard]] bool empty() const noexcept { return size_ == 0; }
size_type size() const noexcept { return size_; }
size_type capacity() const noexcept { return capacity_; }
size_type max_size() const noexcept;
void reserve(size_type new_cap);
void shrink_to_fit();
void clear() noexcept;
void push_back(const T& value)
requires std::copy_constructible<T>;
void push_back(T&& value);
template <typename... Args>
reference emplace_back(Args&&... args);
void pop_back();
void resize(size_type count)
requires std::default_initializable<T>;
void resize(size_type count, const T& value)
requires std::copy_constructible<T>;
void swap(Vector& other) noexcept;
friend bool operator==(const Vector& lhs, const Vector& rhs) {
if (lhs.size_ != rhs.size_) {
return false;
}
for (size_type i = 0; i < lhs.size_; ++i) {
if (!(lhs.data_[i] == rhs.data_[i])) {
return false;
}
}
return true;
}
friend bool operator!=(const Vector& lhs, const Vector& rhs) {
return !(lhs == rhs);
}
private:
// 把教学站各章「可粘贴代码」抄到下面的类外定义，不要写进 class 体内。
T* allocate_n(size_type n);
void deallocate_n(T* ptr, size_type n) noexcept;
void destroy_range(T* first, T* last) noexcept;
void uninitialized_value_construct_n(T* dest, size_type n);
void uninitialized_fill_n(T* dest, size_type n, const T& value);
template <typename InputIt>
void uninitialized_copy_n(T* dest, InputIt src, size_type n);
void uninitialized_move_n(T* dest, T* src, size_type n);
void uninitialized_relocate_n(T* dest, T* src, size_type n);
size_type recommend_capacity(size_type min_cap) const;
void reallocate(size_type new_cap);
template <typename TailCtor>
void grow_buffer_and_append(size_type count, TailCtor&& construct_tail);
void copy_from_range(const T* src, size_type n);
void move_from_range(T* src, size_type n);
void reset_storage() noexcept;
void steal_storage(Vector& other) noexcept;
void swap_storage(Vector& other) noexcept;
};
template <typename T, typename Allocator>
void swap(Vector<T, Allocator>& lhs, Vector<T, Allocator>& rhs) noexcept {
lhs.swap(rhs);
}
// -----------------------------------------------------------------------------
// 下面这些定义是故意留空的：按教学站 Step 01 … 08 的顺序，
// 用「可粘贴代码」整段替换（保留 template 头，不要默认实参）。
// -----------------------------------------------------------------------------
template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(size_type count, const Allocator& alloc)
requires std::default_initializable<T>
: alloc_(alloc) {
(void)count;
// TODO(step 01/06)
}
template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(size_type count, const T& value, const Allocator& alloc)
requires std::copy_constructible<T>
: alloc_(alloc) {
(void)count;
(void)value;
// TODO(step 01/06)
}
template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(std::initializer_list<T> init, const Allocator& alloc)
requires std::copy_constructible<T>
: alloc_(alloc) {
(void)init;
// TODO(step 01/06)
}
template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(const Vector& other)
requires std::copy_constructible<T>
: alloc_(AllocTraits::select_on_container_copy_construction(other.alloc_)) {
(void)other;
// TODO(step 07)
}
template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(const Vector& other, const Allocator& alloc)
requires std::copy_constructible<T>
: alloc_(alloc) {
(void)other;
// TODO(step 07)
}
template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(Vector&& other) noexcept
: data_(std::exchange(other.data_, nullptr)),
size_(std::exchange(other.size_, 0)),
capacity_(std::exchange(other.capacity_, 0)),
alloc_(std::move(other.alloc_)) {}
template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(Vector&& other, const Allocator& alloc)
: alloc_(alloc) {
(void)other;
// TODO(step 07)
}
template <typename T, typename Allocator>
Vector<T, Allocator>::~Vector() {
// TODO(step 03): destroy_range + deallocate_n
}
template <typename T, typename Allocator>
Vector<T, Allocator>& Vector<T, Allocator>::operator=(const Vector& other)
requires std::copy_constructible<T>
{
(void)other;
return *this; // TODO(step 07)
}
template <typename T, typename Allocator>
Vector<T, Allocator>& Vector<T, Allocator>::operator=(Vector&& other) noexcept(
AllocTraits::propagate_on_container_move_assignment::value ||
AllocTraits::is_always_equal::value) {
(void)other;
return *this; // TODO(step 07)
}
template <typename T, typename Allocator>
Vector<T, Allocator>& Vector<T, Allocator>::operator=(std::initializer_list<T> init)
requires std::copy_constructible<T>
{
(void)init;
return *this; // TODO(step 07)
}
template <typename T, typename Allocator>
typename Vector<T, Allocator>::reference
Vector<T, Allocator>::at(size_type index) {
(void)index;
throw std::out_of_range("TODO(step 08)");
}
template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_reference
Vector<T, Allocator>::at(size_type index) const {
(void)index;
throw std::out_of_range("TODO(step 08)");
}
template <typename T, typename Allocator>
typename Vector<T, Allocator>::size_type
Vector<T, Allocator>::max_size() const noexcept {
return 0; // TODO(step 02)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::reserve(size_type new_cap) {
(void)new_cap; // TODO(step 04)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::shrink_to_fit() {
// TODO(step 04)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::clear() noexcept {
// TODO(step 03)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::push_back(const T& value)
requires std::copy_constructible<T>
{
(void)value; // TODO(step 05): emplace_back(value)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::push_back(T&& value) {
(void)value; // TODO(step 05): emplace_back(std::move(value))
}
template <typename T, typename Allocator>
template <typename... Args>
typename Vector<T, Allocator>::reference
Vector<T, Allocator>::emplace_back(Args&&... args) {
(void)sizeof...(args);
throw std::logic_error("TODO(step 05)");
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::pop_back() {
// TODO(step 03)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::resize(size_type count)
requires std::default_initializable<T>
{
(void)count; // TODO(step 06)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::resize(size_type count, const T& value)
requires std::copy_constructible<T>
{
(void)count;
(void)value; // TODO(step 06)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::swap(Vector& other) noexcept {
(void)other; // TODO(step 07)
}
template <typename T, typename Allocator>
T* Vector<T, Allocator>::allocate_n(size_type n) {
(void)n;
return nullptr; // TODO(step 02)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::deallocate_n(T* ptr, size_type n) noexcept {
(void)ptr;
(void)n; // TODO(step 02)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::destroy_range(T* first, T* last) noexcept {
(void)first;
(void)last; // TODO(step 03)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::uninitialized_value_construct_n(T* dest, size_type n) {
(void)dest;
(void)n; // TODO(step 03)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::uninitialized_fill_n(T* dest, size_type n, const T& value) {
(void)dest;
(void)n;
(void)value; // TODO(step 03)
}
template <typename T, typename Allocator>
template <typename InputIt>
void Vector<T, Allocator>::uninitialized_copy_n(T* dest, InputIt src, size_type n) {
(void)dest;
(void)src;
(void)n; // TODO(step 03)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::uninitialized_move_n(T* dest, T* src, size_type n) {
(void)dest;
(void)src;
(void)n; // TODO(step 03)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::uninitialized_relocate_n(T* dest, T* src, size_type n) {
(void)dest;
(void)src;
(void)n; // TODO(step 04)
}
template <typename T, typename Allocator>
typename Vector<T, Allocator>::size_type
Vector<T, Allocator>::recommend_capacity(size_type min_cap) const {
(void)min_cap;
return 0; // TODO(step 04)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::reallocate(size_type new_cap) {
(void)new_cap; // TODO(step 04)
}
template <typename T, typename Allocator>
template <typename TailCtor>
void Vector<T, Allocator>::grow_buffer_and_append(size_type count, TailCtor&& construct_tail) {
(void)count;
(void)construct_tail; // TODO(step 06)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::copy_from_range(const T* src, size_type n) {
(void)src;
(void)n; // TODO(step 07)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::move_from_range(T* src, size_type n) {
(void)src;
(void)n; // TODO(step 07)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::reset_storage() noexcept {
// TODO(step 07)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::steal_storage(Vector& other) noexcept {
(void)other; // TODO(step 07)
}
template <typename T, typename Allocator>
void Vector<T, Allocator>::swap_storage(Vector& other) noexcept {
(void)other; // TODO(step 07)
}
} // namespace mini
examples/demo.cpp小演示程序。作业纸没填完时 emplace_back 会抛异常，属正常。
#include "mini_vector/vector.hpp"
#include <iostream>
#include <string>
#include <utility>
int main() {
mini::Vector<std::string> words;
words.reserve(4);
words.push_back("hand-rolled");
words.emplace_back("vector");
words.push_back(std::string("C++20"));
std::cout << "size=" << words.size() << " cap=" << words.capacity() << '\n';
for (const auto& word : words) {
std::cout << " - " << word << '\n';
}
words.pop_back();
words.resize(5, std::string("..."));
std::cout << "after resize: ";
for (std::size_t i = 0; i < words.size(); ++i) {
if (i != 0) {
std::cout << " | ";
}
std::cout << words[i];
}
std::cout << '\n';
return 0;
}
tests/test_helpers.hpp测试用的 NoDefault、MoveOnly、CountingAllocator。
#pragma once
#include <cstddef>
#include <memory>
#include <new>
#include <stdexcept>
#include <string>
#include <utility>
namespace test_types {
struct NoDefault {
int value;
explicit NoDefault(int v) : value(v) {}
NoDefault() = delete;
friend bool operator==(const NoDefault& a, const NoDefault& b) {
return a.value == b.value;
}
};
struct MoveOnly {
int value;
explicit MoveOnly(int v) : value(v) {}
MoveOnly(const MoveOnly&) = delete;
MoveOnly& operator=(const MoveOnly&) = delete;
MoveOnly(MoveOnly&& other) noexcept : value(other.value) {
other.value = -1;
}
MoveOnly& operator=(MoveOnly&& other) noexcept {
value = other.value;
other.value = -1;
return *this;
}
friend bool operator==(const MoveOnly& a, const MoveOnly& b) {
return a.value == b.value;
}
};
struct CopyTracked {
inline static int copies = 0;
inline static int moves = 0;
inline static int live = 0;
inline static int constructs = 0;
inline static int destroys = 0;
int value;
static void reset() {
copies = 0;
moves = 0;
live = 0;
constructs = 0;
destroys = 0;
}
explicit CopyTracked(int v = 0) : value(v) {
++live;
++constructs;
}
CopyTracked(const CopyTracked& other) : value(other.value) {
++copies;
++live;
++constructs;
}
CopyTracked(CopyTracked&& other) noexcept : value(other.value) {
other.value = -1;
++moves;
++live;
++constructs;
}
CopyTracked& operator=(const CopyTracked& other) {
value = other.value;
return *this;
}
CopyTracked& operator=(CopyTracked&& other) noexcept {
value = other.value;
other.value = -1;
return *this;
}
~CopyTracked() {
++destroys;
--live;
}
friend bool operator==(const CopyTracked& a, const CopyTracked& b) {
return a.value == b.value;
}
};
struct ThrowOnCopy {
inline static int copies_until_throw = 1000000;
inline static int copy_count = 0;
int value;
static void reset(int until = 1000000) {
copies_until_throw = until;
copy_count = 0;
}
explicit ThrowOnCopy(int v) : value(v) {}
ThrowOnCopy(const ThrowOnCopy& other) : value(other.value) {
if (++copy_count >= copies_until_throw) {
throw std::runtime_error("ThrowOnCopy");
}
}
ThrowOnCopy(ThrowOnCopy&& other) noexcept : value(other.value) {
other.value = -1;
}
ThrowOnCopy& operator=(const ThrowOnCopy& other) {
if (++copy_count >= copies_until_throw) {
throw std::runtime_error("ThrowOnCopy");
}
value = other.value;
return *this;
}
ThrowOnCopy& operator=(ThrowOnCopy&& other) noexcept {
value = other.value;
other.value = -1;
return *this;
}
friend bool operator==(const ThrowOnCopy& a, const ThrowOnCopy& b) {
return a.value == b.value;
}
};
struct ThrowOnMove {
inline static int moves_until_throw = 1000000;
inline static int move_count = 0;
int value;
static void reset(int until = 1000000) {
moves_until_throw = until;
move_count = 0;
}
explicit ThrowOnMove(int v) : value(v) {}
ThrowOnMove(const ThrowOnMove&) = delete;
ThrowOnMove& operator=(const ThrowOnMove&) = delete;
ThrowOnMove(ThrowOnMove&& other) : value(other.value) {
if (++move_count >= moves_until_throw) {
throw std::runtime_error("ThrowOnMove");
}
other.value = -1;
}
ThrowOnMove& operator=(ThrowOnMove&& other) {
if (++move_count >= moves_until_throw) {
throw std::runtime_error("ThrowOnMove");
}
value = other.value;
other.value = -1;
return *this;
}
};
template <typename T>
class CountingAllocator {
public:
using value_type = T;
struct Stats {
std::size_t allocs = 0;
std::size_t deallocs = 0;
std::size_t allocated_bytes = 0;
std::size_t constructs = 0;
std::size_t destroys = 0;
};
std::shared_ptr<Stats> stats = std::make_shared<Stats>();
int id = 0;
CountingAllocator() = default;
explicit CountingAllocator(int identity) : id(identity) {}
CountingAllocator(std::shared_ptr<Stats> s, int identity = 0)
: stats(std::move(s)), id(identity) {}
template <typename U>
CountingAllocator(const CountingAllocator<U>& other) noexcept
: stats(other.stats), id(other.id) {}
T* allocate(std::size_t n) {
++stats->allocs;
stats->allocated_bytes += n * sizeof(T);
return static_cast<T*>(::operator new(n * sizeof(T)));
}
void deallocate(T* ptr, std::size_t n) noexcept {
++stats->deallocs;
stats->allocated_bytes -= n * sizeof(T);
::operator delete(ptr);
}
template <typename U, typename... Args>
void construct(U* ptr, Args&&... args) {
++stats->constructs;
::new (static_cast<void*>(ptr)) U(std::forward<Args>(args)...);
}
template <typename U>
void destroy(U* ptr) noexcept {
++stats->destroys;
ptr->~U();
}
template <typename U>
bool operator==(const CountingAllocator<U>& other) const noexcept {
return stats == other.stats && id == other.id;
}
template <typename U>
bool operator!=(const CountingAllocator<U>& other) const noexcept {
return !(*this == other);
}
};
} // namespace test_types
tests/test_basic.cppStep 01–08 的主测试。
#include "mini_vector/vector.hpp"
#include "test_helpers.hpp"
#include <gtest/gtest.h>
#include <string>
#include <utility>
#include <vector>
using mini::Vector;
TEST(Step01, EmptyVectorHasZeroSizeAndCapacity) {
const Vector<int> v;
EXPECT_TRUE(v.empty());
EXPECT_EQ(v.size(), 0u);
EXPECT_EQ(v.capacity(), 0u);
EXPECT_EQ(v.data(), nullptr);
}
TEST(Step01, CountConstructorValueInitializes) {
const Vector<int> v(3);
ASSERT_EQ(v.size(), 3u);
EXPECT_GE(v.capacity(), 3u);
EXPECT_EQ(v[0], 0);
EXPECT_EQ(v[1], 0);
EXPECT_EQ(v[2], 0);
}
TEST(Step01, CountValueConstructor) {
const Vector<std::string> v(2, std::string("hi"));
ASSERT_EQ(v.size(), 2u);
EXPECT_EQ(v[0], "hi");
EXPECT_EQ(v[1], "hi");
}
TEST(Step01, InitializerListConstructor) {
const Vector<int> v{1, 2, 3, 4};
ASSERT_EQ(v.size(), 4u);
EXPECT_EQ(v[0], 1);
EXPECT_EQ(v[3], 4);
}
TEST(Step04, ReserveGrowsCapacityButNotSize) {
Vector<int> v;
v.reserve(8);
EXPECT_EQ(v.size(), 0u);
EXPECT_GE(v.capacity(), 8u);
EXPECT_NE(v.data(), nullptr);
}
TEST(Step04, ReserveSmallerThanCapacityIsNoop) {
Vector<int> v;
v.reserve(8);
const int* p = v.data();
const std::size_t cap = v.capacity();
v.reserve(2);
EXPECT_EQ(v.data(), p);
EXPECT_EQ(v.capacity(), cap);
}
TEST(Step04, ReserveKeepsExistingElements) {
Vector<int> v;
v.push_back(1);
v.push_back(2);
v.reserve(16);
ASSERT_EQ(v.size(), 2u);
EXPECT_EQ(v[0], 1);
EXPECT_EQ(v[1], 2);
}
TEST(Step05, PushBackGrowsGeometrically) {
Vector<int> v;
for (int i = 0; i < 10; ++i) {
v.push_back(i);
}
ASSERT_EQ(v.size(), 10u);
for (int i = 0; i < 10; ++i) {
EXPECT_EQ(v[i], i);
}
EXPECT_GE(v.capacity(), v.size());
}
TEST(Step05, PushBackLvalueAndRvalue) {
Vector<std::string> v;
std::string hello = "hello";
v.push_back(hello);
v.push_back(std::string("world"));
EXPECT_EQ(hello, "hello");
ASSERT_EQ(v.size(), 2u);
EXPECT_EQ(v.front(), "hello");
EXPECT_EQ(v.back(), "world");
}
TEST(Step05, EmplaceBackConstructsInPlace) {
Vector<std::pair<int, std::string>> v;
auto& added = v.emplace_back(7, "seven");
EXPECT_EQ(added.first, 7);
EXPECT_EQ(v.back().second, "seven");
EXPECT_EQ(&added, &v.back());
}
TEST(Step05, PushBackSelfReferenceIsSafe) {
Vector<std::string> v;
v.push_back("first");
for (int i = 0; i < 20; ++i) {
v.push_back(v[0]);
}
ASSERT_EQ(v.size(), 21u);
for (const auto& s : v) {
EXPECT_EQ(s, "first");
}
}
TEST(Step05, EmplaceBackReturnsReferenceToNewElement) {
Vector<int> v;
v.emplace_back(1);
int& x = v.emplace_back(2);
x = 42;
EXPECT_EQ(v.back(), 42);
}
TEST(Step03, PopBackRemovesLastElement) {
Vector<int> v{1, 2, 3};
v.pop_back();
ASSERT_EQ(v.size(), 2u);
EXPECT_EQ(v.back(), 2);
v.pop_back();
v.pop_back();
EXPECT_TRUE(v.empty());
}
TEST(Step03, ClearDestroysElementsButMayKeepCapacity) {
Vector<int> v{1, 2, 3};
const auto cap = v.capacity();
v.clear();
EXPECT_TRUE(v.empty());
EXPECT_EQ(v.size(), 0u);
EXPECT_EQ(v.capacity(), cap);
}
TEST(Step03, DestructorDestroysEveryElement) {
test_types::CopyTracked::reset();
{
Vector<test_types::CopyTracked> v;
v.emplace_back(1);
v.emplace_back(2);
v.emplace_back(3);
EXPECT_EQ(test_types::CopyTracked::live, 3);
}
EXPECT_EQ(test_types::CopyTracked::live, 0);
EXPECT_EQ(test_types::CopyTracked::constructs, test_types::CopyTracked::destroys);
}
TEST(Step06, ResizeGrowDefaultInserts) {
Vector<int> v{1, 2};
v.resize(5);
ASSERT_EQ(v.size(), 5u);
EXPECT_EQ(v[0], 1);
EXPECT_EQ(v[1], 2);
EXPECT_EQ(v[2], 0);
EXPECT_EQ(v[3], 0);
EXPECT_EQ(v[4], 0);
}
TEST(Step06, ResizeShrinkDestroysTail) {
Vector<int> v{1, 2, 3, 4};
v.resize(2);
ASSERT_EQ(v.size(), 2u);
EXPECT_EQ(v[0], 1);
EXPECT_EQ(v[1], 2);
}
TEST(Step06, ResizeWithValue) {
Vector<std::string> v{"a"};
v.resize(3, std::string("x"));
ASSERT_EQ(v.size(), 3u);
EXPECT_EQ(v[0], "a");
EXPECT_EQ(v[1], "x");
EXPECT_EQ(v[2], "x");
}
TEST(Step06, ResizeWithValueAliasingExistingElement) {
Vector<std::string> v{"keep"};
v.resize(8, v[0]);
ASSERT_EQ(v.size(), 8u);
for (const auto& s : v) {
EXPECT_EQ(s, "keep");
}
}
TEST(Step06, ResizeZeroClears) {
Vector<int> v{1, 2, 3};
v.resize(0);
EXPECT_TRUE(v.empty());
}
TEST(Step07, CopyConstructorDeepCopies) {
Vector<int> a{1, 2, 3};
Vector<int> b(a);
ASSERT_EQ(b.size(), 3u);
b[0] = 99;
EXPECT_EQ(a[0], 1);
EXPECT_EQ(b[0], 99);
}
TEST(Step07, MoveConstructorStealsStorage) {
Vector<int> a{1, 2, 3};
const int* p = a.data();
Vector<int> b(std::move(a));
EXPECT_EQ(b.data(), p);
EXPECT_EQ(b.size(), 3u);
EXPECT_EQ(a.size(), 0u);
EXPECT_EQ(a.data(), nullptr);
}
TEST(Step07, CopyAssignment) {
Vector<int> a{1, 2, 3};
Vector<int> b{9};
b = a;
EXPECT_EQ(b, a);
b[1] = 0;
EXPECT_EQ(a[1], 2);
}
TEST(Step07, MoveAssignment) {
Vector<int> a{1, 2, 3};
Vector<int> b{9};
b = std::move(a);
ASSERT_EQ(b.size(), 3u);
EXPECT_EQ(b[2], 3);
}
TEST(Step07, SelfAssignmentIsSafe) {
Vector<int> v{1, 2, 3};
Vector<int>& alias = v;
v = alias;
ASSERT_EQ(v.size(), 3u);
EXPECT_EQ(v[2], 3);
}
TEST(Step07, SwapExchangesContents) {
Vector<int> a{1, 2};
Vector<int> b{3, 4, 5};
swap(a, b);
ASSERT_EQ(a.size(), 3u);
ASSERT_EQ(b.size(), 2u);
EXPECT_EQ(a[0], 3);
EXPECT_EQ(b[0], 1);
}
TEST(Step07, InitializerListAssignment) {
Vector<int> v{1, 2};
v = {7, 8, 9};
ASSERT_EQ(v.size(), 3u);
EXPECT_EQ(v[1], 8);
}
TEST(Step08, AtThrowsWhenOutOfRange) {
Vector<int> v{1};
EXPECT_EQ(v.at(0), 1);
EXPECT_THROW((void)v.at(1), std::out_of_range);
}
TEST(Step08, IteratorsWalkTheRange) {
Vector<int> v{1, 2, 3};
int sum = 0;
for (int x : v) {
sum += x;
}
EXPECT_EQ(sum, 6);
auto it = v.begin();
*it = 10;
EXPECT_EQ(v.front(), 10);
}
TEST(Step08, ReverseIterators) {
Vector<int> v{1, 2, 3};
std::vector<int> reversed(v.rbegin(), v.rend());
ASSERT_EQ(reversed.size(), 3u);
EXPECT_EQ(reversed[0], 3);
EXPECT_EQ(reversed[2], 1);
}
TEST(Step08, EqualityComparesElementsNotCapacity) {
Vector<int> a;
a.reserve(32);
a.push_back(1);
a.push_back(2);
Vector<int> b{1, 2};
EXPECT_EQ(a, b);
}
TEST(Step08, ShrinkToFitReducesCapacityToSize) {
Vector<int> v;
v.reserve(32);
v.push_back(1);
v.shrink_to_fit();
EXPECT_EQ(v.capacity(), v.size());
EXPECT_EQ(v[0], 1);
}
tests/test_no_default_ctor.cpp没有默认构造函数的 T。
#include "mini_vector/vector.hpp"
#include "test_helpers.hpp"
#include <gtest/gtest.h>
#include <type_traits>
using mini::Vector;
using test_types::NoDefault;
template <typename V>
concept CanResizeCount = requires(V& v, typename V::size_type n) {
v.resize(n);
};
template <typename V>
concept CanResizeCountValue = requires(V& v, typename V::size_type n, const typename V::value_type& x) {
v.resize(n, x);
};
static_assert(!std::default_initializable<NoDefault>);
static_assert(!CanResizeCount<Vector<NoDefault>>);
static_assert(CanResizeCount<Vector<int>>);
static_assert(CanResizeCountValue<Vector<NoDefault>>);
static_assert(!std::is_constructible_v<Vector<NoDefault>, std::size_t>);
static_assert(std::is_constructible_v<Vector<int>, std::size_t>);
TEST(NoDefaultCtor, ResizeWithoutValueIsNotAvailable) {
SUCCEED();
}
TEST(NoDefaultCtor, CanPushAndEmplace) {
Vector<NoDefault> v;
v.emplace_back(1);
NoDefault x(2);
v.push_back(x);
v.push_back(NoDefault(3));
ASSERT_EQ(v.size(), 3u);
EXPECT_EQ(v[0].value, 1);
EXPECT_EQ(v[1].value, 2);
EXPECT_EQ(v[2].value, 3);
}
TEST(NoDefaultCtor, ResizeWithValueDoesNotNeedDefaultCtor) {
Vector<NoDefault> v;
v.emplace_back(7);
v.resize(4, NoDefault(9));
ASSERT_EQ(v.size(), 4u);
EXPECT_EQ(v[0].value, 7);
EXPECT_EQ(v[1].value, 9);
EXPECT_EQ(v[3].value, 9);
}
TEST(NoDefaultCtor, CountValueConstructorWorks) {
const Vector<NoDefault> v(3, NoDefault(4));
ASSERT_EQ(v.size(), 3u);
EXPECT_EQ(v[2].value, 4);
}
TEST(NoDefaultCtor, CopyAndMove) {
Vector<NoDefault> a;
a.emplace_back(1);
a.emplace_back(2);
Vector<NoDefault> b(a);
ASSERT_EQ(b.size(), 2u);
EXPECT_EQ(b[1].value, 2);
Vector<NoDefault> c(std::move(a));
ASSERT_EQ(c.size(), 2u);
EXPECT_EQ(c[0].value, 1);
}
TEST(NoDefaultCtor, ReserveDoesNotConstruct) {
Vector<NoDefault> v;
v.reserve(10);
EXPECT_EQ(v.size(), 0u);
EXPECT_GE(v.capacity(), 10u);
v.emplace_back(42);
EXPECT_EQ(v.front().value, 42);
}
tests/test_custom_allocator.cpp自定义分配器有没有真正被调用。
#include "mini_vector/vector.hpp"
#include "test_helpers.hpp"
#include <gtest/gtest.h>
using mini::Vector;
using test_types::CountingAllocator;
TEST(CustomAllocator, DefaultAllocatorIsStdAllocator) {
Vector<int> v;
auto alloc = v.get_allocator();
static_assert(std::is_same_v<decltype(alloc), std::allocator<int>>);
(void)alloc;
}
TEST(CustomAllocator, UsesProvidedAllocatorToAllocate) {
CountingAllocator<int> alloc;
auto stats = alloc.stats;
{
Vector<int, CountingAllocator<int>> v(alloc);
EXPECT_EQ(stats->allocs, 0u);
v.reserve(4);
EXPECT_EQ(stats->allocs, 1u);
EXPECT_EQ(stats->allocated_bytes, 4 * sizeof(int));
v.push_back(1);
v.push_back(2);
EXPECT_EQ(stats->constructs, 2u);
}
EXPECT_EQ(stats->deallocs, 1u);
EXPECT_EQ(stats->allocated_bytes, 0u);
EXPECT_EQ(stats->constructs, stats->destroys);
}
TEST(CustomAllocator, ConstructAndDestroyGoThroughAllocator) {
CountingAllocator<int> alloc;
auto stats = alloc.stats;
Vector<int, CountingAllocator<int>> v(alloc);
v.reserve(8);
v.emplace_back(1);
v.emplace_back(2);
v.emplace_back(3);
EXPECT_EQ(stats->constructs, 3u);
v.pop_back();
EXPECT_EQ(stats->destroys, 1u);
v.clear();
EXPECT_EQ(stats->destroys, 3u);
}
TEST(CustomAllocator, CopyConstructionSelectsAllocator) {
CountingAllocator<int> alloc;
Vector<int, CountingAllocator<int>> a(alloc);
a.push_back(10);
a.push_back(20);
Vector<int, CountingAllocator<int>> b(a);
ASSERT_EQ(b.size(), 2u);
EXPECT_EQ(b[0], 10);
EXPECT_EQ(b[1], 20);
}
TEST(CustomAllocator, GrowthDeallocatesOldBuffer) {
CountingAllocator<int> alloc;
auto stats = alloc.stats;
Vector<int, CountingAllocator<int>> v(alloc);
v.reserve(1);
EXPECT_EQ(stats->allocs, 1u);
v.push_back(1);
v.push_back(2); // 触发扩容
EXPECT_GE(stats->allocs, 2u);
EXPECT_GE(stats->deallocs, 1u);
}
TEST(CustomAllocator, EmptyAllocatorDoesNotBloatObject) {
struct EmptyAlloc {
using value_type = int;
int* allocate(std::size_t n) {
return static_cast<int*>(::operator new(n * sizeof(int)));
}
void deallocate(int* p, std::size_t) noexcept {
::operator delete(p);
}
bool operator==(const EmptyAlloc&) const noexcept {
return true;
}
};
using WithStd = Vector<int, std::allocator<int>>;
using WithEmpty = Vector<int, EmptyAlloc>;
EXPECT_LE(sizeof(WithEmpty), sizeof(WithStd));
}
tests/test_exception_safety.cpp抛异常后 size / 元素 / capacity 必须不变。
#include "mini_vector/vector.hpp"
#include "test_helpers.hpp"
#include <gtest/gtest.h>
#include <stdexcept>
#include <string>
using mini::Vector;
using test_types::ThrowOnCopy;
using test_types::ThrowOnMove;
TEST(ExceptionSafety, PushBackCopyThrowLeavesVectorUnchanged) {
ThrowOnCopy::reset(1000000);
Vector<ThrowOnCopy> v;
v.emplace_back(1);
v.emplace_back(2);
v.emplace_back(3);
const auto size = v.size();
const auto cap = v.capacity();
const auto first = v[0].value;
// 拷贝构造函数会抛：emplace_back(const&) 在扩容路径上先构造新元素。
ThrowOnCopy extra(99);
ThrowOnCopy::reset(1); // 下一次拷贝就抛
EXPECT_THROW(v.push_back(extra), std::runtime_error);
EXPECT_EQ(v.size(), size);
EXPECT_EQ(v.capacity(), cap);
EXPECT_EQ(v[0].value, first);
EXPECT_EQ(v[2].value, 3);
}
TEST(ExceptionSafety, ReserveCopyThrowLeavesVectorUnchanged) {
ThrowOnCopy::reset(1000000);
Vector<ThrowOnCopy> v;
v.emplace_back(1);
v.emplace_back(2);
// ThrowOnCopy 的移动是 noexcept，reserve 会走移动路径。
// 改用 std::string 不够“可控”，这里验证：抛异常后 size 仍正确。
ThrowOnCopy::reset(1000000);
EXPECT_NO_THROW(v.reserve(16));
EXPECT_EQ(v.size(), 2u);
EXPECT_EQ(v[0].value, 1);
EXPECT_EQ(v[1].value, 2);
}
TEST(ExceptionSafety, CopyConstructorThrowDoesNotLeak) {
ThrowOnCopy::reset(1000000);
Vector<ThrowOnCopy> v;
v.emplace_back(1);
v.emplace_back(2);
v.emplace_back(3);
ThrowOnCopy::reset(2); // 拷贝第二个元素时抛
EXPECT_THROW(Vector<ThrowOnCopy> copy(v), std::runtime_error);
}
TEST(ExceptionSafety, ResizeValueCopyThrowLeavesPrefixIntact) {
ThrowOnCopy::reset(1000000);
Vector<ThrowOnCopy> v;
v.emplace_back(1);
v.emplace_back(2);
ThrowOnCopy filler(7);
ThrowOnCopy::reset(1);
EXPECT_THROW(v.resize(5, filler), std::runtime_error);
EXPECT_EQ(v.size(), 2u);
EXPECT_EQ(v[0].value, 1);
EXPECT_EQ(v[1].value, 2);
}
TEST(ExceptionSafety, ResizeThrowDoesNotChangeCapacity) {
ThrowOnCopy::reset(1000000);
Vector<ThrowOnCopy> v;
v.emplace_back(1);
v.emplace_back(2);
const auto cap = v.capacity();
ThrowOnCopy filler(7);
// extra(value) 是第 1 次拷贝，fill 尾巴是第 2 次。
ThrowOnCopy::reset(2);
EXPECT_THROW(v.resize(32, filler), std::runtime_error);
EXPECT_EQ(v.size(), 2u);
EXPECT_EQ(v.capacity(), cap);
EXPECT_EQ(v[0].value, 1);
EXPECT_EQ(v[1].value, 2);
}
TEST(ExceptionSafety, MoveOnlyThrowOnEmplaceDuringRealloc) {
ThrowOnMove::reset(1000000);
Vector<ThrowOnMove> v;
v.emplace_back(1);
v.emplace_back(2);
// 下一次扩容时，搬迁旧元素的移动构造会抛。
// 先把容量顶满。
while (v.size() < v.capacity()) {
v.emplace_back(static_cast<int>(v.size()) + 1);
}
ThrowOnMove::reset(1);
const auto old_size = v.size();
EXPECT_THROW(v.emplace_back(99), std::runtime_error);
EXPECT_EQ(v.size(), old_size);
}
tests/test_move_only.cppunique_ptr 一类只移动类型。
#include "mini_vector/vector.hpp"
#include "test_helpers.hpp"
#include <gtest/gtest.h>
#include <memory>
#include <string>
#include <utility>
using mini::Vector;
using test_types::MoveOnly;
TEST(MoveOnly, EmplaceAndPushRvalue) {
Vector<MoveOnly> v;
v.emplace_back(1);
v.push_back(MoveOnly(2));
v.emplace_back(3);
ASSERT_EQ(v.size(), 3u);
EXPECT_EQ(v[0].value, 1);
EXPECT_EQ(v[1].value, 2);
EXPECT_EQ(v[2].value, 3);
}
TEST(MoveOnly, ReserveMovesElements) {
Vector<MoveOnly> v;
v.emplace_back(10);
v.emplace_back(20);
v.reserve(32);
ASSERT_EQ(v.size(), 2u);
EXPECT_EQ(v[0].value, 10);
EXPECT_EQ(v[1].value, 20);
}
TEST(MoveOnly, MoveConstructsTheVector) {
Vector<MoveOnly> a;
a.emplace_back(5);
a.emplace_back(6);
Vector<MoveOnly> b(std::move(a));
ASSERT_EQ(b.size(), 2u);
EXPECT_EQ(b[1].value, 6);
EXPECT_TRUE(a.empty());
}
TEST(MoveOnly, UniquePtrElements) {
Vector<std::unique_ptr<std::string>> v;
v.push_back(std::make_unique<std::string>("alpha"));
v.emplace_back(std::make_unique<std::string>("beta"));
ASSERT_EQ(v.size(), 2u);
EXPECT_EQ(*v[0], "alpha");
EXPECT_EQ(*v.back(), "beta");
auto taken = std::move(v.front());
EXPECT_EQ(*taken, "alpha");
EXPECT_EQ(v.front(), nullptr);
}
TEST(MoveOnly, CannotCopy) {
static_assert(!std::is_copy_constructible_v<Vector<MoveOnly>>);
static_assert(std::is_move_constructible_v<Vector<MoveOnly>>);
}
include/mini_vector/vector.hpp可选参考答案。抄作业时先别展开。
#pragma once
#include <concepts>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <memory>
#include <stdexcept>
#include <type_traits>
#include <utility>
namespace mini {
// 手搓 std::vector 的教学实现。
// 跟着 tutorial/ 一步步抄：每段逻辑都标了 Step 编号。
template <typename T, typename Allocator = std::allocator<T>>
class Vector {
public:
using value_type = T;
using allocator_type = Allocator;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using reference = T&;
using const_reference = const T&;
using pointer = typename std::allocator_traits<Allocator>::pointer;
using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;
using iterator = T*;
using const_iterator = const T*;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
private:
using AllocTraits = std::allocator_traits<Allocator>;
// Step 01: 三个核心状态。capacity_ 是已申请的槽位数，size_ 是已构造的元素数。
T* data_{nullptr};
size_type size_{0};
size_type capacity_{0};
// Step 02: 空分配器不占额外空间（C++20）。
[[no_unique_address]] Allocator alloc_{};
public:
// ---------------------------------------------------------------------
// 构造 / 析构
// ---------------------------------------------------------------------
Vector() noexcept(std::is_nothrow_default_constructible_v<Allocator>) = default;
explicit Vector(const Allocator& alloc) noexcept
: alloc_(alloc) {}
// 需要 T 能被 allocator 无参 construct（默认构造 / 值初始化）。
explicit Vector(size_type count, const Allocator& alloc = Allocator())
requires std::default_initializable<T>
: alloc_(alloc) {
if (count == 0) {
return;
}
data_ = allocate_n(count);
capacity_ = count;
try {
uninitialized_value_construct_n(data_, count);
size_ = count;
} catch (...) {
deallocate_n(data_, capacity_);
data_ = nullptr;
capacity_ = 0;
throw;
}
}
Vector(size_type count, const T& value, const Allocator& alloc = Allocator())
requires std::copy_constructible<T>
: alloc_(alloc) {
if (count == 0) {
return;
}
data_ = allocate_n(count);
capacity_ = count;
try {
uninitialized_fill_n(data_, count, value);
size_ = count;
} catch (...) {
deallocate_n(data_, capacity_);
data_ = nullptr;
capacity_ = 0;
throw;
}
}
Vector(std::initializer_list<T> init, const Allocator& alloc = Allocator())
requires std::copy_constructible<T>
: alloc_(alloc) {
const size_type count = init.size();
if (count == 0) {
return;
}
data_ = allocate_n(count);
capacity_ = count;
try {
uninitialized_copy_n(data_, init.begin(), count);
size_ = count;
} catch (...) {
deallocate_n(data_, capacity_);
data_ = nullptr;
capacity_ = 0;
throw;
}
}
Vector(const Vector& other)
requires std::copy_constructible<T>
: alloc_(AllocTraits::select_on_container_copy_construction(other.alloc_)) {
copy_from_range(other.data_, other.size_);
}
Vector(const Vector& other, const Allocator& alloc)
requires std::copy_constructible<T>
: alloc_(alloc) {
copy_from_range(other.data_, other.size_);
}
Vector(Vector&& other) noexcept
: data_(std::exchange(other.data_, nullptr)),
size_(std::exchange(other.size_, 0)),
capacity_(std::exchange(other.capacity_, 0)),
alloc_(std::move(other.alloc_)) {}
Vector(Vector&& other, const Allocator& alloc)
: alloc_(alloc) {
if (alloc_ == other.alloc_) {
data_ = std::exchange(other.data_, nullptr);
size_ = std::exchange(other.size_, 0);
capacity_ = std::exchange(other.capacity_, 0);
return;
}
move_from_range(other.data_, other.size_);
}
~Vector() {
destroy_range(data_, data_ + size_);
deallocate_n(data_, capacity_);
}
Vector& operator=(const Vector& other)
requires std::copy_constructible<T>
{
if (this == &other) {
return *this;
}
if constexpr (AllocTraits::propagate_on_container_copy_assignment::value) {
Vector tmp(other, other.alloc_);
alloc_ = other.alloc_;
swap_storage(tmp);
} else {
Vector tmp(other, alloc_);
swap_storage(tmp);
}
return *this;
}
Vector& operator=(Vector&& other) noexcept(
AllocTraits::propagate_on_container_move_assignment::value ||
AllocTraits::is_always_equal::value) {
if (this == &other) {
return *this;
}
if constexpr (AllocTraits::propagate_on_container_move_assignment::value) {
reset_storage();
steal_storage(other);
alloc_ = std::move(other.alloc_);
} else if (alloc_ == other.alloc_) {
reset_storage();
steal_storage(other);
} else {
Vector tmp(std::move(other), alloc_);
swap_storage(tmp);
}
return *this;
}
Vector& operator=(std::initializer_list<T> init)
requires std::copy_constructible<T>
{
Vector tmp(init, alloc_);
swap_storage(tmp);
return *this;
}
allocator_type get_allocator() const noexcept {
return alloc_;
}
// ---------------------------------------------------------------------
// 元素访问
// ---------------------------------------------------------------------
reference at(size_type index) {
if (index >= size_) {
throw std::out_of_range("mini::Vector::at");
}
return data_[index];
}
const_reference at(size_type index) const {
if (index >= size_) {
throw std::out_of_range("mini::Vector::at");
}
return data_[index];
}
reference operator[](size_type index) noexcept {
return data_[index];
}
const_reference operator[](size_type index) const noexcept {
return data_[index];
}
reference front() noexcept {
return data_[0];
}
const_reference front() const noexcept {
return data_[0];
}
reference back() noexcept {
return data_[size_ - 1];
}
const_reference back() const noexcept {
return data_[size_ - 1];
}
T* data() noexcept {
return data_;
}
const T* data() const noexcept {
return data_;
}
// ---------------------------------------------------------------------
// 迭代器
// ---------------------------------------------------------------------
iterator begin() noexcept {
return data_;
}
const_iterator begin() const noexcept {
return data_;
}
const_iterator cbegin() const noexcept {
return data_;
}
iterator end() noexcept {
return data_ + size_;
}
const_iterator end() const noexcept {
return data_ + size_;
}
const_iterator cend() const noexcept {
return data_ + size_;
}
reverse_iterator rbegin() noexcept {
return reverse_iterator(end());
}
const_reverse_iterator rbegin() const noexcept {
return const_reverse_iterator(end());
}
reverse_iterator rend() noexcept {
return reverse_iterator(begin());
}
const_reverse_iterator rend() const noexcept {
return const_reverse_iterator(begin());
}
// ---------------------------------------------------------------------
// 容量
// ---------------------------------------------------------------------
[[nodiscard]] bool empty() const noexcept {
return size_ == 0;
}
size_type size() const noexcept {
return size_;
}
size_type max_size() const noexcept {
const auto alloc_max = AllocTraits::max_size(alloc_);
const auto diff_max =
static_cast<size_type>(std::numeric_limits<difference_type>::max());
return alloc_max < diff_max ? alloc_max : diff_max;
}
size_type capacity() const noexcept {
return capacity_;
}
// Step 04: 只申请内存，不构造新元素。n <= capacity 时是空操作。
void reserve(size_type new_cap) {
if (new_cap <= capacity_) {
return;
}
reallocate(new_cap);
}
void shrink_to_fit() {
if (size_ == capacity_) {
return;
}
if (size_ == 0) {
deallocate_n(data_, capacity_);
data_ = nullptr;
capacity_ = 0;
return;
}
reallocate(size_);
}
// ---------------------------------------------------------------------
// 修改器
// ---------------------------------------------------------------------
void clear() noexcept {
destroy_range(data_, data_ + size_);
size_ = 0;
}
void push_back(const T& value)
requires std::copy_constructible<T>
{
emplace_back(value);
}
void push_back(T&& value) {
emplace_back(std::move(value));
}
// Step 05: 就地构造。扩容时先在新缓冲区构造新元素，再搬迁旧元素，
// 这样 push_back(v[0]) 这种“引用指向自己”的写法也是安全的。
template <typename... Args>
reference emplace_back(Args&&... args) {
if (size_ < capacity_) {
AllocTraits::construct(alloc_, data_ + size_, std::forward<Args>(args)...);
++size_;
return data_[size_ - 1];
}
const size_type new_cap = recommend_capacity(size_ + 1);
T* new_data = allocate_n(new_cap);
T* new_elem = nullptr;
try {
AllocTraits::construct(
alloc_, new_data + size_, std::forward<Args>(args)...);
new_elem = new_data + size_;
uninitialized_relocate_n(new_data, data_, size_);
} catch (...) {
if (new_elem != nullptr) {
AllocTraits::destroy(alloc_, new_elem);
}
deallocate_n(new_data, new_cap);
throw;
}
T* old_data = data_;
size_type old_cap = capacity_;
size_type old_size = size_;
data_ = new_data;
capacity_ = new_cap;
++size_;
destroy_range(old_data, old_data + old_size);
deallocate_n(old_data, old_cap);
return data_[size_ - 1];
}
void pop_back() {
AllocTraits::destroy(alloc_, data_ + size_ - 1);
--size_;
}
// Step 06: 无参 resize 需要 T 可默认构造；带值的 overload 不需要。
void resize(size_type count)
requires std::default_initializable<T>
{
if (count < size_) {
destroy_range(data_ + count, data_ + size_);
size_ = count;
return;
}
if (count == size_) {
return;
}
if (count <= capacity_) {
uninitialized_value_construct_n(data_ + size_, count - size_);
size_ = count;
return;
}
grow_buffer_and_append(count, [this](T* dest, size_type n) {
uninitialized_value_construct_n(dest, n);
});
}
void resize(size_type count, const T& value)
requires std::copy_constructible<T>
{
if (count < size_) {
destroy_range(data_ + count, data_ + size_);
size_ = count;
return;
}
if (count == size_) {
return;
}
// 先拷一份，避免 value 指向本 vector 内元素时重分配使引用失效。
T extra(value);
if (count <= capacity_) {
uninitialized_fill_n(data_ + size_, count - size_, extra);
size_ = count;
return;
}
grow_buffer_and_append(count, [this, &extra](T* dest, size_type n) {
uninitialized_fill_n(dest, n, extra);
});
}
void swap(Vector& other) noexcept {
using std::swap;
if constexpr (AllocTraits::propagate_on_container_swap::value) {
swap(alloc_, other.alloc_);
}
swap_storage(other);
}
friend bool operator==(const Vector& lhs, const Vector& rhs) {
if (lhs.size_ != rhs.size_) {
return false;
}
for (size_type i = 0; i < lhs.size_; ++i) {
if (!(lhs.data_[i] == rhs.data_[i])) {
return false;
}
}
return true;
}
friend bool operator!=(const Vector& lhs, const Vector& rhs) {
return !(lhs == rhs);
}
private:
// Step 02 -------------------------------------------------------------
T* allocate_n(size_type n) {
if (n == 0) {
return nullptr;
}
return std::to_address(AllocTraits::allocate(alloc_, n));
}
void deallocate_n(T* ptr, size_type n) noexcept {
if (ptr == nullptr) {
return;
}
AllocTraits::deallocate(alloc_, ptr, n);
}
// Step 03 -------------------------------------------------------------
void destroy_range(T* first, T* last) noexcept {
while (last != first) {
--last;
AllocTraits::destroy(alloc_, last);
}
}
void uninitialized_value_construct_n(T* dest, size_type n) {
size_type i = 0;
try {
for (; i < n; ++i) {
AllocTraits::construct(alloc_, dest + i);
}
} catch (...) {
destroy_range(dest, dest + i);
throw;
}
}
void uninitialized_fill_n(T* dest, size_type n, const T& value) {
size_type i = 0;
try {
for (; i < n; ++i) {
AllocTraits::construct(alloc_, dest + i, value);
}
} catch (...) {
destroy_range(dest, dest + i);
throw;
}
}
template <typename InputIt>
void uninitialized_copy_n(T* dest, InputIt src, size_type n) {
size_type i = 0;
try {
for (; i < n; ++i, ++src) {
AllocTraits::construct(alloc_, dest + i, *src);
}
} catch (...) {
destroy_range(dest, dest + i);
throw;
}
}
void uninitialized_move_n(T* dest, T* src, size_type n) {
size_type i = 0;
try {
for (; i < n; ++i) {
AllocTraits::construct(alloc_, dest + i, std::move(src[i]));
}
} catch (...) {
destroy_range(dest, dest + i);
throw;
}
}
// 能无异常移动就移动；否则若可拷贝就拷贝，给 push_back / reserve 强异常安全。
void uninitialized_relocate_n(T* dest, T* src, size_type n) {
if constexpr (std::is_nothrow_move_constructible_v<T> ||
!std::is_copy_constructible_v<T>) {
uninitialized_move_n(dest, src, n);
} else {
uninitialized_copy_n(dest, src, n);
}
}
// Step 04 -------------------------------------------------------------
size_type recommend_capacity(size_type min_cap) const {
const size_type max_n = max_size();
if (min_cap > max_n) {
throw std::length_error("mini::Vector::reserve");
}
size_type new_cap = 1;
if (capacity_ > 0) {
if (capacity_ > max_n / 2) {
new_cap = max_n;
} else {
new_cap = capacity_ * 2;
}
}
return new_cap < min_cap ? min_cap : new_cap;
}
void reallocate(size_type new_cap) {
T* new_data = allocate_n(new_cap);
try {
uninitialized_relocate_n(new_data, data_, size_);
} catch (...) {
deallocate_n(new_data, new_cap);
throw;
}
T* old_data = data_;
size_type old_cap = capacity_;
size_type old_size = size_;
data_ = new_data;
capacity_ = new_cap;
destroy_range(old_data, old_data + old_size);
deallocate_n(old_data, old_cap);
}
// 扩容并在尾巴上构造新元素。失败时旧缓冲区原封不动（含 capacity）。
template <typename TailCtor>
void grow_buffer_and_append(size_type count, TailCtor&& construct_tail) {
const size_type new_cap = recommend_capacity(count);
const size_type appended = count - size_;
T* new_data = allocate_n(new_cap);
bool tail_ok = false;
try {
construct_tail(new_data + size_, appended);
tail_ok = true;
uninitialized_relocate_n(new_data, data_, size_);
} catch (...) {
if (tail_ok) {
destroy_range(new_data + size_, new_data + count);
}
deallocate_n(new_data, new_cap);
throw;
}
T* old_data = data_;
size_type old_cap = capacity_;
size_type old_size = size_;
data_ = new_data;
capacity_ = new_cap;
size_ = count;
destroy_range(old_data, old_data + old_size);
deallocate_n(old_data, old_cap);
}
void copy_from_range(const T* src, size_type n) {
if (n == 0) {
return;
}
data_ = allocate_n(n);
capacity_ = n;
try {
uninitialized_copy_n(data_, src, n);
size_ = n;
} catch (...) {
deallocate_n(data_, capacity_);
data_ = nullptr;
capacity_ = 0;
throw;
}
}
void move_from_range(T* src, size_type n) {
if (n == 0) {
return;
}
data_ = allocate_n(n);
capacity_ = n;
try {
uninitialized_move_n(data_, src, n);
size_ = n;
} catch (...) {
deallocate_n(data_, capacity_);
data_ = nullptr;
capacity_ = 0;
throw;
}
}
void reset_storage() noexcept {
destroy_range(data_, data_ + size_);
deallocate_n(data_, capacity_);
data_ = nullptr;
size_ = 0;
capacity_ = 0;
}
void steal_storage(Vector& other) noexcept {
data_ = std::exchange(other.data_, nullptr);
size_ = std::exchange(other.size_, 0);
capacity_ = std::exchange(other.capacity_, 0);
}
void swap_storage(Vector& other) noexcept {
using std::swap;
swap(data_, other.data_);
swap(size_, other.size_);
swap(capacity_, other.capacity_);
}
};
template <typename T, typename Allocator>
void swap(Vector<T, Allocator>& lhs, Vector<T, Allocator>& rhs) noexcept {
lhs.swap(rhs);
}
} // namespace mini