TinySTL

采用C++11实现一款简易的STL标准库，既是C++STL的一个子集（裁剪了一些容器和算法）又是一个超集（增加了一些容器和算法）

目的：练习数据结构与算法和C++ Template编程

编译环境：VS2013及以上版本

##开发计划：

STL的几大基本组件，如string、vector、list、deque、set、map、unordered_*等
STL算法库中的大部分算法
circular buffer
bitmap
skip list
binary search tree
AVL tree
rbtree
线段树
splay tree
rope
Van Emde Boas tree
treap
B-tree
trie
suffix array/tree
Disjoint-set data structure
k-d tree
R-tree
Matrix
Graph
bloom filter

##完成进度：

STL的几大基本组件
- type traits：100%
- 空间配置器：100%
- iterator traits：100%
- reverse_iterator：100%
- vector：100%
- string：100%
- priority_queue：100%
- stack：100%
- deque：100%
- queue：100%
- pair：100%
- list：90%
STL Algorithms:
- fill：100%
- fill_n：100%
- find：100%
- is_heap：100%
- min、max：100%
- make_heap：100%
- pop_heap：100%
- push_heap：100%
- sort_heap：100%
- swap：100%
- all_of：100%
- any_of：100%
- none_of：100%
- find_if：100%
- find_if_not：100%
- adjacent_find：100%
- count：100%
- count_if：100%
- mismatch：100%
其他组件：
- circular_buffer：100%
- bitmap：100%
- binary_search_tree：100%
- avl_tree：100%

#TinySTL测试: ###测试环境：Windows 7 && VS2013 && release模式 ###测试结果： ####(1):vector<int>

//std::vector<int> vec;
TinySTL::vector<int> vec;
ProfilerInstance::start();
int i = 0;
for (; i != 10000; ++i){
	vec.push_back(i);
}
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();

container	quantity	time(ms)
TinySTL::vector<int>	10万	2
TinySTL::vector<int>	100万	11
TinySTL::vector<int>	1000万	129
std::vector<int>	10万	6
std::vector<int>	100万	16
std::vector<int>	1000万	210
####(2):vector<string>

//std::vector<std::string> vec;
TinySTL::vector<std::string> vec;
ProfilerInstance::start();
int i = 0;
for (; i != 100000; ++i){
	vec.push_back(std::string("zouxiaohang"));
}
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();

container	quantity	time(ms)
TinySTL::vector<string>	10万	18
TinySTL::vector<string>	100万	181
TinySTL::vector<string>	1000万	2372
std::vector<string>	10万	29
std::vector<string>	100万	232
std::vector<string>	1000万	1972
####(3):circular_buffer<int, N>

TinySTL::circular_buffer<int, 10000> cb(10000, 0);
//boost::circular_buffer<int> cb(10000, 0);
ProfilerInstance::start();
for (int i = 0; i != 10000000; ++i){
	cb.push_back(i);
}
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();

container	quantity	time(ms)
TinySTL::circular_buffer	1000万	75
TinySTL::circular_buffer	10000万	604
TinySTL::circular_buffer	100000万	5936
boost::circular_buffer	1000万	22
boost::circular_buffer	10000万	252
boost::circular_buffer	100000万	2241
####(4):题目：利用bitmap找出str中未出现的字母

std::string str("abcdefghijklmnpqrstuvwxyz");
TinySTL::bitmap<26> bm;
for (auto it = str.cbegin(); it != str.cend(); ++it){
	bm.set(*it - 'a');
}
cout << bm << endl;
cout << bm.size() << endl;
for (int i = 0; i != 26; ++i){
	if (!bm.test(i))
		cout << "字母" << (char)('a' + i) << "没出现！！！" << endl;
}

输出结果：

111111111111110111111111111000000
32  
字母o没出现！！！

####(5):string

//std::string str;
TinySTL::string str;
ProfilerInstance::start();
int i = 0;
for (; i != 1000000; ++i){
	str.push_back('x');
}
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();

