// ConsoleApplication2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#pragma warning(disable:4996)
#include<array>
#include<ctime>
#include<cstdlib>
#include<iostream>
#define ASIZE 100000
using std::cout;
using std::cin;
using std::string;
using std::endl;
using std::array;
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);// 将a转化为long类型的指针,并取其指向地址的值(即target的值)
}
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;
}
//1.对array的测试
/*
⚪ 创建大小为10万的array;
⚪ 用随机数对每个元素赋值;
⚪ 对整个array执行快排;
⚪ 对输入数据进行二分查找.
*/
namespace jj01
{
void test_array()
{
cout << "\ntest array .........." << endl;
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 << "c.size() = " << c.size() << endl;
cout << "c.front() = " << c.front() << endl;
cout << "c.back() = " << c.back() << endl;
cout << "c.data() = " << c.data() << endl;
long target = get_a_target_long();
timeStart = clock();
qsort(c.data(), ASIZE, sizeof(long), compareLongs);//数组首地址,数组有多少项,每项大小,比大小函数
long* flag = (long*)bsearch(&target, (c.data()), ASIZE, sizeof(long), compareLongs);
cout << "qsort()+bsearch(),milli-seconds:" << clock() - timeStart << endl;
if (flag != NULL)
cout << "found," << *flag << endl;
else
cout << "not found!!!" << endl;
}
}
#include<vector>
#include<cstdlib>//qsort,bsearch,abort
#include<cstdio>//snprintf
#include<iostream>
#include<string>
#include<ctime>
#include<algorithm>//算法,sort
#include<stdexcept>//抛出异常
using std::vector;
using std::exception;
using std::find;
//2.对vector的测试 (扩充的时候在别的地方找到一块2倍的内存把自己搬过去)
/*
⚪ 创建大小为10万的vector;
⚪ 用随机数对每个元素赋值;
⚪ 对整个vector执行快排;
⚪ 对输入数据进行二分查找.
*/
namespace jj02
{
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());
c.push_back(string(buf));//buf是一个char数组,需要转化为string类型,才能放入vector中
}//如果系统无法再分配空间了,就会引发异常
catch (exception& p)//捕获了异常,抓住了异常
{
cout << "i=" << i << " " << p.what() << endl;
abort();//退出程序
}
}
cout << "milli-seconds:" << clock() - timeStart << endl;
cout << "c.size() = " << c.size() << endl;
cout << "c.front() = " << c.front() << endl;
cout << "c.back() = " << c.back() << endl;
cout << "c.data() = " << c.data() << endl;
cout << "c.capicy() = " << c.capacity() << endl;
//vector两倍增长,放入1,变成2,放入2,不变,放入3,变成4,放入4,不变
//放入5,变成8,放入6,7,8,均不变,所以capacity是容器能存储的元素个数
//而size是容器目前存在的元素个数
string target = get_a_target_string();
{
timeStart = clock();
auto flag = ::find(c.begin(), c.end(), target);
cout << "::find().milli-seconds:" << clock() - timeStart << endl;
if (flag != c.end())
cout << "found," << *flag << endl;
else
cout << "not found" << endl;
}
{
timeStart = clock();
sort(c.begin(), c.end());
string* flag = (string*)bsearch(&target, c.data(), c.size(), sizeof(string), compareStrings);
cout << "qsort()+bsearch(),milli-seconds:" << clock() - timeStart << endl;
if (flag != NULL)
cout << "found," << *flag << endl;
else
cout << "not found!!!" << endl;
}
}
}
#include<list>
#include<cstdlib>//qsort,bsearch,abort
#include<cstdio>//snprintf
#include<iostream>
#include<string>
#include<ctime>
#include<algorithm>//算法,sort
#include<stdexcept>//抛出异常
using std::list;
//3.对list的测试
/*
⚪ 在STL标准库全局有一个sort函数,
⚪ 但这里调用的是list容器自身内部的sort函数。
⚪ 注意在STL容器中有些自身有sort函数,此时用自身的排序算法更快。
*/
namespace jj03
{
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());
c.push_back(string(buf));//buf是一个char数组,需要转化为string类型,才能放入vector中
}//如果系统无法再分配空间了,就会引发异常
catch (exception& p)//捕获了异常,抓住了异常
{
cout << "i=" << i << " " << p.what() << endl;
abort();//退出程序
}
}
cout << "milli-seconds:" << clock() - timeStart << endl;
cout << "c.size() = " << c.size() << endl;
cout << "c.front() = " << c.front() << endl;
cout << "c.back() = " << c.back() << endl;
cout << "c.max_size() = " << c.max_size() << endl;
string target = get_a_target_string();
timeStart = clock();
auto flag = ::find(c.begin(), c.end(), target);//标准库提供的全局 find 搜寻
cout << "::find().milli-seconds:" << clock() - timeStart << endl;
if (flag != c.end())
cout << "found," << *flag << endl;
else
cout << "not found" << endl;
timeStart = clock();
c.sort();//容器内部sort
cout << "c.sort(),milli-seconds:" << clock() - timeStart << endl;
}
}
#include <forward_list>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
using std::forward_list;
//4.对forward_list的测试
/*
⚪
⚪
⚪
*/
namespace jj04
{
void test_forward_list(long& value)
{
cout << "\ntest_forward_list().......... \n";
forward_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_front(string(buf));
}
catch (exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock() - timeStart) << endl;
cout << "forward_list.max_size()= " << c.max_size() << endl; //536870911
cout << "forward_list.front()= " << c.front() << 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();
}
}
#include<deque>
#include<cstdlib>//qsort,bsearch,abort
#include<cstdio>//snprintf
#include<iostream>
#include<string>
#include<ctime>
#include<algorithm>//算法,sort
#include<stdexcept>//抛出异常
using std::deque;
using std::sort;
//5.对 deque 的测试
/*
⚪ 每次扩充一个buffer,buffer由指针指向,即分段连续,在使用者看来是连续的;
⚪ 本身没有sort函数,所以只能使用全局的sort函数排序
*/
namespace jj05
{
void test_deque(long& value)//传引用
{
cout << endl << "test deque.........." << endl;
deque<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));//buf是一个char数组,需要转化为string类型,才能放入vector中
}//如果系统无法再分配空间了,就会引发异常
catch (exception& p)//捕获了异常,抓住了异常
{
cout << "i=" << i << " " << p.what() << endl;
abort();//退出程序
}
}
cout << "milli-seconds:" << clock() - timeStart << endl;
cout << "c.size() = " << c.size() << endl;
cout << "c.front() = " << c.front() << endl;
cout << "c.back() = " << c.back() << endl;
cout << "c.max_size() = " << c.max_size() << endl;
string target = get_a_target_string();
timeStart = clock();
auto flag = ::find(c.begin(), c.end(), target);
cout << "::find().milli-seconds:" << clock() - timeStart << endl;
if (flag != c.end())
cout << "found," << *flag << endl;
else
cout << "not found" << endl;
timeStart = clock();
::sort(c.begin(), c.end());
cout << "::sort(c.begin(), c.end()),milli-seconds:" << clock() - timeStart << endl;
}
}
//6.对slist,stack,queue的测试
/*
⚪ stack和queue严格来讲是一种容器适配器,其内部都是由deque构成的
⚪ stack和queue不会有一个函数来返回迭代器(泛化的指针),
因为有了迭代器可能你就会去改变stack或queue中的某个数据的值,
或者说插入一个数据,然而这与stack和queue自身的先进后出和先进先出的特点相违背。
所以以上两种适配器find是无法作用的,因为find函数返回的是迭代器类型
*/
int main()
{
long dequeSize = 100000;
using jj05::test_deque;
test_deque(dequeSize);
long forward_listSize = 100000;
using jj04::test_forward_list;
test_forward_list(forward_listSize);
long listSize = 100000;
using jj03::test_list;
test_list(listSize);
long vectorSize = 100000;
using jj02::test_vector;
test_vector(vectorSize);
using jj01::test_array;
test_array();
std::cout << "Hello World!\n";
}