加入CODE CHINA

· 不限速    · 不限空间    · 不限人数    · 私仓免费

免费加入
    README.md

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

    项目简介

    Forked from https://github.com/zouxiaohang/TinySTL TinySTL is a subset of STL(cut some containers and algorithms) and also a superset of STL(add some other containers and algorithms)

    发行版本

    当前项目没有发行版本

    贡献者 5

    Z zhanglanqing @zhanglanqing
    Z zouxiaohang @zouxiaohang
    J jiangtao @jiangtao
    P Pink Floyd @Pink Floyd

    开发语言

    • C++ 100.0 %