我近期查看boost库时发现如下写法，不是很了解其原理
duration模板类里面有个静态断言使用到了is_duration
BOOST_CHRONO_STATIC_ASSERT(!boost::chrono::detail::is_duration<Rep>::value,
BOOST_CHRONO_A_DURATION_REPRESENTATION_CAN_NOT_BE_A_DURATION, ());
我去找了is_duration的定义：
template <class Rep, class Period>
struct is_duration<duration<Rep, Period> >
: boost::true_type {};
他这个struct后面跟了个<>的写法没见过，我自己试了写一下类似的发现编译器报错，请问这是什么写法
这是模板类。可以带自定义类进来。
我有一份快排的代码就是这么写的。
// Code from Mark Allen Weiss textbook
// Modified by: YOUR NAME
#ifndef SORT_H
#define SORT_H
/**
* Several sorting routines.
* Arrays are rearranged with smallest item first.
*/
#include <vector>
#include <functional>
using namespace std;
/**
* Simple insertion sort.
*/
template <typename Comparable, typename Comparator>
void insertionSort(vector<Comparable> & a, Comparator less_than)
{
for (int p = 1; p < a.size(); ++p)
{
Comparable tmp = std::move(a[p]);
int j;
for (j = p; j > 0 && less_than(tmp,a[j - 1]); --j)
a[j] = std::move(a[j - 1]);
a[j] = std::move(tmp);
}
}
/**
* Internal insertion sort routine for subarrays
* that is used by quicksort.
* a is an array of Comparable items.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template <typename Comparable, typename Comparator>
void insertionSort(vector<Comparable> & a, int left, int right, Comparator less_than)
{
for (int p = left + 1; p <= right; ++p)
{
Comparable tmp = std::move(a[p]);
int j;
for (j = p; j > left && less_than(tmp, a[j - 1]); --j)
a[j] = std::move(a[j - 1]);
a[j] = std::move(tmp);
}
}
/**
* Shellsort, using Shell's (poor) increments.
*/
template <typename Comparable>
void shellsort(vector<Comparable> & a)
{
for (int gap = a.size() / 2; gap > 0; gap /= 2)
for (int i = gap; i < a.size(); ++i)
{
Comparable tmp = std::move(a[i]);
int j = i;
for (; j >= gap && tmp < a[j - gap]; j -= gap)
a[j] = std::move(a[j - gap]);
a[j] = std::move(tmp);
}
}
/**
* Standard heapsort.
*/
template <typename Comparable, typename Comparator>
void heapsort(vector<Comparable> & a, Comparator less_than)
{
for (int i = a.size() / 2 - 1; i >= 0; --i) /* buildHeap */
percDown(a, i, a.size(), less_than);
for (int j = a.size() - 1; j > 0; --j)
{
std::swap(a[0], a[j]); /* deleteMax */
percDown(a, 0, j, less_than);
}
}
/**
* Internal method for heapsort.
* i is the index of an item in the heap.
* Returns the index of the left child.
*/
inline int leftChild(int i)
{
return 2 * i + 1;
}
/**
* Internal method for heapsort that is used in
* deleteMax and buildHeap.
* i is the position from which to percolate down.
* n is the logical size of the binary heap.
*/
template <typename Comparable, typename Comparator>
void percDown(vector<Comparable> & a, int i, int n, Comparator less_than)
{
int child;
Comparable tmp;
for (tmp = std::move(a[i]); leftChild(i) < n; i = child)
{
child = leftChild(i);
if (child != n - 1 && less_than(a[child] , a[child + 1]))
++child;
if (less_than(tmp , a[child]))
a[i] = std::move(a[child]);
else
break;
}
a[i] = std::move(tmp);
}
/**
* Internal method that makes recursive calls.
* a is an array of Comparable items.
* tmpArray is an array to place the merged result.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template <typename Comparable, typename Comparator>
void mergeSort(vector<Comparable> & a,
vector<Comparable> & tmpArray, int left, int right, Comparator less_than)
{
if (left < right)
{
int center = (left + right) / 2;
mergeSort(a, tmpArray, left, center, less_than);
mergeSort(a, tmpArray, center + 1, right, less_than);
merge(a, tmpArray, left, center + 1, right, less_than);
}
}
/**
* Mergesort algorithm (driver).
*/
template <typename Comparable, typename Comparator>
void mergeSort(vector<Comparable> & a, Comparator less_than)
{
vector<Comparable> tmpArray(a.size());
mergeSort(a, tmpArray, 0, a.size() - 1, less_than);
}
/**
* Internal method that merges two sorted halves of a subarray.
* a is an array of Comparable items.
* tmpArray is an array to place the merged result.
* leftPos is the left-most index of the subarray.
* rightPos is the index of the start of the second half.
* rightEnd is the right-most index of the subarray.
*/
template <typename Comparable, typename Comparator>
void merge(vector<Comparable> & a, vector<Comparable> & tmpArray,
int leftPos, int rightPos, int rightEnd, Comparator less_than)
{
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
// Main loop
while (leftPos <= leftEnd && rightPos <= rightEnd)
/////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////
if (less_than(a[leftPos], a[rightPos]))
tmpArray[tmpPos++] = std::move(a[leftPos++]);
else
tmpArray[tmpPos++] = std::move(a[rightPos++]);
while (leftPos <= leftEnd) // Copy rest of first half
tmpArray[tmpPos++] = std::move(a[leftPos++]);
while (rightPos <= rightEnd) // Copy rest of right half
tmpArray[tmpPos++] = std::move(a[rightPos++]);
// Copy tmpArray back
for (int i = 0; i < numElements; ++i, --rightEnd)
a[rightEnd] = std::move(tmpArray[rightEnd]);
}
/**
* Return median of left, center, and right.
* Order these and hide the pivot.
*/
template <typename Comparable, typename Comparator>
const Comparable & median3(vector<Comparable> & a, int left, int right, Comparator less_than)
{
int center = (left + right) / 2;
if (less_than(a[center], a[left]))
std::swap(a[left], a[center]);
if (less_than(a[right], a[left]))
std::swap(a[left], a[right]);
if (less_than(a[right], a[center]))
std::swap(a[center], a[right]);
// Place pivot at position right - 1
std::swap(a[center], a[right - 1]);
return a[right - 1];
}
//template <typename Comparable, typename Comparator>
// partition the array using last element as pivot
//int partition(vector<Comparable> & a, int left, int right, Comparator less_than)
//{
// int pivot = a[right]; // pivot
// int i = (left - 1);
//
// for (int j = left; j <= right - 1; j++)
// {
// //if current element is smaller than pivot, increment the low element
// //swap elements at i and j
// if (less_than(a[j], pivot))
// {
// i++; // increment index of smaller element
// std::swap(a[i], a[j]);
// }
// }
// std::swap(a[i + 1], a[right]);
// return (i + 1);
//}
template <typename Comparable, typename Comparator>
// partition the array using first element as pivot
int partition(vector<Comparable> & a, int left, int right, Comparator less_than)
{
int pivot = a[left]; // pivot
int i = left + 1;
for (int j = left + 1; j <= right ; j++)
{
//if current element is smaller than pivot, increment the low element
//swap elements at i and j
if (less_than(a[j], pivot))
{
i++; // increment index of smaller element
std::swap(a[i], a[j]);
}
}
std::swap(a[i - 1], a[left]);
return (i - 1);
}
template <typename Comparable, typename Comparator>
//quicksort algorithm
void quickSort2(vector<Comparable> & a, int left, int right, Comparator less_than)
{
if (left < right)
{
//partition the array
int pivot = partition(a, left, right, less_than);
//sort the sub arrays independently
quickSort2(a, left, pivot - 1, less_than);
quickSort2(a, pivot + 1, right, less_than);
}
}
template <typename Comparable, typename Comparator>
void quickSort2(vector<Comparable> & a, Comparator less_than)
{
quickSort2(a, 0, a.size() - 1, less_than);
}
template <typename Comparable, typename Comparator>
void quicksort3(vector<Comparable> & a, Comparator less_than)
{
quicksort3(a, 0, a.size() - 1, less_than);
}
template <typename Comparable, typename Comparator>
void quicksort3(vector<Comparable> & a, int left, int right, Comparator less_than)
{
if (left + 10 <= right)
{
const Comparable & pivot = median3(a, left, right, less_than);
// Begin partitioning
int i = left, j = right - 1;
for (;;)
{
while (less_than(a[++i], pivot)) {}
while (less_than(pivot, a[--j])) {}
if (i < j)
std::swap(a[i], a[j]);
else
break;
}
std::swap(a[i], a[right - 1]); // Restore pivot
quicksort3(a, left, i - 1, less_than); // Sort small elements
quicksort3(a, i + 1, right, less_than); // Sort large elements
}
else // Do an insertion sort on the subarray
insertionSort(a, left, right, less_than);
}
/**
* Internal quicksort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* a is an array of Comparable items.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template <typename Comparable, typename Comparator>
void quicksort(vector<Comparable> & a, int left, int right, Comparator less_than)
{
if (left + 10 <= right)
{
const Comparable & pivot = median3(a, left, right, less_than);
// Begin partitioning
int i = left, j = right - 1;
for (;;)
{
while (less_than(a[++i], pivot)) {}
while (less_than(pivot, a[--j])) {}
if (i < j)
std::swap(a[i], a[j]);
else
break;
}
std::swap(a[i], a[right - 1]); // Restore pivot
quicksort(a, left, i - 1, less_than); // Sort small elements
quicksort(a, i + 1, right, less_than); // Sort large elements
}
else // Do an insertion sort on the subarray
insertionSort(a, left, right,less_than);
}
/**
* Quicksort algorithm (driver).
*/
template <typename Comparable, typename Comparator>
void quicksort2(vector<Comparable> & a, Comparator less_than)
{
quicksort2(a, 0, a.size() - 1, less_than);
}
/**
* Quicksort algorithm (driver).
*/
template <typename Comparable, typename Comparator>
void quicksort(vector<Comparable> & a, Comparator less_than)
{
quicksort(a, 0, a.size() - 1, less_than);
}
/**
* Internal selection method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* Places the kth smallest item in a[k-1].
* a is an array of Comparable items.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
* k is the desired rank (1 is minimum) in the entire array.
*/
template <typename Comparable>
void quickSelect(vector<Comparable> & a, int left, int right, int k)
{
if (left + 10 <= right)
{
const Comparable & pivot = median3(a, left, right);
// Begin partitioning
int i = left, j = right - 1;
for (;;)
{
while (a[++i] < pivot) {}
while (pivot < a[--j]) {}
if (i < j)
std::swap(a[i], a[j]);
else
break;
}
std::swap(a[i], a[right - 1]); // Restore pivot
// Recurse; only this part changes
if (k <= i)
quickSelect(a, left, i - 1, k);
else if (k > i + 1)
quickSelect(a, i + 1, right, k);
}
else // Do an insertion sort on the subarray
insertionSort(a, left, right);
}
/**
* Quick selection algorithm.
* Places the kth smallest item in a[k-1].
* a is an array of Comparable items.
* k is the desired rank (1 is minimum) in the entire array.
*/
template <typename Comparable>
void quickSelect(vector<Comparable> & a, int k)
{
quickSelect(a, 0, a.size() - 1, k);
}
template <typename Comparable>
void SORT(vector<Comparable> & items)
{
if (items.size() > 1)
{
vector<Comparable> smaller;
vector<Comparable> same;
vector<Comparable> larger;
auto chosenItem = items[items.size() / 2];
for (auto & i : items)
{
if (i < chosenItem)
smaller.push_back(std::move(i));
else if (chosenItem < i)
larger.push_back(std::move(i));
else
same.push_back(std::move(i));
}
SORT(smaller); // Recursive call!
SORT(larger); // Recursive call!
std::move(begin(smaller), end(smaller), begin(items));
std::move(begin(same), end(same), begin(items) + smaller.size());
std::move(begin(larger), end(larger), end(items) - larger.size());
/*
items.clear( );
items.insert( end( items ), begin( smaller ), end( smaller ) );
items.insert( end( items ), begin( same ), end( same ) );
items.insert( end( items ), begin( larger ), end( larger ) );
*/
}
}
/*
* This is the more public version of insertion sort.
* It requires a pair of iterators and a comparison
* function object.
*/
template <typename RandomIterator, typename Comparator>
void insertionSort(const RandomIterator & begin,
const RandomIterator & end,
Comparator lessThan)
{
if (begin == end)
return;
RandomIterator j;
for (RandomIterator p = begin + 1; p != end; ++p)
{
auto tmp = std::move(*p);
for (j = p; j != begin && lessThan(tmp, *(j - 1)); --j)
*j = std::move(*(j - 1));
*j = std::move(tmp);
}
}
/*
* The two-parameter version calls the three parameter version, using C++11 decltype
*/
template <typename RandomIterator>
void insertionSort(const RandomIterator & begin,
const RandomIterator & end)
{
insertionSort(begin, end, less<decltype(*begin)>{ });
}
#endif
// Homework 5
// Testing Sorting Algorithms
// YOUR NAME
#include "Sort.h"
#include <chrono>
#include <iostream>
#include <fstream>
#include <functional>
#include <string>
#include <vector>
#include <algorithm>
//////////////////////
// the limits of type
#include <limits>
namespace tools {
bool less(int left, int right){
return left <= right;
}
bool greater(int left, int right){
return left >= right;
}
}
namespace judge{
bool less(const vector<int> &input){
int judge = numeric_limits<int>::min();
for (size_t i = 0; i < input.size(); i++){
if (judge <= input[i]){
judge = input[i];
continue;
}
else{
return false;
}
}
return true;
}
bool greater(const vector<int> &input){
int judge = numeric_limits<int>::max();
for (size_t i = 0; i < input.size(); i++){
if (judge >= input[i]){
judge = input[i];
continue;
}
else{
return false;
}
}
return true;
}
}
using namespace std;
// Test function that shows how you can time a piece of code.
// Just times a simple loop.
void TestingTiming() {
cout << "Testing Timing" << endl;
const auto begin = chrono::high_resolution_clock::now();
// Time this piece of code.
int sum = 0;
for (int i = 1; i < 10000; ++i) sum++;
// End of piece of code to time.
const auto end = chrono::high_resolution_clock::now();
cout << chrono::duration_cast<chrono::nanoseconds>(end - begin).count() << "ns" << endl;
cout << chrono::duration_cast<chrono::milliseconds>(end - begin).count() << "ms" << endl;
}
// Generates and returns random vector of size @size_of_vector.
vector<int> GenerateRandomVector(size_t size_of_vector) {
// Use rand() to generate random integer
// Add code
srand(time(0));
vector<int> res;
for (size_t i = 0; i < size_of_vector; i++){
res.push_back(rand() % numeric_limits < int > ::max() + 1);
}
return res;
}
// Generate and returns sorted vector of size @size_of_vector
// If smaller_to_larger is true, returns vector sorted from small to large
// Otherwise returns vector sorted from large to small
vector<int> GenerateSortedVector(size_t size_of_vector, bool smaller_to_larger) {
// Add code
vector<int> res;
if (smaller_to_larger){
for (size_t i = 0; i < size_of_vector; i++){
res.push_back(i);
}
}
else{
for (size_t i = size_of_vector; i > 0; i--){
res.push_back(i);
}
}
return res;
}
// Verifies that a vector is sorted given a comparator
template <typename Comparable, typename Comparator>
bool VerifyOrder(const vector<Comparable> &input, Comparator less_than) {
// Add code
// to judge if the input is order by asc or desc
bool flag = less_than(input);
cout << "Verified:" << flag << endl;
return flag;
}
// Computes duration given a start time and a stop time in nano seconds
long long ComputeDuration(chrono::high_resolution_clock::time_point start_time, chrono::high_resolution_clock::time_point end_time) {
// Add code
long long res = 0;
res = chrono::duration_cast<chrono::nanoseconds>(end_time - start_time).count();
return res;
}
// Wrapper function to test the different sorting algorithms
int testSortingWrapper(int argc, char **argv) {
//const string input_type = string(argv[1]);
//const int input_size = stoi(string(argv[2]));
//const string comparison_type = string(argv[3]);
string input_type = "random";
int input_size = stoi("25");
string comparison_type = "less";
if (input_type != "random" && input_type != "sorted_small_to_large" && input_type != "sorted_large_to_small") {
cout << "Invalid input type" << endl;
return 0;
}
if (input_size <= 0) {
cout << "Invalid size" << endl;
return 0;
}
if (comparison_type != "less" && comparison_type != "greater") {
cout << "Invalid comparison type" << endl;
return 0;
}
// This block of code to be removed for your final submission.
// removed
// TestingTiming();
//sort();
cout << "Running sorting algorithms: " << input_type << " " << input_size << " numbers " << comparison_type << endl;
vector<int> input_vector;
if (input_type == "random") {
// Generate random vector
input_vector = GenerateRandomVector(input_size);
}
else {
// Generate sorted vector.
if (input_type == "sorted_small_to_large"){
input_vector = GenerateSortedVector(input_size, true);
}
else{
input_vector = GenerateSortedVector(input_size, false);
}
}
// Call quicksort / heapsort / mergesort using appropriate input.
// ...
// if comparison type is "less" then call
// MergeSort(input_vector, less<int>{})
// otherwise call
// MergeSort(input_vector, greater<int>{})
// ...
if (comparison_type == "less"){
cout << "HeapSort" << endl;
auto begin = chrono::high_resolution_clock::now();
// Time this piece of code.
heapsort(input_vector, tools::less);
// End of piece of code to time.
auto end = chrono::high_resolution_clock::now();
VerifyOrder(input_vector, judge::less);
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
cout << "MergeSort" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
mergeSort(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
cout << "QuickSort" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quicksort(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
input_vector = GenerateSortedVector(input_size, true);
cout << "QuickSort2" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quickSort2(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
input_vector = GenerateSortedVector(input_size, true);
cout << "QuickSort3" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quicksort3(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
}else{
cout << "HeapSort" << endl << endl;;
auto begin = chrono::high_resolution_clock::now();
// Time this piece of code.
heapsort(input_vector, tools::greater);
VerifyOrder(input_vector, judge::greater);
// End of piece of code to time.
auto end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
cout << "MergeSort" << endl << endl;;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
mergeSort(input_vector, tools::greater);
VerifyOrder(input_vector, judge::greater);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
cout << "QuickSort" << endl << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quicksort(input_vector, tools::greater);
VerifyOrder(input_vector, judge::greater);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
input_vector = GenerateSortedVector(input_size, false);
cout << "QuickSort2" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quickSort2(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
input_vector = GenerateSortedVector(input_size, false);
cout << "QuickSort3" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quicksort3(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
}
// Call quicksort with median of three as pivot / middle as pivot / first as pivot using appropriate input.
// ...
// if comparison type is "less" then call
// QuickSort(input_vector, less<int>{})
// otherwise call
// QuickSort(input_vector, greater<int>{})
// ...
return 0;
}
// Do not change anything below
int main(int argc, char **argv) {
if (argc != 4) {
cout << "Usage: " << argv[0] << "<input_type> <input_size> <comparison_type>" << endl;
return 0;
}
testSortingWrapper(argc, argv);
return 0;
}
//int main(int argc) {
// /*if (argc != 4) {
// cout << "Usage: " << argv[0] << "<input_type> <input_size> <comparison_type>" << endl;
// return 0;
// }*/
// testSortingWrapper(argc, NULL);
// return 0;
//}
看一下这篇文档。
https://www.runoob.com/w3cnote/c-templates-detail.html
您好，我是有问必答小助手，您的问题已经有小伙伴解答了，您看下是否解决，可以追评进行沟通哦~
如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～
ps:问答VIP仅需29元，即可享受5次/月 有问必答服务，了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632