时间戳

首页 > 解决方案 > C++ 模板堆栈映射/多映射

c++ - C++ 模板堆栈映射/多映射

问题描述

我必须测量将 100000 个 int 类型数字添加到不同类型的容器中需要多少时间。所以有standard , vector , list - 这些都是正确的。而且我在做map和multimap时遇到了问题，然后我必须测量删除每个容器的所有这些元素需要多少时间。有什么线索吗？

每个容器必须保存 100000 个 int 类型编号。

  1. 创建一个堆栈容器 (s1)。测量向其中添加 100000 个数字需要多少时间。
  2. 创建一个堆栈容器（s2），它将像矢量容器一样管理内存。测量向其中添加 100000 个数字需要多少时间。
  3. 创建一个堆栈容器（s3），它将像列表容器一样管理内存。测量向其中添加 100000 个数字需要多少时间。
  4. 创建一个堆栈容器（s2），它将像地图容器一样管理内存。测量向其中添加 100000 个数字需要多少时间。
  5. 创建一个堆栈容器（s2），它将像多映射容器一样管理内存。测量向其中添加 100000 个数字需要多少时间。
  6. 测量删除所有容器的元素所需的时间。

附加信息：

  1. 使用标准 C++ 计时方法。可以这样计算时间：
clock_t begin = clock();
//instructions
clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
cout << elapsed_secs <<endl;
  1. 使用两种类型的自己的堆栈实现：
  • 未优化（正常工作且未定向以获得较少耗时的操作）
  • 优化（正常工作，但也针对获得更少耗时的操作）

也基于标准 stack<> 类的实现。

#include <iostream>
#include <stack>
#include <vector>
#include <list>
#include <map>

using namespace std;


template <class T>
void timeTest(T s)
{
    clock_t begin = clock();
    for (int i = 0; i < 100000; i++) { s.push(i); }
    clock_t end = clock();
    double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout << elapsed_secs << endl;
}

/*
template <class T, class S>
void timeTest(stack <int, map <int, int>> s)
{
    clock_t begin = clock();
    for (int i = 0; i < 100000; i++) { s.emplace(i, i); }
    clock_t end = clock();
    double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout << elapsed_secs << endl;
}

template <class T, class S>
void timeTest(stack <pair <int, int>, multimap <int, int>> s)
{
    clock_t begin = clock();
    for (int i = 0; i < 100000; i++) { s.emplace(i, i); }
    clock_t end = clock();
    double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout << elapsed_secs << endl;
}
*/


int main()
{
    stack <int> s1;
    stack <int, vector <int>> s2;
    stack <int, list <int>> s3;
    //stack <int, map <int, int>> s4;
    //stack<pair<int, int>, multimap<int, int>> s5;


    timeTest(s1);
    timeTest(s2);
    timeTest(s3);
    //timeTest(s4);
    //timeTest(s5);
}

标签： c++templatesmemory-managementstackmultimap

解决方案

找到了解决方案

#include <iostream>
#include <time.h>
#include <math.h>
#include <vector>
#include <map>
#include <list>
#include <stack>
using namespace std;

template<class T>
void test(T t,const int I = 1000000) {
    clock_t begin = clock();
    cout << "Uzupelnianie:\t";
    for (int i = 0; i <= I; i++) {
        t.push(i);
    }
    clock_t end = clock();
    double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout << elapsed_secs << endl;
    cout << "Usuwanie:\t";
    begin = clock();
    for (int i = 0; i <= I; i++) {
        t.pop();
    }
    end = clock();
    elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout << elapsed_secs << endl;
}


template<class T>
class Mapa {
public:
    map<T, T> mapa;
    using value_type = typename T;
    using reference = typename map<T, T>::reference;
    using const_reference = typename map<T, T>::const_reference;
    using size_type = typename map<T, T>::size_type;
    using container_type = map<T, T>;
    
    
    void push_back(T i) {
        mapa.emplace(i, i);
    }
    void pop_back() {        
        mapa.erase(prev(mapa.end()));
    }
    void empty() {
        cout << "empty\n";
    }
    void back() {
        cout << "back\n";
    }
    void size() {
        cout << "size\n";
    }
    
};

template<class T>
class MultiMapa {
public:
    multimap<T, T> mapa;
    using value_type = typename T;
    using reference = typename multimap<T, T>::reference;
    using const_reference = typename multimap<T, T>::const_reference;
    using size_type = typename multimap<T, T>::size_type;
    using container_type = multimap<T, T>;


    void push_back(T i) {
        mapa.emplace(i, i);
    }
    void pop_back() {
        mapa.erase(prev(mapa.end()));
    }
    void empty() {
        cout << "empty\n";
    }
    void back() {
        cout << "back\n";
    }
    void size() {
        cout << "size\n";
    }

};

int main()
{
    const int N = 1000000;
    stack<int> s1;
    stack<int, vector<int>> s2;
    stack<int, list<int>> s3;
    
    stack<int, Mapa<int>> s4; 
    stack<int, MultiMapa<int>> s5;
    cout << "Stack:\n";
    test(s1, N);

    cout << "Vector:\n";
    test(s2, N);

    cout << "List:\n";
    test(s3, N);

    cout << "Map:\n";
    test(s4,N); 
    
    cout << "MultiMapa:\n";
    test(s5, N);
}

推荐阅读