Skip to content
/ TinySTL Public
forked from JiZhiSheng/TinySTL

TinySTL is a subset of STL(cut some containers and algorithms) and also a superset of STL(add some other containers and algorithms)

1 star 637 forks Branches Tags Activity
Star
Notifications You must be signed in to change notification settings

desayVincent/TinySTL

BranchesTags
 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

529 Commits
TinySTL
TinySTL
 
 
.gitattributes
.gitattributes
 
 
.gitignore
.gitignore
 
 
README.md
README.md
 
 
TinySTL.sln
TinySTL.sln
 
 

Repository files navigation

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));

About

TinySTL is a subset of STL(cut some containers and algorithms) and also a superset of STL(add some other containers and algorithms)

Resources

Readme
Activity

Stars

1 star

Watchers

0 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages

  • C++ 100.0%