C++中标准模板库std::vector的实现

以下实现了C++标准模板库std::vector的部分实现，参考了 cplusplus.

关于C++中标准模板库std::vector的介绍和用法可以参考 https://blog.csdn.net/fengbingchun/article/details/51510916

实现代码vector.hpp内容如下：

#ifndef FBC_STL_VECTOR_HPP_
#define FBC_STL_VECTOR_HPP_#include <stdlib.h>namespace fbcstd {template<class T>
class vector {
public:typedef size_t size_type;typedef T value_type;typedef T* iterator;typedef const T* const_iterator;vector();vector(size_type n, const value_type& val = value_type());vector(const vector& x);~vector();void reserve(size_type n);size_type capacity() const;size_type size() const;bool empty() const;value_type* data();const value_type* data() const;value_type& at(size_type n);const value_type& at(size_type n) const;value_type& operator [] (size_type n);const value_type& operator [] (size_type n) const;vector& operator = (const vector& x);void clear();value_type& back();const value_type& back() const;value_type& front();const value_type& front() const;void push_back(const value_type& val);void pop_back();void resize(size_type n, value_type val = value_type());iterator begin();const_iterator begin() const;iterator end();const_iterator end() const;private:size_type size_ = 0;size_type capacity_ = 0; // 2^nvalue_type* buffer_ = nullptr;}; // class vectortemplate<class T> inline
vector<T>::vector() : size_(0), capacity_(0), buffer_(nullptr)
{
}template<class T> inline
vector<T>::vector(size_type n, const value_type& val)
{reserve(n);size_ = n;for (size_t i = 0; i < n; ++i)buffer_[i] = val;
}template<class T> inline
vector<T>::vector(const vector& x)
{reserve(x.size_);size_ = x.size_;for (size_t i = 0; i < x.size_; ++i)buffer_[i] = x.buffer_[i];
}template<class T> inline
vector<T>::~vector()
{if (buffer_)delete [] buffer_;
}template<class T> inline
void vector<T>::reserve(size_type n)
{if (capacity_ < n) {delete [] buffer_;capacity_ = 1;if (capacity_ < n) {capacity_ = 2;while (capacity_ < n) {		capacity_ *= 2;}}buffer_ = new value_type[capacity_];}
}template<class T> inline
size_t vector<T>::capacity() const
{return capacity_;
}template<class T> inline
size_t vector<T>::size() const
{return size_;
}template<class T> inline
bool vector<T>::empty() const
{return size_ == 0 ? true : false;
}template<class T> inline
T* vector<T>::data()
{return buffer_;
}template<class T> inline
const T* vector<T>::data() const
{return buffer_;
}template<class T> inline
T& vector<T>::at(size_type n)
{if (size_ <= n) abort();return buffer_[n];
}template<class T> inline
const T& vector<T>::at(size_type n) const
{if (size_ <= n) abort();return buffer_[n];
}template<class T> inline
T& vector<T>::operator [] (size_type n)
{if (size_ <= n) abort();return buffer_[n];
}template<class T> inline
const T& vector<T>::operator [] (size_type n) const
{if (size_ <= n) abort();return buffer_[n];
}template<class T> inline
vector<T>& vector<T>::operator = (const vector& x)
{reserve(x.size_);size_ = x.size_;for (size_t i = 0; i < size_; ++i)buffer_[i] = x.buffer_[i];return *this;
}template<class T> inline
void vector<T>::clear()
{size_ = 0;
}template<class T> inline	
T& vector<T>::back()
{if (size_ == 0) abort();return buffer_[size_-1];
}template<class T> inline
const T& vector<T>::back() const
{if (size_ == 0) abort();return buffer_[size_-1];
}template<class T> inline	
T& vector<T>::front()
{if (size_ == 0) abort();return buffer_[0];
}template<class T> inline
const T& vector<T>::front() const
{if (size_ == 0) abort();return buffer_[0];
}template<class T> inline
void vector<T>::push_back(const value_type& val)
{if (size_ >= capacity_) {T* tmp = new T[size_];for (size_t i = 0; i < size_; ++i)tmp[i] = buffer_[i];reserve(size_+1);for (size_t i = 0; i < size_; ++i)buffer_[i] = tmp[i];delete [] tmp;}buffer_[size_] = val;size_ += 1;
}template<class T> inline
void vector<T>::pop_back()
{if (size_ == 0) abort();--size_;
}template<class T> inline
void vector<T>::resize(size_type n, value_type val)
{if (size_ < n) {if (n > capacity_) {T* tmp = new T[size_];for (size_t i = 0; i < size_; ++i)tmp[i] = buffer_[i];reserve(n);for (size_t i = 0; i < size_; ++i)buffer_[i] = tmp[i];delete [] tmp;}for (size_t i = size_; i < n; ++i)buffer_[i] = val;}size_ = n;
}template<class T> inline
T* vector<T>::begin()
{return buffer_;
}template<class T> inline
const T* vector<T>::begin() const
{return buffer_;
}template<class T> inline
T* vector<T>::end()
{return buffer_ + size_;
}template<class T> inline
const T* vector<T>::end() const
{return buffer_ + size_;
}template<class T> static inline
bool operator == (const vector<T>& lhs, const vector<T>& rhs)
{if (lhs.size() != rhs.size())return false;for (size_t i = 0; i < lhs.size(); ++i)	{if (lhs[i] != rhs[i])return false;}return true;
}template<class T> static inline
bool operator != (const vector<T>& lhs, const vector<T>& rhs)
{return !(lhs == rhs);
}template<class T> static inline
bool operator < (const vector<T>& lhs, const vector<T>& rhs)
{bool flag = true;if (lhs.size() == rhs.size()) {if (lhs == rhs) {flag = false;} else {for (size_t i = 0; i < lhs.size(); ++i) {if (lhs[i] > rhs[i]) {flag = false;break;}}}} else if (lhs.size() < rhs.size()) {vector<T> vec(lhs.size());for (size_t i = 0; i < lhs.size(); ++i)vec[i] = rhs[i];if (lhs == vec) {flag = true;} else {for (size_t i = 0; i < lhs.size(); ++i) {if (lhs[i] > rhs[i]) {flag = false;break;}}}} else {vector<T> vec(rhs.size());for (size_t i = 0; i < rhs.size(); ++i)vec[i] = lhs[i];if (vec == rhs) {flag = false;} else {for (size_t i = 0; i < rhs.size(); ++i) {if (lhs[i] > rhs[i]) {flag = false;break;}}}}return flag;
}template<class T> static inline
bool operator <= (const vector<T>& lhs, const vector<T>& rhs)
{return !(rhs < lhs);
}template<class T> static inline
bool operator > (const vector<T>& lhs, const vector<T>& rhs)
{return (rhs < lhs);
}template<class T> static inline
bool operator >= (const vector<T>& lhs, const vector<T>& rhs)
{return !(lhs < rhs);
}} // namespace fbcstd#endif // FBC_STL_VECTOR_HPP_ 

