TinySTL 是 STL 的子集(去掉了一些容器和算法),也是 STL 的超集(增加了一些其他容器和算法)
采用C++11实现一款简易的STL标准库，既是C++STL的一个子集（裁剪了一些容器和算法）又是一个超集（增加了一些容器和算法）
目的：练习数据结构与算法和C++ Template编程
编译环境：VS2013及以上版本
##开发计划：
##完成进度：
##TinySTL单元测试(原单元测试代码逐步)：
#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();
//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();
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();
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();
####(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();
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();
####(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();
####(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();
####(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();
####(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;
####(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");
####(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();
####(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();
####(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.mak
暂无开放 Issues，或尚未同步最近议题。