Skip to content

Latest commit

 

History

History
600 lines (499 loc) · 15.6 KB

README.md

File metadata and controls

600 lines (499 loc) · 15.6 KB
Raw

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
  • segment tree
  • 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：100%
    • unordered_set：100%
    • unique_ptr：100%
    • shared_ptr：100%
    • cow_ptr：100%
  • 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%
    • equal：100%
    • is_permutation：100%
    • search：100%
    • advance：100%
    • sort：100%
    • generate：100%
    • generate_n：100%
    • distance：100%
    • copy：100%
  • 其他组件：
    • circular_buffer：100%
    • bitmap：100%
    • binary_search_tree：100%
    • avl_tree：100%
    • suffix_array：100%
    • directed_graph：100%
    • trie tree：100%
    • Disjoint-set data structure：100%

##TinySTL单元测试(原单元测试代码逐步)：

  • pair：100%
  • algorithm：20%
  • vector：100%
  • string：100%
  • priority_queue：100%
  • suffix_array：100%
  • queue：100%
  • stack：100%
  • bitmap：100%
  • circular_buffer：100%
  • deque：100%
  • list：100%
  • binary_search_tree：100%
  • avl_tree：100%
  • unordered_set：100%
  • directed_graph：100%
  • trie tree：100%
  • unique_ptr：100%
  • shared_ptr：100%
  • Disjoint-set data structure：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()));
	v.push_back(word);
}
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

####(11):list<int>::sort()

TinySTL::list<int> list1;
std::list<int> list2;
std::default_random_engine dre;
std::uniform_int_distribution<int> id;
const size_t max = 10000;
for (int i = 0; i != max; ++i){
	auto n = id(dre);
	list1.push_back(n);
	list2.push_back(n);
}
double cost1 = 0.0, cost2 = 0.0;
for (int i = 0; i != 100; ++i){
	ProfilerInstance::start();
	list1.sort();//TinySTL::list<int>
	ProfilerInstance::finish();
	cost1 += ProfilerInstance::millisecond();

	ProfilerInstance::start();
	list2.sort();//std::list<int>
	ProfilerInstance::finish();
	cost2 += ProfilerInstance::millisecond();
}
cout << "TinySTL time: " << cost1 / 100 << "ms" << endl;
cout << "std time: " << cost2 / 100 << "ms" << endl;
container quantity time(ms)
TinySTL::list<int> 1万 0.88
TinySTL::list<int> 10万 17.621
TinySTL::list<int> 100万 591.354
std::list<int> 1万 1.25
std::list<int> 10万 35.692
std::list<int> 100万 665.128

####(12):suffix_array

char arr[] = { 'a', 'a', 'b', 'a', 'a', 'a', 'a', 'b' };
TinySTL::suffix_array sa(arr, 8);
auto suffixArray = sa.suffixArray();
auto rankArray = sa.rankArray();
auto heightArray = sa.heightArray();

TinySTL::Test::print_container(suffixArray, "suffixArray");
TinySTL::Test::print_container(rankArray, "rankArray");
TinySTL::Test::print_container(heightArray, "heightArray");

image

####(13):unordered_set<int>

TinySTL::Unordered_set<int> ust(10);
//std::unordered_set<int> ust(10);
const size_t insert_count = 1000000;
const uint64_t query_count = 100000000;
//calculate total insert time
ProfilerInstance::start();
for (size_t i = 0; i != insert_count; ++i){
	ust.insert(i);//per insert time
}
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();

//calculate total query time
ProfilerInstance::start();
for (uint64_t i = 0; i != query_count; ++i){
	ust.count(i);//per query time
}
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();
container quantity insert time(ms) query time(ms)
TinySTL::unordered_set<int> 1万/1亿 8 97
TinySTL::unordered_set<int> 10万/10亿 139 1000
TinySTL::unordered_set<int> 100万/100亿 1214 9546
std::unordered_set<int> 1万/1亿 64 101
std::unordered_set<int> 10万/10亿 884 953
std::unordered_set<int> 100万/100亿 2781 9682

####(14):sort