测试代码test_vector.cpp内容如下：

#include <iostream>
#include "vector.hpp"
#include "string.hpp"#define std fbcstdint main()
{{ // constructor, capacity, size, empty, datastd::vector<int> vec1;fprintf(stdout, "vec1 size: %d, capacity: %d, empty: %d\n", vec1.size(), vec1.capacity(), vec1.empty());std::vector<int> vec2(1);fprintf(stdout, "vec2 size: %d, capacity: %d, empty: %d\n", vec2.size(), vec2.capacity(), vec2.empty());fprintf(stdout, "vec2 data: %d\n", *(vec2.data()));std::vector<std::string> vec3(5, "test vector");fprintf(stdout, "vec3 size: %d, capacity: %d, empty: %d\n", vec3.size(), vec3.capacity(), vec3.empty());const std::string* p1 = vec3.data();fprintf(stdout, "vec3 data: \n");for (size_t i = 0; i < vec3.size(); ++i) {fprintf(stdout, " %s,", (*p1).c_str());p1++;}std::vector<std::string> vec4(vec3);fprintf(stdout, "\nvec4 size: %d, capacity: %d, empty: %d\n", vec4.size(), vec4.capacity(), vec4.empty());std::string* p2 = vec4.data();fprintf(stdout, "vec4 data: \n");for (size_t i = 0; i < vec4.size(); ++i)*p2++ = "TEST VECTOR";const std::string* p3 = vec4.data();for (size_t i = 0; i < vec4.size(); ++i) {fprintf(stdout, " %s,", (*p3).c_str());p3++;}fprintf(stdout, "\n");
}{ // at, [], =, clearstd::vector<std::string> vec1(2);vec1.at(0) = "test";vec1.at(1) = "vector";fprintf(stdout, "vec1: %s, %s\n", vec1.at(0).c_str(), vec1.at(1).c_str());vec1[0] = "TEST";vec1[1] = "VECTOR";fprintf(stdout, "vec1: %s, %s\n", vec1[0].c_str(), vec1[1].c_str());std::vector<std::string> vec2;vec2 = vec1;fprintf(stdout, "vec2 size: %d, %s, %s\n", vec2.size(), vec2[0].c_str(), vec2[1].c_str());vec2.clear();fprintf(stdout, "vec2 size: %d\n", vec2.size());
}{ // back, frontstd::vector<int> vec(2, 1000);fprintf(stdout, "value: %d\n", vec.back());vec.back() = -1000;fprintf(stdout, "value: %d\n", vec.back());fprintf(stdout, "value: %d\n", vec.front());vec.front() = -1000;fprintf(stdout, "value: %d\n", vec.front());
}{ // push_back, pop_backstd::vector<int> vec;for (int i = 0; i < 10; ++i)vec.push_back((i+1)*10);fprintf(stdout, "vec: size: %d, capacity: %d\nvalue: ", vec.size(), vec.capacity());for (int i = 0; i < vec.size(); ++i)fprintf(stdout, " %d,", vec[i]);for (int i = 0; i < 5; ++i)vec.pop_back();fprintf(stdout, "\nvec: size: %d, capacity: %d\nvalue: ", vec.size(), vec.capacity());for (int i = 0; i < vec.size(); ++i)fprintf(stdout, " %d,", vec[i]);fprintf(stdout, "\n");	
}{ // resizestd::vector<int> myvector;for (int i = 1; i < 10; ++i)myvector.push_back(i);myvector.resize(5);myvector.resize(8,100);myvector.resize(12);fprintf(stdout, "myvector contains:");for (size_t i = 0; i < myvector.size(); ++i)fprintf(stdout, " %d,", myvector[i]);fprintf(stdout, "\n");
}{ // begin, endstd::vector<int> myvector;for (int i = 1; i <= 5; ++i)myvector.push_back(i);fprintf(stdout, "myvector contains:");for (std::vector<int>::iterator it = myvector.begin() ; it != myvector.end(); ++it)fprintf(stdout, " %d,", *it);fprintf(stdout, "\n");for (std::vector<int>::const_iterator it = myvector.begin() ; it != myvector.end(); ++it)fprintf(stdout, " %d,", *it);fprintf(stdout, "\n");
}{ // compare operatorstd::vector<int> foo (3,100);std::vector<int> bar (2,200);if (foo == bar) fprintf(stdout, "foo and bar are equal\n");if (foo != bar) fprintf(stdout, "foo and bar are not equal\n");if (foo < bar) fprintf(stdout, "foo is less than bar\n");if (foo > bar) fprintf(stdout, "foo is greater than bar\n");if (foo <= bar)	fprintf(stdout, "foo is less than or equal to bar\n");if (foo >=bar)	fprintf(stdout, "foo is greater than or equal to bar\n");
}return 0;
}

