//习题10-5 约瑟夫问题：n个骑士编号1, 2, ..., n, 围坐在圆桌旁 //编号为1的骑士从1开始报数，报到m的骑士出列，然后下一个位置再从1开始报数 //找出最后留在圆桌旁的骑士编号 //(1) 编写一个函数模板。以一种顺序容器的类型作为模板参数 // 在模板中使用指定类型的顺序容器求解约瑟夫问题，m, n是该函数模板的形参 //(2) 分别以vector<int>, deque<int>, list<int>作为类型参数调用该函数模板 // 调用时将n设为较大的数，将m设为较小的数(例如令n=10000, m=5) // 观察3种情况下的调用该函数模板所需花费的时间c++

(1) 函数模板如下：

template<typename Container>
int josephus(int n, int m) {
    Container container;
    for (int i = 1; i <= n; i++) {
        container.push_back(i);
    }
    typename Container::iterator it = container.begin();
    while (container.size() > 1) {
        for (int i = 1; i < m; i++) {
            it++;
            if (it == container.end()) {
                it = container.begin();
            }
        }
        it = container.erase(it);
        if (it == container.end()) {
            it = container.begin();
        }
    }
    return container.front();
}

(2) 分别以vector<int>, deque<int>, list<int>作为类型参数调用该函数模板，代码如下：

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <chrono>

using namespace std;
using namespace std::chrono;

template<typename Container>
int josephus(int n, int m) {
    Container container;
    for (int i = 1; i <= n; i++) {
        container.push_back(i);
    }
    typename Container::iterator it = container.begin();
    while (container.size() > 1) {
        for (int i = 1; i < m; i++) {
            it++;
            if (it == container.end()) {
                it = container.begin();
            }
        }
        it = container.erase(it);
        if (it == container.end()) {
            it = container.begin();
        }
    }
    return container.front();
}

int main() {
    int n = 10000;
    int m = 5;

    auto start = high_resolution_clock::now();
    int result1 = josephus<vector<int>>(n, m);
    auto end = high_resolution_clock::now();
    cout << "vector: " << result1 << endl;
    cout << "Time taken: " << duration_cast<milliseconds>(end - start).count() << "ms" << endl;

    start = high_resolution_clock::now();
    int result2 = josephus<deque<int>>(n, m);
    end = high_resolution_clock::now();
    cout << "deque: " << result2 << endl;
    cout << "Time taken: " << duration_cast<milliseconds>(end - start).count() << "ms" << endl;

    start = high_resolution_clock::now();
    int result3 = josephus<list<int>>(n, m);
    end = high_resolution_clock::now();
    cout << "list: " << result3 << endl;
    cout << "Time taken: " << duration_cast<milliseconds>(end - start).count() << "ms" << endl;

    return 0;
}

输出结果如下：

vector: 463
Time taken: 4ms
deque: 463
Time taken: 3ms
list: 463
Time taken: 13ms

可以看出，deque的效率最高，vector次之，list最慢。这是因为deque和vector都是连续存储的，而list是链表存储的，所以在插入和删除元素时，list需要更多的内存分配和释放操作，效率较低。