程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++ Primer 學習筆記_46_STL剖析(一):泛型程序設計、什麼是STL、STL六大組件及其關系

C++ Primer 學習筆記_46_STL剖析(一):泛型程序設計、什麼是STL、STL六大組件及其關系

編輯:C++入門知識

C++ Primer 學習筆記_46_STL剖析(一):泛型程序設計、什麼是STL、STL六大組件及其關系


一、泛型程序設計

1、泛型編程(generic programming):相同的邏輯和算法,對不同類型的數據進行處理
2、將程序寫得盡可能通用
3、將算法從數據結構中抽象出來,成為通用的
4、C++的模板為泛型程序設計奠定了關鍵的基礎

二、什麼是STL

1、STL(Standard Template Library),即標准模板庫,是一個高效的C++程序庫。
2、包含了諸多在計算機科學領域裡常用的基本數據結構和基本算法。為廣大C++程序員們提供了一個可擴展的應用框架,高度體現了軟件的可復用性

3、從邏輯層次來看,在STL中體現了泛型化程序設計的思想(generic programming)

(1)在這種思想裡,大部分基本算法被抽象,被泛化,獨立於與之對應的數據結構,用於以相同或相近的方式處理各種不同情形。

4、從實現層次看,整個STL是以一種類型參數化(type parameterized)的方式實現的

(1)基於模板(template)

(2)模板,泛型程序設計思想,STL的關系

模板為泛型程序設計奠定了基礎

STL是一套C++標准模板庫,體現了泛型程序設計思想,換句話說,STL是泛型程序設計思想比較成功的一套產品

三、STL六大組件及其關系

1、STL六大組件

————Container(容器) 各種基本數據結構

————Adapter(適配器) 可改變containers、Iterators或Function object接口的一種組件(之前通過deque是實現了新的容器Stack,Stack稱為容器適配器)

————Algorithm(算法) 各種基本算法如sort、search…等

————Iterator(迭代器) 連接containers和algorithms,迭代器是容器與算法的橋梁

————Function object(函數對象)

————Allocator(分配器)

2、容器算法迭代器關系

容器是數據結構,算法是邏輯,迭代器是遍歷接口

\

3、容器

(1)容器類是容納、包含一組元素或元素集合的對象


(2)七種基本容器:

————向量(vector)、雙端隊列(deque)、列表(list)、集合(set)、多重集合(multiset)、映射(map)和多重映射(multimap)

(3)標准容器的成員絕大部分都具有共同的名稱

\

(4)序列式容器

————序列式容器Sequence containers,其中每個元素均有固定位置——取決於插入時機和地點,和元素值無關。(vector、deque、list)

(5)關聯式容器

————關聯式容器Associative containers,元素位置取決於特定的排序准則以及元素值,和插入次序無關。(set、multiset、map、multimap)

(6)如何選擇序列式容器

【1】、需要頻繁在序列中間位置上進行插入和/或刪除操作且不需要過多地在序列內部進行長距離跳轉,應該選擇list。不支持下標操作

【2】、vector頭部與中間插入刪除效率較低,在尾部插入與刪除效率高。支持下標操作

【3】、deque是在頭部與尾部插入與刪除效率較高。支持下標操作

4、迭代器

(1)迭代器Iterators,用來在一個對象群集(collection of objects)的元素上進行遍歷。這個對象群集或許是個容器,或許是容器的一部分。迭代器的主要好處是,為所有容器提供了一組很小的公共接口。迭代器以++進行累進,以*進行提領,因而它類似於指針,我們可以把它視為一種smart pointer
(2)比如++操作可以遍歷至群集內的下一個元素。至於如何做到,取決於容器內部的數據組織形式。
(3)每種容器都提供了自己的迭代器,而這些迭代器能夠了解容器內部的數據結構。

5、算法

算法Algorithms,用來處理群集內的元素。它們可以出於不同的目的而搜尋、排序、修改、使用那些元素。通過迭代器的協助,我們可以只需編寫一次算法,就可以將它應用於任意容器,這是因為所有的容器迭代器都提供一致的接口。

6、適配器

(1)、適配器是一種接口類(構造出新的類)

【1】為已有的類提供新的接口stack、queue

【2】目的是簡化、約束、使之安全、隱藏或者改變被修改類提供的服務集合

(2)、三種類型的適配器:

【1】容器適配器:用來擴展7種基本容器,它們和順序容器相結合構成棧、隊列和優先隊列容器

【2】迭代器適配器(反向迭代器、插入迭代器、IO流迭代器)

【3】函數適配器(函數對象適配器、成員函數適配器、普通函數適配器)

7、函數對象

(1)、函數對象(function object)也稱為仿函數(functor)
(2)、一個行為類似函數的對象,它可以沒有參數,也可以帶有若干參數。
(3)、任何重載了調用運算符operator()的類的對象都滿足函數對象的特征
(4)、函數對象可以把它稱之為smart function。
(5)、STL中也定義了一些標准的函數對象,如果以功能劃分,可以分為算術運算、關系運算、邏輯運算三大類。為了調用這些標准函數對象,需要包含頭文件

8、分配器

負責空間配置與管理。從實現的角度來看,配置器是一個實現了動態空間配置、空間管理、空間釋放的class template。

隱藏在這些容器後的內存管理工作是通過STL提供的一個默認的allocator實現的。當然,用戶也可以定制自己的allocator,只要實現allocator模板所定義的接口方法即可,然後通過將自定義的allocator作為模板參數傳遞給STL容器,創建一個使用自定義allocator的STL容器對象,如:
stl::vector array;
大多數情況下,STL默認的allocator就已經足夠了。這個allocator是一個由兩級分配器構成的內存管理器,當申請的內存大小大於128byte時,就啟動第一級分配器通過malloc直接向系統的堆空間分配,如果申請的內存大小小於128byte時,就啟動第二級分配器,從一個預先分配好的內存池中取一塊內存交付給用戶,這個內存池由16個不同大小(8的倍數,8~128byte)的空閒列表組成,allocator會根據申請內存的大小(將這個大小round up成8的倍數)從對應的空閒塊列表取表頭塊給用戶。

這種做法有兩個優點:
(1)小對象的快速分配。小對象是從內存池分配的,這個內存池是系統調用一次malloc分配一塊足夠大的區域給程序備用,當內存池耗盡時再向系統申請一塊新的區域,整個過程類似於批發和零售,起先是由allocator向總經商批發一定量的貨物,然後零售給用戶,與每次都總經商要一個貨物再零售給用戶的過程相比,顯然是快捷了。當然,這裡的一個問題時,內存池會帶來一些內存的浪費,比如當只需分配一個小對象時,為了這個小對象可能要申請一大塊的內存池,但這個浪費還是值得的,況且這種情況在實際應用中也並不多見。
(2)避免了內存碎片的生成。程序中的小對象的分配極易造成內存碎片,給操作系統的內存管理帶來了很大壓力,系統中碎片的增多不但會影響內存分配的速度,而且會極大地降低內存的利用率。以內存池組織小對象的內存,從系統的角度看,只是一大塊內存池,看不到小對象內存的分配和釋放。

參考:

C++ primer 第四版
Effective C++ 3rd
C++編程規范

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved