目录
一.string
二.vector
三.list
四.stack
五.queue
六.priority_queue
一.string
#pragma once
namespace hebre
{
class string
{
public:
typedef char* iterator;
typedef const char* const_iterator;
//Member functions
string()
:_str(new char[1]{'\0'})
,_size(0)
,_capacity(0)
{}
string(const string& str)
{
_size = str._size;
_capacity = str._capacity;
_str = new char[_size + 1];
strcpy(_str, str._str);
}
string(const string& str, size_t pos, size_t len = npos)
{
if (len > _size - pos)
{
len = _size - pos;
}
_str = new char[len + 1];
_capacity = _size = len;
size_t i = 0;
size_t n = len;
while (n--)
{
_str[i] = str._str[pos];
i++;
pos++;
}
_str[len] = '\0';
}
string(const char* s)
{
_size = strlen(s);
_capacity = _size;
_str = new char[_size + 1];
strcpy(_str, s);
}
string(const char* s, size_t n)
{
_size = n;
_capacity = n;
_str = new char[n + 1];
size_t i = 0;
while (i < n)
{
_str[i] = s[i];
i++;
}
_str[_size] = '\0';
}
string(size_t n, char c)
{
_size = n;
_capacity = n;
_str = new char[n + 1];
size_t i = 0;
while (i < n)
{
_str[i] = c;
}
_str[_size] = '\0';
}
template<class InputIterator>
string(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
~string()
{
delete[] _str;
_str = nullptr;
_size = 0;
_capacity = 0;
}
string& operator= (const char* s)
{
string tmp(s);
swap(tmp);
return *this;
}
string& operator=(string s)
{
swap(s);
return *this;
}
//Iterators
iterator begin()
{
return _str;
}
const_iterator begin() const
{
return _str;
}
iterator end()
{
return _str + _size;
}
const_iterator end() const
{
return _str + _size;
}
//Capacity
size_t size() const
{
return _size;
}
void resize(size_t n, char c = '\0')
{
if (n <= _size)
{
_str[n - 1] = '\0';
_size = n;
}
else
{
if (n > _capacity)
{
reserve(n);
}
for (size_t i = _size; i < n; i++)
{
_str[i] = '\0';
_size = n;
}
}
}
size_t capacity() const
{
return _capacity;
}
void reserve(size_t n = 0)
{
if (n > _capacity)
{
char* newstr = new char[n + 1];
// 避免浅拷贝，允许自定义类型的使用
// 联系string(InputIterator first, InputIterator last)
for (int i = 0; i < _size; i++)
{
newstr[i] = _str[i];
}
delete[] _str;
_str = newstr;
_capacity = n;
}
}
void clear()
{
_str[0] = '\0';
_size = 0;
}
bool empty() const
{
return _size == 0;
}
//Element access
char& operator[] (size_t pos)
{
assert(pos <= _size);
return _str[pos];
}
const char& operator[] (size_t pos) const
{
assert(pos <= _size);
return _str[pos];
}
char& at(size_t pos)
{
assert(pos <= _size);
return _str[pos];
}
const char& at(size_t pos) const
{
assert(pos <= _size);
return _str[pos];
}
char& back()
{
return _str[_size - 1];
}
const char& back() const
{
return _str[_size - 1];
}
char& front()
{
return _str[0];
}
const char& front() const
{
return _str[0];
}
//Modifiers:
string& operator+= (char c)
{
push_back(c);
return *this;
}
string& operator+= (const char* s)
{
insert(_size, s);
return *this;
}
string& append(const char* s)
{
insert(_size, s);
return *this;
}
void push_back(char c)
{
insert(_size, 1, c);
}
string& assign(const char* s)
{
clear();
insert(0, s);
return *this;
}
string& insert(size_t pos, size_t n, char c)
{
assert(pos <= _size);
if (_size == _capacity)
{
size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;
reserve(newcapacity);
}
size_t end = _size + n;
while (end >= pos + n)
{
_str[end] = _str[end - n];
end--;
}
for (int i = 0; i < n; i++)
{
_str[pos + i] = c;
}
_size++;
return *this;
}
string& insert(size_t pos, const char* s)
{
assert(pos <= _size);
size_t len = strlen(s);
size_t newcapacity = len+_size;
if (newcapacity > _capacity)
{
reserve(newcapacity);
}
size_t end = _size + len;
while (end >= pos+len)
{
_str[end] = _str[end - len];
end--;
}
for (int i = 0; i < len; i++)
{
_str[pos+i] = s[i];
}
_size += len;
return *this;
}
string& erase(size_t pos = 0, size_t len = npos)
{
if (len > _size - pos)
{
len = _size - pos;
}
size_t end = pos + len;
while (end <=_size)
{
_str[end - len] = _str[end];
end++;
}
_size -= len;
return *this;
}
void pop_back()
{
erase(_size - 1);
}
void swap(string& str)
{
std::swap(_str, str._str);
std::swap(_size, str._size);
std::swap(_capacity, str._capacity);
}
//String operations
const char* c_str() const
{
return _str;
}
size_t find(char c, size_t pos = 0) const
{
assert(pos < _size);
size_t i = pos;
while (i <= _size - 1)
{
if (_str[i] == c)
{
return _str[i];
}
}
return npos;
}
size_t find(const char* s, size_t pos = 0) const
{
assert(pos < _size);
char* ptr = strstr(_str, s);
if (ptr != nullptr)
{
return ptr - _str;
}
return npos;
}
string substr(size_t pos = 0, size_t len = npos) const
{
assert(pos < _size);
if (len > _size - pos)
{
len = _size - pos;
}
string str(_str + pos, len);
return str;
}
private:
size_t _size;
size_t _capacity;
char* _str;
public:
static size_t npos;
};
size_t string::npos = -1;
//Non-member function overloads
void swap(string& s1, string& s2)
{
s1.swap(s2);
}
bool operator== (const string& lhs, const string& rhs)
{
return strcmp(lhs.c_str(), rhs.c_str()) == 0;
}
bool operator!= (const string& lhs, const string& rhs)
{
return !(lhs == rhs);
}
bool operator< (const string& lhs, const string& rhs)
{
return strcmp(lhs.c_str(), rhs.c_str()) < 0;
}
bool operator<= (const string& lhs, const string& rhs)
{
return lhs < rhs || lhs == rhs;
}
bool operator> (const string& lhs, const string& rhs)
{
return !(lhs <= rhs);
}
bool operator>= (const string& lhs, const string& rhs)
{
return !(lhs < rhs);
}
ostream& operator << (ostream& out, const string& str)
{
for (size_t i = 0; i < str.size(); i++)
{
out << str[i];
}
return out;
}
istream& operator>>(istream& in, string& str)
{
str.clear();
char c;
char buffer[256];
size_t i = 0;
c = in.get();
while (c != ' ' && c != '\n')
{
buffer[i++] = c;
if (i == 255)
{
buffer[i] = '\0';
str += buffer;
i = 0;
}
c = in.get();
c = in.get();
}
if (i > 0)
{
buffer[i] = '\0';
str += buffer;
}
return in;
}
istream& getline(istream& is, string& str, char delim = '\n')
{
str.clear();
int i = 0;
char buffer[256];
char ch;
ch = is.get();
while (ch != delim)
{
// 放到buff
buffer[i++] = ch;
if (i == 255)
{
buffer[i] = '\0';
str += buffer;
i = 0;
}
ch = is.get();
}
if (i > 0)
{
buffer[i] = '\0';
str += buffer;
}
return is;
}
}二.vector
#pragma once
namespace hebre
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//Member functions
vector()
{}
//initializer_list是一个类，支持迭代器
//底层相当于开了一块数组的空间
vector(initializer_list<T> il)
{
reserve(il.size());
for (auto e : il)
{
push_back(e);
}
}
// 这里的第一个参数必须是一个int类型
// 如果参数类型是size_t的话
// 调用函数会与vector(InputIterator first, InputIterator last)函数更加的适配
// 编译器就会优先调用vector(InputIterator first, InputIterator last)函数
// 我们如果使用int类型的话，才会更加适配
vector(int n, const T& val = T())
{
while (n--)
{
push_back(val);
}
}
vector(const vector<T>& v)
{
size_t len = v.capacity();
reserve(len);
for (auto& e : v)
{
push_back(e);
}
}
// 类模板的成员函数，也可以是一个函数模板。例如：list，string
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
~vector()
{
delete[] _start;
_start = nullptr;
_finish = nullptr;
_endofstorage = nullptr;
}
vector& operator= (const vector& x)
{
for (auto e : x)
{
push_back(e);
}
return *this;
}
//Iterators:
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
//Capacity:
size_t size()
{
return _finish - _start;
}
const size_t size() const
{
return _finish - _start;
}
void resize(size_t n, T val = T())
{
if (n <= size())
{
_finish = _start + n;
}
else
{
if (n > capacity)
{
reserve(n);
}
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
size_t capacity() const
{
return _endofstorage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldsize = size();//size()在过程中会出错，因为_start会改变，_finish还保留着原来的值
T* tmp;
tmp = new T[n];
if (_start)
{
// 浅拷贝，不能拷贝自定义类型
// memcpy(tmp, _start, sizeof(T) * oldSize);
for (int i = 0; i < size(); i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldsize;
_endofstorage = _start + n;
}
}
bool empty() const
{
return _start == _finish;
}
//Element access:
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
T& at(size_t i)
{
assert(i < size());
return _start[i];
}
const T& at(size_t i) const
{
assert(i < size());
return _start[i];
}
T& front()
{
return _start[0];
}
const T& front() const
{
return _start[0];
}
T& back()
{
return _start[size() - 1];;
}
const T& back() const
{
return _start[size() - 1];
}
//Modifiers:
iterator insert(const_iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
size_t len = pos - _start;
iterator p = _start + len;
if (_finish == _endofstorage)
{
size_t len = p - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
p = _start + len;
}
iterator i = _finish - 1;
while (i >= p)
{
*(i + 1) = *i;
--i;
}
*p = x;
++_finish;
return p;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator i = pos + 1;
while (i < _finish)
{
*(i - 1) = *i;
++i;
}
_finish--;
return pos;
}
void push_back(const T& x)
{
insert(_finish, x);
}
void pop_back()
{
assert(!empty());
--_finish;
}
void swap(vector<T>& x)
{
std::swap(_start, x._start);
std::swap(_finish, x._finish);
std::swap(_endofstorage, x._endofstorage);
}
void clear()
{
_finish = _start;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
//Non-member function overloads
template <class T>
void swap(vector<T>& x, vector<T>& y)
{
x.swap(y);
}
template<class T>
void swap(T& x, T& y)
{
std::swap(x, y);
}
}三.list
#pragma once
namespace hebre
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
list_node(const T& val = T())
: _data(val)
, _next(nullptr)
, _prev(nullptr)
{}
};
template<class T,class Dereference,class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Dereference, Ptr> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Dereference operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
void empty_init()
{
_node = new Node();
_node->_next = _node;
_node->_prev = _node;
_size = 0;
}
list()
{
empty_init();
}
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
first++;
}
}
//注意：n的数据类型必须是int,原因在上面的构造函数
list(int n, const T& val = T())
{
empty_init();
while (n--)
{
push_back(val);
}
}
list(const list& x)
{
empty_init();
for (auto e : x)
{
push_back(e);
}
}
list(initializer_list<T> il)
{
empty_init();
for (auto e : il)
{
push_back(e);
}
}
~list()
{
clear();
delete _node;
_node = nullptr;
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
//Iterators:
iterator begin()
{
return iterator(_node->_next);
}
const_iterator begin() const
{
return const_iterator(_node->_next);
}
iterator end()
{
return iterator(_node);
}
const_iterator end() const
{
return const_iterator(_node);
}
//Capacity:
bool empty() const
{
return _node->_next == _node;
}
size_t size() const
{
return _size;
}
T& front()
{
return _node->_next;
}
const T& front() const
{
return _node->_next;
}
T& back()
{
return _node->_prev;
}
const T& back() const
{
return _node->_prev;
}
//Modifiers:
template <class InputIterator>
void assign(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
iterator insert(iterator position, const T& val)
{
Node* cur = position._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
_size++;
return iterator(newnode);
}
iterator erase(iterator position)
{
Node* cur = position._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
prev->_next = next;
next->_prev = prev;
_size--;
delete cur;
cur = nullptr;
return iterator(prev);
}
void swap(list<T>& x)
{
std::swap(_node, x._node);
std::swap(_size, x._size);
}
void resize(size_t n, T val = T())
{
if (n < _size)
{
size_t x = _size - n;
while (x--)
{
pop_back();
}
}
else
{
size_t x = n - _size;
while (x--)
{
push_back(val);
}
}
}
void clear()
{
while (_node->_next != _node)
{
pop_back();
}
}
private:
Node* _node;
size_t _size;
};
}四.stack
#pragma once
#include<deque>
namespace hebre
{
template<class T, class Container = deque<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top() const
{
return _con.back();
}
T& top()
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
void swap(stack& x)
{
_con.swap(x);
}
private:
Container _con;
};
}五.queue
#pragma once
#include<deque>
namespace hebre
{
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
size_t size()
{
return _con.size();
}
T& front()
{
return _con.front();
}
const T& front() const
{
return _con.front();
}
T& back()
{
return _con.back();
}
const T& back() const
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}六.priority_queue
#pragma once
#include<deque>
namespace hebre
{
//默认为升序排序
template<class T, class Container = deque<T>>
class priority_queue
{
public:
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (_con[child] < _con[parent])
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && _con[child] > _con[child + 1])
{
child++;
}
if (_con[parent] > _con[child])
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& val)
{
_con.push_back(val);
AdjustUp(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
bool empty() const
{
return _con.empty();
}
T& top()
{
return _con[0];
}
const T& top() const
{
return _con[0];
}
size_t size() const
{
return _con.size();
}
private:
Container _con;
};
}