CMakeLists.txt内容如下：

PROJECT(Samples_STL_Implementation)
CMAKE_MINIMUM_REQUIRED(VERSION 3.0)SET(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -g -Wall -O2 -std=c11")
SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}  -g -Wall -O2 -std=c++11")INCLUDE_DIRECTORIES(${PROJECT_SOURCE_DIR}/src)
MESSAGE(STATUS "project source dir: ${PROJECT_SOURCE_DIR}")FILE(GLOB tests ${PROJECT_SOURCE_DIR}/test/*.cpp)FOREACH (test ${tests})STRING(REGEX MATCH "[^/]+$" test_file ${test})STRING(REPLACE ".cpp" "" test_basename ${test_file})ADD_EXECUTABLE(${test_basename} ${test})TARGET_LINK_LIBRARIES(${test_basename} pthread)
ENDFOREACH()

build.sh脚本内容如下：

#! /bin/bashreal_path=$(realpath $0)
dir_name=`dirname "${real_path}"`
echo "real_path: ${real_path}, dir_name: ${dir_name}"new_dir_name=${dir_name}/build
mkdir -p ${new_dir_name}
cd ${new_dir_name}
cmake ..
makecd -

编译及执行操作步骤：将终端定位到Samples_STL_Implementation目录下，执行：$ ./build.sh , 然后再执行$ ./build/test_vector即可。

GitHub： https://github.com/fengbingchun/Linux_Code_Test