container	quantity	time(ms)
TinySTL::string	100万	7
TinySTL::string	1000万	39
TinySTL::string	10000万	484
std::string	100万	37
std::string	1000万	229
std::string	10000万	1965

####(6):priority_queue<int>

//std::priority_queue<int> pq;
TinySTL::priority_queue<int> pq;
ProfilerInstance::start();
int i = 0;
for (; i != 100000; ++i){
	pq.push(i);
}
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();

container	quantity	time(ms)
TinySTL::priority_queue<int>	10万	13
TinySTL::priority_queue<int>	100万	97
TinySTL::priority_queue<int>	1000万	1032
std::priority_queue<int>	10万	12
std::priority_queue<int>	100万	67
std::priority_queue<int>	1000万	752

TinySTL::vector<int> v;
int i = 0;
for (; i != 100000; ++i){
	v.push_back(i);
}
//std::priority_queue<int> pq(v.begin(), v.end());
TinySTL::priority_queue<int> pq(v.begin(), v.end());
ProfilerInstance::start();
for (i = 0; i != 100000; ++i){
	pq.pop();
}
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();

container	quantity	time(ms)
TinySTL::priority_queue<int>	10万	19
TinySTL::priority_queue<int>	100万	137
TinySTL::priority_queue<int>	1000万	1532
std::priority_queue<int>	10万	7
std::priority_queue<int>	100万	92
std::priority_queue<int>	1000万	1214

####(7):binary_search_tree<string>

ifstream f;
char buff[256] = { 0 };
std::string word;
f.open("C:\\Users\\zxh\\Desktop\\text.txt");
TinySTL::vector<TinySTL::string> v;
while (f.good()){
	f >> word;
	std::copy(word.begin(), word.end(), buff);
	v.push_back(TinySTL::string(buff, buff + word.size()));
}
TinySTL::binary_search_tree<TinySTL::string> sbst;
ProfilerInstance::start();
for (const auto& word : v){
	sbst.insert(word);
}
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();
f.close();

container	quantity	time(ms)
TinySTL::binary_search_tree<string>	44067	16
TinySTL::binary_search_tree<string>	169664	64
TinySTL::binary_search_tree<string>	438230	277

####(8):deque<int>

//std::deque<int> dq;
TinySTL::deque<int> dq;
ProfilerInstance::start();
const int max = 10000000;
int i = 0;
for (; i != max / 2; ++i){
	dq.push_front(i);
}
for (; i != max; ++i){
	dq.push_back(i);
}
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();

container	quantity	time(ms)
TinySTL::deque<int>	10万	15
TinySTL::deque<int>	100万	78
TinySTL::deque<int>	1000万	1186
std::deque<int>	10万	90
std::deque<int>	100万	1087
std::deque<int>	1000万	4835
#####ps：这个性能差距的原因1是内部实现的机制不同，我的deque是预先分配内存因此相同条件下占用的内存更多，而stl的deque是需要的时候再分配，更加节省内存；2是stl的deque实现了更多更灵活的插入删除操作，我只是实现了在头尾的插入和删除

####(9):avl_tree<int> TinySTL::binary_search_tree bst; TinySTL::avl_tree avlt; for (int i = 0; i != 10000; ++i){ avlt.insert(i); bst.insert(i); } cout << "binary_search_tree height = " << bst.height() << endl; cout << "avl_tree height = " << avlt.height() << endl; 输出结果：

binary_search_tree height = 10000
avl_tree height = 14

####(10):list<int>

TinySTL::list<int> list;
//std::list<int> list;
const size_t max = 100000;
ProfilerInstance::start();
for (size_t i = 0; i != max; ++i)
	list.push_back(i);
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();

container	quantity	time(ms)
TinySTL::list<int>	10万	4
TinySTL::list<int>	100万	33
TinySTL::list<int>	1000万	286
std::list<int>	10万	189
std::list<int>	100万	1774
std::list<int>	1000万	17571

anti-mage / tinystl Goto Github PK

tinystl's Introduction

TinySTL

tinystl's People

Contributors

Watchers

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent