1. 容器的结构与分类
-
Sequence Containers(顺序容器): 快速顺序访问元素
Array:C++11新特新，将语言的数组封装成Class，大小固定；
Vector:前端固定不变，连续内存空间，后端可以自动增长[分配器处理内存空间，增长速率为2^n]；
Deque:双向队列，连续内存空间，两端可进可出；
List:双向链表，内存空间不连续；
Forward-List:C++11新特新，单项链表，内存空间不连续，同等数据，内存空间小于List。 -
Associative Containers(关联容器):支持高效的关键字查找和访问
Set/Multiset:编译器一般用红黑树实现Set/Multiset，每一个结点为key；Set中结点key不可以重复，Multiset中结点key可以重复。
Map/Multimap:编译器一般用红黑树实现Map/Multimap，每一个结点中包含key-value，可以通过key来查找value；Map中结点key不可以重复，Multimap中结点key可以重复。 -
Unordered Containers(无序容器)：通过HashTable实现
容器的分类
注意：红色框代表C++11新特性
HashTable实现无序容器
2. 测试程序的辅助函数
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib> // RAND_MAX
using namespace std;
// 输入最大值, RAND_MAX
long get_a_target_long()
{
long target = 0;
cout << "target (0~" << RAND_MAX << "):";
cin >> target;
return target;
}
// 将数值转化为string
string get_a_target_string()
{
int target = 0;
char buf[10];
cout << "target (0~" << RAND_MAX << "):";
cin >> target;
snprintf(buf, 10, "%d", target);
return string(buf);
}
// 比较两个long是否相等
int compare_longs(const void* a, const void* b) // 没有理解为什么return int
{
return ( *(long*)a - *(long*)b );
}
// 比较两个字符串是否相等
int compare_strings(const void* a, const void* b)
{
if ( *(string*)a > *(string*)b )
{
return 1;
}
else if ( *(string*)a < *(string*)b )
{
return -1;
}
else
{
return 0;
}
}
3. 使用容器array
array结构图
#include <array>
#include <iostream>
#include <ctime>
#include <cstdlib>
#include "assist.h"
using namespace std;
const long ASIZE = 500000;
void test_array()
{
cout << "test_array()............" << endl;
array<long, ASIZE> c;
clock_t timeStart = clock();
for(long i=0; i<ASIZE; ++i)
{
c[i] = rand() % 100000;
}
cout << "milli-seconds: " << (clock() - timeStart) << endl; // 赋值500000数据所用时间
cout << "array.size() = " << c.size() << endl;
cout << "array.front() = " << c.front() << endl; //Returns a reference to the first element in the array container
cout << "array.back() = " << c.back() << endl; // Returns a reference to the last element in the array container
cout << "array.data() = " << c.data() << endl; // Returns a pointer to the first element in the array object
long target = get_a_target_long(); // 输入一个目标数据
timeStart = clock();
qsort(c.data(), ASIZE, sizeof(long), compare_longs); // 快排
long *pItem = (long*) bsearch( // 二分查找
&target,
c.data(),
ASIZE,
sizeof(long),
compare_longs
);
cout << "qsort()+bsearch(), milli-seconds: "
<< clock() - timeStart
<< endl;
if (pItem != NULL)
{
cout << "found, " << *pItem << endl;
}
else
{
cout << "not found" << endl;
}
}
int main()
{
test_array();
return 0;
}
4. 使用vector
vector结构图
#include <vector>
#include <stdexcept>
#include <string>
#include <cstdlib> // abort()
#include <cstdio> // snprintf()
#include <iostream>
#include <ctime>
#include <algorithm> // sort()
#include "assist.h"
using namespace std;
void test_vector(long& value)
{
cout << "test_vector......." << endl;
vector<string> c;
char buf[10];
clock_t timeStart = clock();
for(long i=0; i < value; ++i)
{
try{
snprintf(buf, 10, "%d", rand() % 10000);
c.push_back(string(buf));
}
catch(exception& p){
cout << "i=" << i << " " << p.what() << endl; // 内存不足，抛出异常
abort(); // 退出程序
}
}
cout << "milli-seconds: " << clock() - timeStart << 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; //容器的容量大小
// 查找给定元素
string target = get_a_target_string();
timeStart = clock();
vector<string>::iterator pItem = ::find(c.begin(), c.end(), target);
cout << "::find(), milli-second: " << clock() - timeStart << endl;
if ( pItem != c.end() )
{
cout << "found, " << *pItem << endl;
}
else
{
cout << "not found" << endl;
}
// 排序+二分查找
timeStart = clock();
sort(c.begin(), c.end()); // <algorithm>中的排序算法,时间复杂度为O(nlogn),应该为快排
string* pIt = (string*) bsearch(
&target,
c.data(),
c.size(),
sizeof(string),
compare_strings
);
cout << "sort() + bsearch(), milli-second: " << clock() - timeStart << endl;
if(pIt != NULL)
{
cout << "found, " << *pIt << endl;
}
else
{
cout << "not found" << endl;
}
}
int main()
{
long value = 1000000;
test_vector(value);
return 0;
}
5. 使用容器list
list结构图
#include <list>
#include <string>
#include <ctime>
#include <stdexcept>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include "assist.h"
using namespace std;
void test_list(long& value)
{
cout << "test_list()......" << endl;
list<string> c;
char buf[10];
clock_t timeStart = clock();
for(long i=0; i<value; ++i)
{
try{
snprintf(buf, 10, "%d", rand() % 10000);
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();
list<string>::iterator pItem = ::find(c.begin(), c.end(), target); // 调用std的find()
cout << "::find(), milli-seconds:" << clock() - timeStart << endl;
if(pItem != c.end())
{
cout << "found, " << *pItem << endl;
}
else
{
cout << "not found" << endl;
}
timeStart = clock();
c.sort(); // 调用list中的sort()
cout << "c.sort(), milli-seconds:" << clock() - timeStart << endl;
}
int main()
{
long value = 1000000;
test_list(value);
return 0;
}
6. 使用容器forward_list
forward_list结构图
test_forward_list.cpp
#include <forward_list>
#include <string>
#include <ctime>
#include <stdexcept>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include "assist.h"
using namespace std;
void test_forward_list(long& value)
{
cout << "test_forward_list()......" << endl;
forward_list<string> c;
char buf[10];
clock_t timeStart = clock();
for(long i=0; i<value; ++i)
{
try{
snprintf(buf, 10, "%d", rand() % 10000);
c.push_front(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();
forward_list<string>::iterator pItem = ::find(c.begin(), c.end(), target); // 调用std的find()
cout << "::find(), milli-seconds:" << clock() - timeStart << endl;
if(pItem != c.end())
{
cout << "found, " << *pItem << endl;
}
else
{
cout << "not found" << endl;
}
timeStart = clock();
c.sort(); // 调用list中的sort()
cout << "c.sort(), milli-seconds:" << clock() - timeStart << endl;
}
int main()
{
long value = 1000000;
test_forward_list(value);
return 0;
}
7. 使用容器deque
deque结构图
deque结构原理图
网友评论