C++ STL 体系结构与内核分析(一)

    科技2022-07-17  101

    C++标准库

    泛型编程GP:就是使用模板为主要工具来编写程序 C++标准库>STL(六大部件)

    重要网页1

    重要网页2

    重要网页3

    六大部件

    数据和其操作是分开的(这里是泛型编程和面向对象的一个区别)

    例子

    注意上诉的分配器一般情况下不用写,系统有默认的

    注意前闭后开

    候大佬建议少用auto

    ::是全局运算符,可以不加

    容器分类与测试

    容器分类上诉给的是三种:序列容器,关联容器和不定序容器 红色框框为C++11所增加的东西 注意上图中的容器表示,很形象也很清楚 各家编译器所带的标准库基本都是用红黑树来做set和map,但是C++标准库中并没有明确声明 注意multiset/multimap的key是可重复的

    Sequence Containers

    以下测试程序之辅助函数

    array容器

    using std::cin; using std::cout; using std::string; long get_a_target_long() { long target=0; cout << "target (0~" << RAND_MAX << "): "; cin >> target; return target; } string get_a_target_string() { long target=0; char buf[10]; cout << "target (0~" << RAND_MAX << "): "; cin >> target; snprintf(buf, 10, "%d", target); return string(buf); } int compareLongs(const void* a, const void* b) { return ( *(long*)a - *(long*)b ); } int compareStrings(const void* a, const void* b) { if ( *(string*)a > *(string*)b ) return 1; else if ( *(string*)a < *(string*)b ) return -1; else return 0; }

    #include <array> #include <iostream> #include <ctime> #include <cstdlib> //qsort, bsearch, NULL namespace jj01 { void test_array() { cout << "\ntest_array().......... \n"; array<long,ASIZE> c; //ASIZE为array的大小 clock_t timeStart = clock(); for(long i=0; i< ASIZE; ++i) { c[i] = rand(); //rand()为生成随机数的函数 } cout << "milli-seconds : " << (clock()-timeStart) << endl; // cout << "array.size()= " << c.size() << endl; cout << "array.front()= " << c.front() << endl; cout << "array.back()= " << c.back() << endl; cout << "array.data()= " << c.data() << endl;//传回这个数组在内存中的起始地址 long target = get_a_target_long(); timeStart = clock();//到这里的时候的毫秒数ms ::qsort(c.data(), ASIZE, sizeof(long), compareLongs);//qsort快排,bsearch二分查找 long* pItem = (long*)::bsearch(&target, (c.data()), ASIZE, sizeof(long), compareLongs); cout << "qsort()+bsearch(), milli-seconds : " << (clock()-timeStart) << endl; // if (pItem != NULL) cout << "found, " << *pItem << endl; else cout << "not found! " << endl; } }

    vector容器

    有几点需要注意的 1namespace的使用,不同namespace之间的变量和函数互不影响 2、应该在每一个namespace上面出引入标准库,这样可以告诉自己使用了那些标准库 3、在写测试程序的时候,可以把变量放置首位(不Tab),提醒自己

    vector的增长是两倍两倍的增长(24,48……)

    上面的打印结果表明sort花费的时候过多

    上诉代码

    #include <vector> #include <stdexcept> #include <string> #include <cstdlib> //abort() #include <cstdio> //snprintf() #include <iostream> #include <ctime> #include <algorithm> //sort() namespace jj02 { void test_vector(long& value) { cout << "\ntest_vector().......... \n"; vector<string> c;//一个字符串的大小只是指针的大小 char buf[10]; clock_t timeStart = clock(); for(long i=0; i< value; ++i) { try { snprintf(buf, 10, "%d", rand()); c.push_back(string(buf)); //从后面放元素 } catch(exception& p) { cout << "i=" << i << " " << p.what() << endl; //曾經最高 i=58389486 then std::bad_alloc abort(); } } cout << "milli-seconds : " << (clock()-timeStart) << endl; cout << "vector.max_size()= " << c.max_size() << endl; //1073747823 cout << "vector.size()= " << c.size() << endl;//元素个数 cout << "vector.front()= " << c.front() << endl; cout << "vector.back()= " << c.back() << endl; cout << "vector.data()= " << c.data() << endl;//整个vector的起始地址 cout << "vector.capacity()= " << c.capacity() << endl << endl; //注意capacity一定比size大,因为vector是两倍增长的,符合逻辑 string target = get_a_target_string(); { timeStart = clock(); auto pItem = ::find(c.begin(), c.end(), target);//find前面的::表示全局(函数) cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl; if (pItem != c.end()) cout << "found, " << *pItem << endl << endl; else cout << "not found! " << endl << endl; } { timeStart = clock(); sort(c.begin(), c.end()); cout << "sort(), milli-seconds : " << (clock()-timeStart) << endl; timeStart = clock();//bsearch是C标准库提供的 string* pItem = (string*)::bsearch(&target, (c.data()), c.size(), sizeof(string), compareStrings); cout << "bsearch(), milli-seconds : " << (clock()-timeStart) << endl; if (pItem != NULL) cout << "found, " << *pItem << endl << endl; else cout << "not found! " << endl << endl; } c.clear(); test_moveable(vector<MyString>(),vector<MyStrNoMove>(), value); } }

    list容器

    #include <list> #include <stdexcept> #include <string> #include <cstdlib> //abort() #include <cstdio> //snprintf() #include <algorithm> //find() #include <iostream> #include <ctime> namespace jj03 { void test_list(long& value) { cout << "\ntest_list().......... \n"; list<string> c; char buf[10]; clock_t timeStart = clock(); for(long i=0; i< value; ++i) { try { snprintf(buf, 10, "%d", rand()); c.push_back(string(buf)); } catch(exception& p) { cout << "i=" << i << " " << p.what() << endl; abort(); } } cout << "milli-seconds : " << (clock()-timeStart) << endl; cout << "list.size()= " << c.size() << endl; cout << "list.max_size()= " << c.max_size() << endl; //357913941 cout << "list.front()= " << c.front() << endl; cout << "list.back()= " << c.back() << endl; string target = get_a_target_string(); timeStart = clock(); auto pItem = find(c.begin(), c.end(), target); cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl; if (pItem != c.end()) cout << "found, " << *pItem << endl; else cout << "not found! " << endl; timeStart = clock(); c.sort();//这里用的容器里面的sort,不是标准库中的sort cout << "c.sort(), milli-seconds : " << (clock()-timeStart) << endl; c.clear(); test_moveable(list<MyString>(),list<MyStrNoMove>(), value); } } 注意,标准库有sort,而某些容器自己也有sort,这种情况优先使用容器自己提供的sort

    forward_list容器

    注意224行的push_front() 注意上面的forward_list是C++11标准库的,而下面的slist是之前就有的,其实差不多

    slist容器

    注意头文件这里有一个ext扩充

    deque容器

    deque是分段连续,但是让使用者感觉它是整个连续的 deque每次扩充都是一个buffer,buffer为512个字节? array是不能扩充的 注意一个容器占用内存后是不可以扩充的,像vector容器它扩充是在别的地方找到一处内存, 并把原来的数据搬过去(找到的那处内存必须是两倍大小) 两倍两倍的扩充,到后面就会很大,很大就意味着内存会被浪费(比如vector的容量要大于size,浪费) list每次扩充都是一个节点,节点占用的内存很小,很小就意味着空间利用率高,效率高,但是找起来慢

    上诉容器中的查找给人的感觉是,查找都需要很多的时间, 而下面要讲的**关联式容器**基本都是几毫秒,查找非常快

    stack和queue容器

    注意stack和queue这两种容器的源代码,其实它内部就是拥有一个deque(因为这个功能最强大) 从技术上讲,stack和queue这两种容器是容器适配器(六大部件之一) 而且这两个容器是不提供iterator的,不能随机访问 注意上诉容器的声明和使用方式

    Associative Containers

    可以把它看成小型的关联数据,查找是非常快 下面这俩容器都是用红黑树做支撑

    multiset容器

    这里的安插元素用的是insert,没有明确的插入位置,但是在插入的时候已经在排序了 上诉容器本身就有一个find函数,肯定是容器本身的函数快 注意上面的size=100万,说明重复的元素也算进去了,但是如果是set的话,要<100

    multimap容器

    multimap,所以key是可以重复的 注意370行的声明 379行的插入(pair一对,标准库里面的东西)

    Unordered Containers

    下面的是用hashtable做支撑

    unordered_multiset

    bucket_count()是篮子的个数 篮子比元素多,合理,见散列表 (如果元素的个数大于等于篮子,那个容器就需要扩充,大约两倍) load_factor()载重因子=元素个数/篮子个数

    unordered_multimap

    下面的四个容器的key是独一无二的

    size=32768远远小于100,说明key不重复

    注意这里的size=100万,key不会重复

    注意还有下面几个容器

    分配器之测试

    上诉的分配器都是在ext下面,属于扩充性的分配器 _pool_alloc:内存池 #include <list> #include <stdexcept> #include <string> #include <cstdlib> //abort() #include <cstdio> //snprintf() #include <algorithm> //find() #include <iostream> #include <ctime> #include <cstddef> #include <memory> //內含 std::allocator //欲使用 std::allocator 以外的 allocator, 得自行 #include <ext\...> #ifdef __GNUC__ #include <ext\array_allocator.h> #include <ext\mt_allocator.h> #include <ext\debug_allocator.h> #include <ext\pool_allocator.h> #include <ext\bitmap_allocator.h> #include <ext\malloc_allocator.h> #include <ext\new_allocator.h> #endif namespace jj20 { //pass A object to function template impl(), //而 A 本身是個 class template, 帶有 type parameter T, //那麼有無可能在 impl() 中抓出 T, 創建一個 list<T, A<T>> object? //以下先暫時迴避上述疑問. void test_list_with_special_allocator() { #ifdef __GNUC__ cout << "\ntest_list_with_special_allocator().......... \n"; //不能在 switch case 中宣告,只好下面這樣. //1000000次 list<string, allocator<string>> c1; //3140 list<string, __gnu_cxx::malloc_allocator<string>> c2; //3110 list<string, __gnu_cxx::new_allocator<string>> c3; //3156 list<string, __gnu_cxx::__pool_alloc<string>> c4; //4922 list<string, __gnu_cxx::__mt_alloc<string>> c5; //3297 list<string, __gnu_cxx::bitmap_allocator<string>> c6; //4781 int choice; long value; cout << "select: " << " (1) std::allocator " << " (2) malloc_allocator " << " (3) new_allocator " << " (4) __pool_alloc " << " (5) __mt_alloc " << " (6) bitmap_allocator "; cin >> choice; if ( choice != 0 ) { cout << "how many elements: "; cin >> value; } char buf[10]; clock_t timeStart = clock(); for(long i=0; i< value; ++i) { try { snprintf(buf, 10, "%d", i); switch (choice) { case 1 : c1.push_back(string(buf)); break; case 2 : c2.push_back(string(buf)); break; case 3 : c3.push_back(string(buf)); break; case 4 : c4.push_back(string(buf)); break; case 5 : c5.push_back(string(buf)); break; case 6 : c6.push_back(string(buf)); break; default: break; } } catch(exception& p) { cout << "i=" << i << " " << p.what() << endl; abort(); } } cout << "a lot of push_back(), milli-seconds : " << (clock()-timeStart) << endl; //test all allocators' allocate() & deallocate(); int* p; allocator<int> alloc1; p = alloc1.allocate(1); alloc1.deallocate(p,1); __gnu_cxx::malloc_allocator<int> alloc2; p = alloc2.allocate(1); alloc2.deallocate(p,1); __gnu_cxx::new_allocator<int> alloc3; p = alloc3.allocate(1); alloc3.deallocate(p,1); __gnu_cxx::__pool_alloc<int> alloc4; p = alloc4.allocate(2); alloc4.deallocate(p,2); //我刻意令參數為 2, 但這有何意義!! 一次要 2 個 ints? __gnu_cxx::__mt_alloc<int> alloc5; p = alloc5.allocate(1); alloc5.deallocate(p,1); __gnu_cxx::bitmap_allocator<int> alloc6; p = alloc6.allocate(3); alloc6.deallocate(p,3); //我刻意令參數為 3, 但這有何意義!! 一次要 3 個 ints? #endif } } / 不应该直接用分配器,要是用的话,还需要记住放出分配的内存有多少个,负担会很重 建议应该使用容器,要是小量的内存的话,可以用newdelete,malloc和de,而不应该用分配器

    参考

    Processed: 0.010, SQL: 8