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>
namespace jj01
{
void test_array()
{
cout
<< "\ntest_array().......... \n";
array
<long,ASIZE
> c
;
clock_t timeStart
= clock();
for(long i
=0; i
< ASIZE
; ++i
) {
c
[i
] = 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();
::qsort(c
.data(), ASIZE
, sizeof(long), compareLongs
);
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容器
有几点需要注意的
1、
namespace的使用,不同
namespace之间的变量和函数互不影响
2、应该在每一个
namespace上面出引入标准库,这样可以告诉自己使用了那些标准库
3、在写测试程序的时候,可以把变量放置首位(不Tab),提醒自己
vector的增长是两倍两倍的增长(
2变
4,4变
8……)
上面的打印结果表明sort花费的时候过多
上诉代码
#include <vector>
#include <stdexcept>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <ctime>
#include <algorithm>
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
;
abort();
}
}
cout
<< "milli-seconds : " << (clock()-timeStart
) << endl
;
cout
<< "vector.max_size()= " << c
.max_size() << endl
;
cout
<< "vector.size()= " << c
.size() << endl
;
cout
<< "vector.front()= " << c
.front() << endl
;
cout
<< "vector.back()= " << c
.back() << endl
;
cout
<< "vector.data()= " << c
.data() << endl
;
cout
<< "vector.capacity()= " << c
.capacity() << endl
<< 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
<< endl
;
else
cout
<< "not found! " << endl
<< endl
;
}
{
timeStart
= clock();
sort(c
.begin(), c
.end());
cout
<< "sort(), milli-seconds : " << (clock()-timeStart
) << endl
;
timeStart
= clock();
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>
#include <cstdio>
#include <algorithm>
#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
;
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();
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>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <ctime>
#include <cstddef>
#include <memory>
#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
{
void test_list_with_special_allocator()
{
#ifdef __GNUC__
cout
<< "\ntest_list_with_special_allocator().......... \n";
list
<string
, allocator
<string
>> c1
;
list
<string
, __gnu_cxx
::malloc_allocator
<string
>> c2
;
list
<string
, __gnu_cxx
::new_allocator
<string
>> c3
;
list
<string
, __gnu_cxx
::__pool_alloc
<string
>> c4
;
list
<string
, __gnu_cxx
::__mt_alloc
<string
>> c5
;
list
<string
, __gnu_cxx
::bitmap_allocator
<string
>> c6
;
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
;
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);
__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);
#endif
}
}
/
不应该直接用分配器,要是用的话,还需要记住放出分配的内存有多少个,负担会很重
建议应该使用容器,要是小量的内存的话,可以用
new,
delete,malloc和de,而不应该用分配器
参考