std::random_device rd;
const int len = 10000000;
int arr[len];
std::generate(std::begin(arr), std::end(arr), [&rd](){return rd(); });
ProfilerInstance::start();
TinySTL::sort(std::begin(arr), std::end(arr));
//std::sort(std::begin(arr), std::end(arr));
ProfilerInstance::finish();
ProfilerInstance::dumpDuringTime();
algorithm quantity time(ms)
TinySTL::sort 10万 11
TinySTL::sort 100万 133
TinySTL::sort 1000万 1547
std::sort 10万 13
std::sort 100万 147
std::sort 1000万 1730

####(15):directed_graph

template<class Index, class Value>
using dGraph = TinySTL::directed_graph < Index, Value > ;
dGraph<int, int> g;
dGraph<int, int>::nodes_set_type set1, set2, set3;
set1.push_back(g.make_node(1, 11));
set1.push_back(g.make_node(2, 22));
set1.push_back(g.make_node(3, 33));
g.add_node(g.make_node(0, 0), set1);

set2.push_back(g.make_node(5, 55));
set2.push_back(g.make_node(6, 66));
set2.push_back(g.make_node(7, 77));
g.add_node(g.make_node(1, 11), set2);

set3.push_back(g.make_node(12, 1212));
set3.push_back(g.make_node(13, 1313));
set3.push_back(g.make_node(14, 1414));
g.add_node(7, set3);

g.make_edge(12, 2);
g.make_edge(12, 3);
g.make_edge(12, 0);
std::cout << "graph after add nodes:" << std::endl;
std::cout << g.to_string();

auto func = [](const dGraph<int, int>::node_type& node){
	std::cout << "[" << node.first << "," << node.second << "]" << std::endl;
};
std::cout << "graph DFS from node(1, 11):" << std::endl;
g.DFS(1, func);
std::cout << "graph BFS from node(1, 11):" << std::endl;
g.BFS(1, func);

std::cout << "graph after delete node(7, 77):" << std::endl;
g.delete_node(dGraph<int, int>::node_type(7, 77));
std::cout << g.to_string();

image
image
image
image

####(16):trie tree

TinySTL::trie_tree t;
std::ifstream in;
in.open("C:\\Users\\zxh\\Desktop\\trie_tree_test.txt");
std::vector<std::string> v;
std::string s;
while (in){
	in >> s;
	v.push_back(s);
}
ProfilerInstance::start();
for (const auto& str : v){
	t.insert(TinySTL::string(str.data()));
}
ProfilerInstance::finish();
std::cout << "build trie tree costs " << ProfilerInstance::millisecond() << "ms" << std::endl;

ProfilerInstance::start();
auto res = t.get_word_by_prefix("v");
ProfilerInstance::finish();
std::cout << "get word by prefix \"v\" costs " << ProfilerInstance::millisecond() << "ms" << std::endl;
auto i = 0;
for (const auto& str : res){
	++i;
	if (i % 10 == 0) std::cout << std::endl;
	std::cout << str << " ";
}
std::cout << std::endl;

image

####(17):shared_ptr

shared_ptr<string> sp1(new string("hello"));
assert(sp1.use_count() == 1);
assert(*sp1 == "hello");
sp1->append(" world");
assert(*sp1 == "hello world");

{
	auto sp2 = sp1;
	assert(sp1.use_count() == 2);
}
assert(sp1.use_count() == 1);

####(18):unique_ptr

auto up = make_unique<string>(10, '0');
up->append("111");
assert(*up == "0000000000111");

up.release();
assert(up == nullptr);

up.reset(new string("hello"));
assert(*up == "hello");

####(19):cow_ptr

cow_ptr<string> cp1 = make_cow<string>("zouxiaohang");
auto cp2 = cp1, cp3 = cp1;
assert(cp1 == cp2 && cp2 == cp3);
assert(*cp1 == *cp2 && *cp2 == *cp3 && *cp3 == "zouxiaohang");

string s = *cp2;//read
assert(s == "zouxiaohang");
assert(cp1 == cp2 && cp2 == cp3);
assert(*cp1 == *cp2 && *cp2 == *cp3 && *cp3 == "zouxiaohang");

*cp2 = ("C++");//write
assert(*cp1 == *cp3 && *cp3 == "zouxiaohang");
assert(*cp2 == "C++");

####(19):union-find set

uf_set<10> uf;
uf.Union(0, 1);
uf.Union(2, 3);
uf.Union(3, 1);
assert(uf.Find(0) == uf.Find(2));