美文网首页
STL 容器操作效率测试

STL 容器操作效率测试

作者: FredricZhu | 来源:发表于2023-09-26 13:35 被阅读0次

本例是<C++ 性能优化指南>一书STL容器部分的代码。
着重比较了STL各种操作的性能。
代码比较长。
conanfile.txt

[requires]
boost/1.72.0

[generators]
cmake

CMakeLists.txt

cmake_minimum_required(VERSION 2.6)

project(optimize)
set(ENV{PKG_CONFIG_PATH} "$ENV{PKG_CONFIG_PATH}:/usr/local/lib/pkgconfig/")

set ( CMAKE_CXX_FLAGS "-pthread")
set(CMAKE_CXX_STANDARD 17)
add_definitions(-g)

include(${CMAKE_BINARY_DIR}/conanbuildinfo.cmake)
conan_basic_setup()

include_directories(${CMAKE_CURRENT_SOURCE_DIR}/include)
LINK_DIRECTORIES(${LINK_DIRS})

file( GLOB main_file_list ${CMAKE_CURRENT_SOURCE_DIR}/*.cpp) 
file( GLOB source_file_list ${CMAKE_CURRENT_SOURCE_DIR}/impl/*.cpp)

foreach( main_file ${main_file_list} )
    file(RELATIVE_PATH filename ${CMAKE_CURRENT_SOURCE_DIR} ${main_file})
    string(REPLACE ".cpp" "" file ${filename})
    add_executable(${file}  ${main_file} ${source_file_list})
    target_link_libraries(${file}  ${CONAN_LIBS} pthread)
endforeach( main_file ${main_file_list})

stopwatch.h

#ifndef _STOPWATCH_H_
#define _STOPWATCH_H_

#include <iostream>

template <class T>
class basic_stopwatch: public T {
public:
    using BaseTimer = T;
    using tick_t = typename T::tick_t;

    // 创建可选的,开始对一个行为计时
    explicit basic_stopwatch(bool start);
    explicit basic_stopwatch(char const* activity="Stopwatch",  
        bool start=true);

    basic_stopwatch(std::ostream& log,
                    char const* activtity="Stopwatch",
                    bool start=true);
    
    ~basic_stopwatch();

    // 获取上次stop以后lap的时间
    tick_t LapGet() const;

    bool IsStarted() const;

    tick_t Show(char const* event="show");

    tick_t Start(char const* event_name="start");

    tick_t Stop(char const* event_name="stop");

private:
    char const* m_activity;
    tick_t m_lap;
    std::ostream& m_log;
};

template <class T>
inline basic_stopwatch<T>::basic_stopwatch(bool start_now):
    m_activity("StopWatch"),
    m_lap(0),
    m_log(std::cout) {
        if(start_now) {
            Start();
        }
    }

template <class T>
inline basic_stopwatch<T>::basic_stopwatch(char const* activity,  
        bool start):
        m_activity(activity&&activity[0]? activity: nullptr),
        m_lap(0),
        m_log(std::cout) {
            if(start) {
                if(m_activity) {
                    Start();
                }else {
                    // 没有activity,连事件名都没有
                    Start(nullptr);
                }
            }
        }


template <typename T>
inline basic_stopwatch<T>::basic_stopwatch(std::ostream& log,
                    char const* activtity,
                    bool start):
                    m_activity(activtity&&activtity[0]? activtity: nullptr),
                    m_lap(0),
                    m_log(log) {
                        if(start) {
                            Start();
                        } else {
                            Start(nullptr);
                        }
                    }



template <class T>
inline basic_stopwatch<T>::~basic_stopwatch() {
    if(IsStarted()) {
        if(m_activity) {
            Stop();
        } else {
            Stop(nullptr);
        }
    }
}


template <class T>
inline bool basic_stopwatch<T>::IsStarted() const {
    return BaseTimer::IsStarted();
}


template <class T>
inline typename basic_stopwatch<T>::tick_t basic_stopwatch<T>::LapGet() const {
    return m_lap;
}

template <class T>
inline typename basic_stopwatch<T>::tick_t basic_stopwatch<T>::Show(char const* event_name) {
    if(IsStarted()) {
        m_lap = BaseTimer::GetMs();
        if(event_name && event_name[0]) {
            if(m_activity) {
                m_log << m_activity << ": ";
            }

            m_log << event_name << " at " << m_lap << " mS" << std::endl << std::flush;  
        }
    }else {
        if(m_activity) {
            m_log << m_activity << ": not started" << std::endl << std::flush;
        }
    }
    return m_lap;
}


template <class T>
inline typename basic_stopwatch<T>::tick_t basic_stopwatch<T>::Start(char const* event_name) {
    if(IsStarted()) {
        Stop(event_name);
    } else {
        if(event_name && event_name[0]) {
            if(m_activity) {
                m_log << m_activity << ": ";
            }

            m_log << event_name << std::endl << std::flush;
        }
    }

    BaseTimer::Start();
    return m_lap;
}


template <class T>
inline typename basic_stopwatch<T>::tick_t basic_stopwatch<T>::Stop(char const* event_name) {
    if(IsStarted()) {
        m_lap = BaseTimer::GetMs();
        if(event_name && event_name[0]) {
            if(m_activity) {
                m_log << m_activity << ": ";
            }
            m_log << event_name << " " << m_lap << "mS" << std::endl << std::flush;
        }
    }

    BaseTimer::Clear();
    return m_lap;
}


#endif

stopwatch11.h

#ifndef STOPWATCH11_H
#define STOPWATCH11_H

#include <chrono>

using namespace std::chrono;

class TimerBaseChrono {
public:
    using tick_t = unsigned long;
    // 构造函数,clears the timer
    TimerBaseChrono(): m_start(system_clock::time_point::min()) {}

    // clears the timer
    void Clear() {
        m_start = system_clock::time_point::min();
    }

    bool IsStarted() const {
        return m_start != system_clock::time_point::min();
    }

    // starts the timer
    void Start() {
        m_start = system_clock::now();
    }

    unsigned long GetMs() {
        if(IsStarted()) {
            system_clock::duration diff;
            diff = system_clock::now() - m_start;
            return (unsigned)(duration_cast<milliseconds>(diff).count());
        }
        return 0;
    }
private:
    system_clock::time_point m_start;
};

#include "stopwatch.h"
using StopWatch = basic_stopwatch<TimerBaseChrono>;
// 声明 stopwatch的测试方法,在外面调用
int test_stopwatch11(int test_no, unsigned long);
# endif

kvstruct.h

#ifndef _FREDRIC_KVSTRUCT_H_
#define _FREDRIC_KVSTRUCT_H_
#include <cstring>


// simple, non-template key/value class with char[] keys, unsigned values
struct kvstruct {
    char key[9];
    unsigned value; 

    kvstruct(unsigned k): value(k) {
        char buf[9];
        strcpy(key, stringify(k, buf));
    }

    // Dec to Hex 
    static char const* stringify(unsigned i, char* buf) {
        buf[8] = 0;
        char* bufp = &buf[8];
        do {
            *--bufp = "0123456789ABCDEF"[i & 0xf];
            i >>= 4;
        } while(i!=0);
        return bufp;
    }

    bool operator<(kvstruct const& that) const { return strcmp(this->key, that.key) < 0; }
    bool operator==(kvstruct const& that) const { return strcmp(this->key, that.key) == 0; }
};

#endif

charbuf.h

#ifndef _FREDRIC_CHAR_BUF_H_
#define _FREDRIC_CHAR_BUF_H_

#include "hash.h"  // hash function 用来扩展std::hash
#include "array_iterator.h" // std::begin(), std::end(), std::size()

// Simple container for a char[] text string
template <unsigned N=10, typename T=char>
struct charbuf{
    charbuf();
    charbuf(charbuf const& cb);
    charbuf(T const* p);
    charbuf& operator=(charbuf const& rhs);
    charbuf& operator=(T const* rhs);

    T* data();
    T const* data() const;

    operator size_t() const;

    bool operator==(charbuf const& that) const;
    bool operator<(charbuf const& that) const;

    size_t capacity() const;
    size_t hash1() const;
    size_t hash2() const;

private:
    T data_[N];
};



template <unsigned N, typename T>
inline charbuf<N, T>::charbuf() {
    for(auto it=std::begin(data_); it<std::end(data_); ++it) {
        *it = 0;
    }
}


template <unsigned N, typename T>
inline charbuf<N, T>::charbuf(charbuf const& cb) {
    T const* p = cb.data();

    for(auto it=std::begin(data_); it!=std::end(data_); ++it) {
        *it = *p;
        if(*p) {
            ++p;
        }
    }
}

template <unsigned N, typename T>
inline charbuf<N, T>::charbuf(T const* p) {
    if(p == nullptr) {
        p = "";
    }
    for(auto it=std::begin(data_); it!=std::end(data_); ++it) {
        *it = *p;
        if(*p) {
            ++p;
        }
    }
}

template <unsigned N, typename T>
inline charbuf<N, T>& charbuf<N, T>::operator=(charbuf const& rhs) {
    if(this != &rhs) {
        T const* p= rhs.data();
        for(auto it=std::begin(data_); it!=std::end(data_); ++it) {
            *it = *p;
            if(*p) {
                ++p;
            }
        }
    }
    return *this;
}

template <unsigned N, typename T>
inline charbuf<N, T>& charbuf<N, T>::operator=(T const* rhs) {
    if(rhs != data_) {
        if(rhs == nullptr) {
            rhs = "";
        }

        for(auto it=std::begin(data_); it!=std::end(data_); ++it) {
            *it = *rhs;
            if(*rhs) {
                ++rhs;
            }
        }
    }
    return *this;
}

template <unsigned N, typename T>
inline T* charbuf<N, T>::data() {
    return data_;
}

template <unsigned N, typename T>
inline T const* charbuf<N, T>::data() const {
    return data_;
}

template <unsigned N, typename T>
inline size_t charbuf<N, T>::hash1() const {
    return hash_range(std::begin(data_), std::end(data_));
}

template <unsigned N, typename T>
inline size_t charbuf<N, T>::hash2() const {
    size_t hash = 5381;
    for(T const* it=std::begin(data_); it!=std::end(data_); ++it) {
        hash = (hash << 6) + hash + (*it);
    }
    return hash;
}

template <unsigned N, typename T>
inline charbuf<N,T>::operator size_t () const {
    return hash1();
}

template <unsigned N, typename T>
inline bool charbuf<N, T>::operator==(charbuf const& that) const {
    return strcmp(this->data_, that.data_) == 0;
}

template <unsigned N, typename T>
inline bool charbuf<N, T>::operator<(charbuf const& that) const {
    return strcmp(this->data_, that.data_) < 0;
}

template <unsigned N, typename T>
inline size_t charbuf<N, T>::capacity() const {
    return N;
}
  

#endif

hash.h

#ifndef _FREDIRC_HASH_H_
#define _FREDRIC_HASH_H_

#include <cstddef>
#include <boost/container_hash/hash.hpp>

template <typename IT>
inline size_t hash_range(IT first, IT last) {
    size_t hash = 0;
    for(; first!=last; ++first) {
        boost::hash_combine(hash, *first);
    }
    return hash;
}

// Hash 一个支持迭代器的顺序容器
template <typename SEQ> 
struct hash_seq {
    size_t operator()(SEQ const& x) const {
        return hash_range(x.begin(), x.end());
    }
};
#endif

test_driver.h

#ifndef _FREDRIC_TEST_DRIVER_H_
#define _FREDRIC_TEST_DRIVER_H_
using test_func = int(*)(int, unsigned long);
// 调用多个 test_func类型的函数
void test_driver(test_func* flist, int argc=0, char** argv=0);

// 调用一个test_func类型的函数
void test_driver(test_func f, int argc=0, char** argv=0);
#endif

array_iterator.h

#ifndef _FREDRIC_ARRAY_ITERATOR_H_
#define _FREDRIC_ARRAY_ITERATOR_H_
#include <cstddef>

// 获取c style array 大小的模板方法
namespace std {
    template <typename T, int N>
    size_t size(T (&a) [N]) {
        return N;
    }
};

#endif

vector.cpp

#include "stopwatch11.h"
#include "kvstruct.h"

#include <iostream>
#include <algorithm>
#include <vector>

bool test_vector(std::vector<kvstruct> const& random_vector, unsigned long multiplier) {
    bool rc = true;
    std::size_t const nelts = random_vector.size();

    std::cout << std::endl << "std::vector  " << random_vector.size() << " entries" << std::endl << std::endl;

    // std::vector 插入和删除
    {
        StopWatch sw("assign vector to vector + delete x 1000");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<multiplier; ++j) {
            test_container = random_vector;
            std::vector<kvstruct>().swap(test_container);
        }
    }
    
    // 1000 次的插入和删除统计 
    {   
        StopWatch sw("assign vector to vector", false);
        StopWatch::tick_t ticks;
        StopWatch::tick_t assign_x_1000 = 0;
        StopWatch::tick_t delete_x_1000 = 0;
        std::vector<kvstruct> test_container;

        for(unsigned j=0; j<1000; ++j) {
            sw.Start("");
            test_container = random_vector;
            ticks = sw.Show("");
            assign_x_1000 += ticks;

            std::vector<kvstruct>().swap(test_container);
            delete_x_1000 += sw.Stop("") - ticks;
        }

        std::cout << "  assign vector to vector x 1000: " 
            << assign_x_1000 << "ms" << std::endl;
        
        std::cout << "  vector delete x 1000: "
            << delete_x_1000 << "ms" << std::endl;
    }

    // std::vector 迭代器插入加删除1000次
    {
        StopWatch sw("vector iterator insert(begin()) vector + delete x 1000");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<1000; ++j) {
            test_container.insert(test_container.begin(), random_vector.begin(), random_vector.end());
            std::vector<kvstruct>().swap(test_container);
        }
    }

    {
        StopWatch sw("same, only with reserve");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<1000; ++j) {
            test_container.reserve(nelts);
            test_container.insert(test_container.begin(), random_vector.begin(), random_vector.end());
            std::vector<kvstruct>().swap(test_container);
        }
    }

    {
        StopWatch sw("vector iterator insert(end()) vector + delete x 1000");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<1000; ++j) {
            test_container.insert(test_container.end(), random_vector.begin(), random_vector.end());
            std::vector<kvstruct>().swap(test_container);
        }
    }

    {
        StopWatch sw("vector iterator push_back() to vector + delete x 1000");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<1000; ++j) {
            for(auto it=random_vector.begin(); it != random_vector.end(); ++it) {
                test_container.push_back(*it);
            }
            std::vector<kvstruct>().swap(test_container);
        }
    }

    {
        StopWatch sw("same, only with reserve");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<1000; ++j) {
            test_container.reserve(nelts);
            for(auto it=random_vector.begin(); it != random_vector.end(); ++it) {
                test_container.push_back(*it);
            }
            std::vector<kvstruct>().swap(test_container);
        }
    }

    {
        StopWatch sw("vector.at() push_back() to vector + delete x 1000");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<1000; ++j) {
            for(unsigned i=0; i<nelts; ++i) {
                test_container.push_back(random_vector.at(i));
            }

            std::vector<kvstruct>().swap(test_container);
        }
    }

    {
        StopWatch sw("vector[] push_back() to vector + delete x 1000");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<1000; ++j) {
            for(unsigned i=0; i<nelts; ++i) {
                test_container.push_back(random_vector[i]);
            }
            std::vector<kvstruct>().swap(test_container);
        }
    }

    {
        StopWatch sw("vector iterator insert at back to vector + delete x 1000");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<1000; ++j) {
            for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                test_container.insert(test_container.end(), *it);
            }
            std::vector<kvstruct>().swap(test_container);
        }
    }

    {
        StopWatch sw("same, but with reserve");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<1000; ++j) {
            test_container.reserve(nelts);
            for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                test_container.insert(test_container.end(), *it);
            }
            std::vector<kvstruct>().swap(test_container);
        }
    }

    {
        StopWatch sw("vector.at() insert at end + delete x 1000");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<1000; ++j) {
            for(unsigned i=0; i<nelts; ++i) {
                test_container.insert(test_container.end(), random_vector.at(i));
            }

            std::vector<kvstruct>().swap(test_container);
        }
    }

    {
        StopWatch sw("vector[] insert at the end + delete x 1000");
        std::vector<kvstruct> test_container;
        for(unsigned j=0; j<1000; ++j) {
            for(unsigned i=0; i<nelts; ++i) {
                test_container.insert(test_container.end(), random_vector[i]);
            }
            std::vector<kvstruct>().swap(test_container);
        }
    }

    // vector insert at front part 
    std::vector<kvstruct> test_container;
    {
        StopWatch sw("vector interator insert at front to vector");
        for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
            test_container.insert(test_container.begin(), *it);
        }
    }

    std::vector<kvstruct>().swap(test_container);
    {
        StopWatch sw("same but with reserve");
        test_container.reserve(nelts);
        for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
            test_container.insert(test_container.begin(), *it);
        }
    }

    std::vector<kvstruct>().swap(test_container);
    {
        StopWatch sw("vector at() insert at front");
        for(unsigned i=0; i<nelts; ++i) {
            test_container.insert(test_container.begin(), random_vector.at(i));
        }
    }

    std::vector<kvstruct>().swap(test_container);
    {
        StopWatch sw("vector [] insert at front");
        for(unsigned i=0; i<nelts; ++i) {
            test_container.insert(test_container.begin(), random_vector[i]);
        }
    }


    // vector traversal
    {
        long long sum;
        std::vector<kvstruct> test_container = random_vector;

        sum = 0;
        {
            StopWatch sw("traversal vector (at) x 1000");
            for(unsigned j=0; j<1000; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    sum += test_container.at(i).value;
                }
            }
        }
        rc &= (sum!=0);

        sum = 0;
        {
            StopWatch sw("traversal vector, subscript, size() x 1000");
            for(unsigned j=0; j<1000; ++j) {
                for(unsigned i=0; i<test_container.size(); ++i) {
                    sum += test_container[i].value;
                }
            }
        }

        rc &= (sum!=0);

        sum = 0;
        {
            StopWatch sw("traversal vector (subscript) x 1000");
            for(unsigned j=0; j<1000; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    sum += test_container[i].value;
                }
            }
        }

        rc &= (sum!=0);

        sum = 0;
        {
            StopWatch sw("traversal vector (iterator) x 1000");
            for(unsigned j=0; j<1000; ++j) {
                for(auto it=test_container.begin(); it!=test_container.end(); ++it) {
                    sum += it->value;
                }
            }
        }

        rc &= (sum!=0);
    }

    // vector sort
    {
        std::vector<kvstruct> sorted_container;
        sorted_container = random_vector;

        {
            StopWatch sw("std::sort() vector + assign + delete x 100");
            for(unsigned j=0; j<100; ++j) {
                sorted_container = random_vector;
                std::sort(sorted_container.begin(), sorted_container.end());
            }
        }

        {
            StopWatch sw("std::sort() sorted vector x 100");
            for(unsigned j=0; j<100; ++j) {
                std::sort(sorted_container.begin(), sorted_container.end());
            }
        }
        rc &= (sorted_container.size() == random_vector.size());

        // std::stable_sort
        sorted_container = random_vector;
        {
            StopWatch sw("std::stable_stort() vector assign + delete x 100");
            for(unsigned j=0; j<100; ++j) {
                sorted_container = random_vector;
                std::stable_sort(sorted_container.begin(), sorted_container.end());
            }
        }

        {
            StopWatch sw("std::stable_sort() sorted vector x 100");
            for(unsigned j=0; j<100; ++j) {
                std::stable_sort(sorted_container.begin(), sorted_container.end());
            }
        }

        rc &= (sorted_container.size() == random_vector.size());
    }

    // lookup
    {
        std::vector<kvstruct> sorted_container;
        sorted_container = random_vector;
        std::sort(sorted_container.begin(), sorted_container.end());

        StopWatch sw("lookup in sorted vector x 100");

        std::vector<kvstruct>::iterator kp;
        for(unsigned j=0; j<100; ++j) {
            for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                kp = std::lower_bound(sorted_container.begin(), sorted_container.end(),
                    *it);
                // 不可能有小于的,因为random_vector中的值都是 sorted_container中的值,都是
                // *it == *kp
                if(kp!= sorted_container.end() && *it < *kp) {
                    kp = sorted_container.end();
                }
            }
        }

        rc &= (kp != sorted_container.end());
    }
    
    return rc;
}

list.cpp

#include "stopwatch11.h"
#include "kvstruct.h"

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>

// TODO: add test_list code
bool test_list(std::vector<kvstruct> const& random_vector, unsigned long multiplier) {
    bool rc = true;
    std::size_t const nelts = random_vector.size();
    std::cout << std::endl << "std::list " << random_vector.size() << " entries" << std::endl
        << "multiplier == " << multiplier << std::endl << std::endl;

    std::list<kvstruct> random_container; 
    // list insert and delete
    {
        random_container.insert(random_container.end(), random_vector.begin(), random_vector.end());

        {
            StopWatch sw("assign list to list + delete x multiplier");
            StopWatch::tick_t begin_ticks = 0;
            StopWatch::tick_t assign_ticks = 0;
            StopWatch::tick_t assign_x_1000 = 0;
            StopWatch::tick_t delete_x_1000 = 0;

            std::list<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                test_container = random_container;
                assign_ticks = sw.Show("");
                assign_x_1000 += assign_ticks - begin_ticks;
                test_container.clear();
                begin_ticks = sw.Show("");
                delete_x_1000 += begin_ticks - assign_ticks;
            }

            std::cout << "assign " << assign_x_1000 << "ms"
                << "    + delete "
                << delete_x_1000 << "ms"
                << " == " << (assign_x_1000 + delete_x_1000)
                << "ms" << std::endl;
        }

        {
            StopWatch sw("vector iterator insert(end()) + delete x multiplier");
            std::list<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                test_container.insert(test_container.end(), random_vector.begin(), random_vector.end());
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector iterator push_back() + delete x multiplier");
            std::list<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                    test_container.push_back(*it);
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector at() push_back + delete x multiplier");
            std::list<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    test_container.push_back(random_vector.at(i));
                }

                test_container.clear();
            }
        }

        {
            StopWatch sw("vector[] push_back + delete x multiplier");
            std::list<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    test_container.push_back(random_vector[i]);
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector iterator push_front() + delete multiplier");
            std::list<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                    test_container.push_front(*it);
                }
                test_container.clear();
            }
        }

        {   StopWatch sw("vector.at() push_front() + delete x multiplier");
            std::list<kvstruct> test_container;
            for (unsigned j = 0; j < multiplier; ++j) {
                for (unsigned i = 0; i < nelts; ++i)
                    test_container.push_front(random_vector.at(i));
                test_container.clear();
            }
        }
        {   StopWatch sw("vector[] push_front() + delete x multiplier");
            std::list<kvstruct> test_container;
            for (unsigned j = 0; j < multiplier; ++j) {
                for (unsigned i = 0; i < nelts; ++i)
                    test_container.push_front(random_vector[i]);
                test_container.clear();
            }
        }

        {   StopWatch sw("vector iterator insert at back + delete x multiplier");
            std::list<kvstruct> test_container;
            for (unsigned j = 0; j < multiplier; ++j) {
                for (auto it = random_vector.begin(); it != random_vector.end(); ++it)
                    test_container.insert(test_container.end(), *it);
                test_container.clear();
            }
        }
        {   StopWatch sw("vector.at() insert at end + delete x multiplier");
            std::list<kvstruct> test_container;
            for (unsigned j = 0; j < multiplier; ++j) {
                for (unsigned i = 0; i < nelts; ++i)
                    test_container.insert(test_container.end(), random_vector.at(i));
                test_container.clear();
            }
        }
        {   StopWatch sw("vector[] insert at end + delete x multiplier");
            std::list<kvstruct> test_container;
            for (unsigned j = 0; j < multiplier; ++j) {
                for (unsigned i = 0; i < nelts; ++i)
                    test_container.insert(test_container.end(), random_vector[i]);
                test_container.clear();
            }
        }

        {   StopWatch sw("vector iterator insert at last position + delete x multiplier");
            std::list<kvstruct> test_container;
            for (unsigned j = 0; j < multiplier; ++j) {
                auto place = test_container.begin();
                for (auto it = random_vector.begin(); it != random_vector.end(); ++it)
                    place = test_container.insert(place, *it);
                test_container.clear();
            }
        }

        {   StopWatch sw("vector iterator insert at front + delete x multiplier");
            std::list<kvstruct> test_container;
            for (unsigned j = 0; j < multiplier; ++j) {
                for (auto it = random_vector.begin(); it != random_vector.end(); ++it)
                    test_container.insert(test_container.begin(), *it);
                test_container.clear();
            }
        }
        {   StopWatch sw("vector.at() insert at front + delete x multiplier");
            std::list<kvstruct> test_container;
            for (unsigned j = 0; j < multiplier; ++j) {
                for (unsigned i = 0; i < nelts; ++i)
                    test_container.insert(test_container.begin(), random_vector.at(i));
                test_container.clear();
            }
        }
        {   StopWatch sw("vector[] insert at frone + delete x multiplier");
            std::list<kvstruct> test_container;
            for (unsigned j = 0; j < multiplier; ++j) {
                for (unsigned i = 0; i < nelts; ++i)
                    test_container.insert(test_container.begin(), random_vector[i]);
                test_container.clear();
            }
        }
    }

    //  traversal
    {
        std::list<kvstruct> test_container;
        unsigned long long sum;
        sum = 0;
        test_container = random_container;
        {   StopWatch sw("traverse list (iterator) x 1000");
            for (unsigned j = 0; j < 1000; ++j)
                for (auto it = test_container.begin(); it != test_container.end(); ++it)
                    sum += it->value;
        }
        rc &= (sum != 0);
    }

    //  list sort
    {
        std::list<kvstruct> sorted_container;
        {   StopWatch sw("std::list::sort() list + build + delete x 100");
            for (unsigned j = 0; j < 100; j++) {
                sorted_container = random_container;
                sorted_container.sort();
            }
        }
        {   StopWatch sw("std::list::sort() sorted list x 100");
            for (unsigned j = 0; j < 100; j++) {
                sorted_container.sort();
            }
        }
        rc &= (sorted_container.size() == random_vector.size());
    }

    return rc;
}

deque.cpp

#include "stopwatch11.h"
#include "kvstruct.h"

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>

bool test_deque(std::vector<kvstruct> const& random_vector, unsigned long multiplier) {
    bool rc = true;
    std::size_t const nelts = random_vector.size();
    std::cout << std::endl << "std::deque " << random_vector.size() << " entries" << std::endl << std::endl;

    std::deque<kvstruct> random_container;

    // deque insert and delete
    {
        std::cout << "multiplier == " << multiplier << std::endl;
        random_container.insert(random_container.end(), random_vector.begin(), random_vector.end());

        {
            StopWatch sw("assign deque to deque + delete x multiplier");
            StopWatch::tick_t begin_ticks = 0;
            StopWatch::tick_t assign_ticks = 0;
            StopWatch::tick_t assign_x_1000 = 0;
            StopWatch::tick_t delete_x_1000 = 0;

            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                test_container = random_container;
                assign_ticks = sw.Show("");
                assign_x_1000 += assign_ticks - begin_ticks;
                test_container.clear();
                begin_ticks = sw.Show("");
                delete_x_1000 += begin_ticks - assign_ticks;
            }

            std::cout << "  assign " << assign_x_1000 << "ms"
                << " + delete " << delete_x_1000 << "ms"
                << " == " << (assign_x_1000 + delete_x_1000) << "ms";
        }

        {
            StopWatch sw("vector iterator insert(end()) + delete x multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                test_container.insert(test_container.end(), random_vector.begin(), random_vector.end());
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector iterator push_back() + delete x multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                    test_container.push_back(*it);
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector.at() push_back() + delete x multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    test_container.push_back(random_vector.at(i));
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector[] push_back() + delete x multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    test_container.push_back(random_vector[i]);
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector iterator push_front() + delete x multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                    test_container.push_front(*it);
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector at() push_front() + delete multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    test_container.push_front(random_vector.at(i));
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector[] push_front() + delete multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    test_container.push_front(random_vector[i]);
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector iterator insert at back + delete x multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                    test_container.insert(test_container.end(), *it);
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector at() insert at end + delete x multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    test_container.insert(test_container.end(), random_vector.at(i));
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector[] insert at end + delete x multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    test_container.insert(test_container.end(), random_vector[i]);
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector iterator insert at front + delete x multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(auto it = random_vector.begin(); it!=random_vector.end(); ++it) {
                    test_container.insert(test_container.begin(), *it);
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector.at() insert at front + delete x multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    test_container.insert(test_container.begin(), random_vector.at(i));
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector[] insert at front + delete multiplier");
            std::deque<kvstruct> test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    test_container.insert(test_container.begin(), random_vector[i]);
                }
                test_container.clear();
            }
        }
    }


    // deque traversal
    {
        std::deque<kvstruct> test_container;
        test_container.insert(test_container.end(), random_vector.begin(), random_vector.end());
        long long sum;
        sum = 0;

        {
            StopWatch sw("traverse deque (at) x 1000");
            for(unsigned j=0; j<1000; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    sum += test_container.at(i).value;
                }
            }
        }

        rc &= (sum != 0);

        sum = 0;
        {
            StopWatch sw("traverse deque (subscript) x 1000");
            for(unsigned j=0; j<1000; ++j) {
                for(unsigned i=0; i<nelts; ++i) {
                    sum += test_container[i].value;
                }
            }
        }
        rc &= (sum != 0);

        sum = 0;
        {
            StopWatch sw("traverse deque iterator x 1000");
            for(unsigned j=0; j<1000; ++j) {
                for(auto it=test_container.begin(); it!=test_container.end(); ++it) {
                    sum += it->value;
                }
            }
        }

        rc &= (sum != 0);
    }


    // deque sort 
    {
        std::deque<kvstruct> sorted_container;
        {
            StopWatch sw("std::sort() deque build + delete x 100");
            for(unsigned j=0; j<100; ++j) {
                sorted_container = random_container;
                std::sort(sorted_container.begin(), sorted_container.end());
            }
        }

        {
            StopWatch sw("std::sort() sorted deque x 100");
            for(unsigned j=0; j<100; ++j) {
                std::sort(sorted_container.begin(), sorted_container.end());
            }
        }

        rc &= (sorted_container.size() == random_vector.size());

        // std::stable_sort() deque
        {
            StopWatch sw("std::stable_sort() deque + build + delete x 100");
            for(unsigned j=0; j<100; ++j) {
                sorted_container = random_container;
                std::stable_sort(sorted_container.begin(), sorted_container.end());
            }

            {
                StopWatch sw("std::stable_sort() sorted deque x 100");
                for(unsigned j=0; j<100; ++j) {
                    std::stable_sort(sorted_container.begin(), sorted_container.end());
                }
            }

            rc &= (sorted_container.size() == random_vector.size());
        }


        // lookup 
        {
            std::deque<kvstruct> sorted_container;
            sorted_container = random_container;
            std::sort(sorted_container.begin(), sorted_container.end());

            StopWatch sw("lookup in sorted vector x 100");

            std::deque<kvstruct>::iterator kp;
            for(unsigned j=0; j<100; ++j) {
                for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                    kp = std::lower_bound(
                        sorted_container.begin(),
                        sorted_container.end(),
                        *it
                    );
                    if(kp != sorted_container.end() && *it < *kp) {
                        kp = sorted_container.end();
                    }
                }
            }

            rc &= (kp != sorted_container.end());
        }
    }

    return rc;
}

map.cpp

 #include "kvstruct.h"
#include "charbuf.h"
#include "stopwatch11.h"

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

bool test_map(std::vector<kvstruct> const& random_vector, unsigned long multiplier) {
    bool rc = true;
    std::size_t const nelts = random_vector.size();
    std::cout << std::endl << "std::map " << random_vector.size() << " entries" << std::endl
        << " multiplier=" << multiplier << std::endl << std::endl;

    using ContainerT = std::map<charbuf<9>, unsigned>;
    using value_type = ContainerT::value_type;
    ContainerT random_container;
    
    for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
        random_container.insert(random_container.end(), value_type(it->key, it->value));
    }

    rc &= random_container.size() == nelts;

    // map insert and delete
    {
        StopWatch::tick_t begin_ticks = 0;
        StopWatch::tick_t assign_ticks = 0;
        StopWatch::tick_t assign_x_1000 = 0;
        StopWatch::tick_t delete_x_1000 = 0;

        {
            StopWatch sw("assign map to map + delete x multiplier");
            ContainerT test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                test_container = random_container;
                assign_ticks = sw.Show("");
                assign_x_1000 += assign_ticks - begin_ticks;
                test_container.clear();
                begin_ticks = sw.Show("");
                delete_x_1000 += begin_ticks - assign_ticks;
            }

            std::cout << "   assign " << assign_x_1000 << "ms"
                << " + delete "
                << delete_x_1000 << "ms"
                << "=="
                << (assign_x_1000 + delete_x_1000)
                << "ms" << std::endl;
        }

        {
            StopWatch sw("vector iterator insert to map + delete x multiplier");
            ContainerT test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                    test_container.insert(value_type(it->key, it->value));
                }

                test_container.clear();
            }
        }

        std::vector<kvstruct> sorted_vector = random_vector;
        std::stable_sort(sorted_vector.begin(), sorted_vector.end());
        {
            StopWatch sw("sorted vector iterator insert into map + delete x multiplier");
            ContainerT test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(auto it=sorted_vector.begin(); it!=sorted_vector.end(); ++it) {
                    test_container.insert(value_type(it->key, it->value));
                }

                test_container.clear();
            }
        }


        {
            StopWatch sw("sorted vector iterator insert into map w/end hint + delete x multiplier");
            ContainerT test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(auto it=sorted_vector.begin(); it!=sorted_vector.end(); ++it){
                    test_container.insert(test_container.end(), value_type(it->key, it->value));
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("sorted vector iterator insert into map w/C++98 preceeder hint + delete x multiplier");
            ContainerT test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                auto hint = test_container.end();
                for(auto it=sorted_vector.begin(); it!=sorted_vector.end(); ++it) {
                    hint = test_container.insert(hint, value_type(it->key, it->value));
                }
            }
            test_container.clear();
        }

        {
            StopWatch sw("sorted vector iterator insert into map w/ reverse iterator follow hint + delete x multiplier");
            ContainerT test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                auto hint = test_container.end();
                for(auto it=sorted_vector.rbegin(); it!=sorted_vector.rend(); ++it) {
                    hint = test_container.insert(hint, value_type(it->key, it->value)); 
                }
                test_container.clear();
            }
        }       
    }

    // map traversal
    ContainerT test_container = random_container;
    
    {
        unsigned long long sum;
        sum = 0;
        {
            StopWatch sw("traverse map (iterator) x multiplier");
            for(unsigned j=0; j<multiplier; ++j) {
                for(auto it=test_container.begin(); it!=test_container.end(); ++it) {
                    sum += it->second;
                }
            }
        }
        rc &= (sum != 0);
    }

    // map lookup 
    {
        StopWatch sw("map lookup x 100");
        for(unsigned j=0; j<100; ++j) {
            for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                rc &= (test_container.find(it->key) != test_container.end());
                if(test_container.find(it->key) == test_container.end()) {
                    std::cout << "error on key " << it->key << std::endl;
                }
            }
        }
    }
    
    return rc;
}

unordered_map.cpp

#include "charbuf.h"
#include "kvstruct.h"
#include "stopwatch11.h"

#include <iostream>
#include <vector>
#include <unordered_map>

// show properties of  a std::unordered_map
template <typename T>
void hash_stats(T const& table) {
    unsigned zeros = 0;
    unsigned ones = 0;
    unsigned many = 0;
    unsigned many_sigma = 0;

    for(unsigned i=0; i<table.bucket_count(); ++i) {
        unsigned how_many_this_bucket = 0;
        for(auto it=table.begin(i); it!=table.end(i); ++it) {
            how_many_this_bucket += 1;
        }

        switch (how_many_this_bucket) {
        case 0:
            zeros += 1;
            break;
        case 1:
            ones += 1;
            break;
        default: {
            many += 1;
            many_sigma += how_many_this_bucket;
        }
            break;
        }
    }

    std::cout << "unordered_map with " << table.size() << " entries" << std::endl 
        << "    " << table.bucket_count() << " buckets"
        << " load factor " << table.load_factor()
        << ", max load factor " << table.max_load_factor() << std::endl;
    if(many > 0) {
        std::cout << "  average length of multi-entry chain " <<((float)many_sigma)/many
            << std::endl;
    }
}

// Performance tests for std::unordered_map
bool test_unordered_map(std::vector<kvstruct> const& random_vector, unsigned long multiplier) {
    bool rc = true;
    std::size_t const nelts = random_vector.size();
    std::cout << std::endl << "std::unordered_map   " << random_vector.size() << " entries"
        << std::endl << "multiplier == " << multiplier << std::endl << std::endl;
    
    struct hash_charbuf {
        std::size_t operator()(charbuf<9> const& cb) const {
            return (size_t)cb;
        }
    };

    using ContainerT = std::unordered_map<charbuf<9>, unsigned, hash_charbuf>;
    using value_type = ContainerT::value_type;

    ContainerT random_container;

    for(auto it=random_vector.begin(); it!=random_vector.end(); ++it){
        random_container.insert(random_container.end(), value_type(it->key, it->value));
    }
    rc &= (random_container.size() == nelts);

    // unordered_map insert and delete 
    {
        StopWatch::tick_t begin_ticks = 0;
        StopWatch::tick_t assign_ticks = 0;
        StopWatch::tick_t assign_x_1000 = 0;
        StopWatch::tick_t delete_x_1000 = 0;

        {
            StopWatch sw("assign unordered_map to unordered_map + delete x multiplier");
            ContainerT test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                test_container = random_container;
                assign_ticks = sw.Show("");
                assign_x_1000 += assign_ticks - begin_ticks;
                test_container.clear();
                begin_ticks = sw.Show("");
                delete_x_1000 += begin_ticks - assign_ticks;
            }
        }

        std::cout << "  assign " << assign_x_1000 << "ms"
            << "    + delete "
            << delete_x_1000 << "ms"
            << " == " << (assign_x_1000 + delete_x_1000)
            << "ms" << std::endl;

        {
            ContainerT test_container;
            for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                test_container.insert(value_type(it->key, it->value));
            }
            std::cout << "test container, no optimization.";
            hash_stats(test_container);
        }

        {
            ContainerT test_container;
            test_container.max_load_factor(2.0f);
            for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                test_container.insert(value_type(it->key, it->value));
            }

            std::cout << "initially set to 100k buckets.";
            hash_stats(test_container);
        }

        {
            ContainerT test_container;
            test_container.rehash(random_vector.size());
            for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                test_container.insert(value_type(it->key, it->value));
            }

            std::cout << "initially set to 100k buckets.";
            hash_stats(test_container);
        }

        {
            StopWatch sw("vector iterator insert into unordered_map + delete multiplier");
            ContainerT test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                    test_container.insert(value_type(it->key, it->value));
                }

                test_container.clear();
            }
        }

        {
            StopWatch sw("vector iterator insert into unordered_map w/ pre-allocation + delete x multiplier");
            ContainerT test_container;
            for(unsigned j=0; j<multiplier; ++j) {
                test_container.rehash(random_vector.size()*5);
                for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                    test_container.insert(value_type(it->key, it->value));
                }
                test_container.clear();
            }
        }

        {
            StopWatch sw("vector iterator insert into unordered_map w/ max 0.8 + delete x multiplier");

            ContainerT test_container;
            test_container.max_load_factor(0.5f);
            for(unsigned j=0; j<multiplier; ++j) {
                test_container.rehash(random_vector.size() * 5);
                for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                    test_container.insert(value_type(it->key, it->value));
                }

                test_container.max_load_factor(1.0f);
                test_container.rehash(1);
                test_container.clear();
            }
        }

        ContainerT test_container = random_container;
        // unordered_map traversal
        {
            unsigned long long sum;
            sum = 0;
            {
                StopWatch sw("traversal unordered_map (iterator) x multiplier");
                for(unsigned j=0; j<multiplier; ++j) {
                    for(auto it=test_container.begin(); it!=test_container.end(); ++it) {
                        sum += it->second;
                    }
                }
            }

            rc &= (sum != 0);
        }

        // unordered_map lookup
        {
            ContainerT test_container;
            for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                test_container.insert(value_type(it->key, it->value));
            }

            hash_stats(test_container);
            {
                StopWatch sw("unordered_map lookup x 100");
                for(unsigned j=0; j<100; ++j) {
                    for(auto it=random_vector.begin(); it!=random_vector.end(); ++j) {
                        rc &= (test_container.find(it->key) != test_container.end());
                        if(test_container.find(it->key) == test_container.end()) {
                            std::cout << "error on key " << it->key << std::endl;
                        }
                    }
                }
            }

            test_container.clear();
            test_container.rehash(random_vector.size());
            for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                test_container.insert(value_type(it->key, it->value));
            }

            hash_stats(test_container);
            {
                StopWatch sw("unordered_map lookup, preallocated table x 100");
                for(unsigned j=0; j<100; ++j) {
                    for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
                        rc &= (test_container.find(it->key) != test_container.end());
                        if(test_container.find(it->key) == test_container.end()) {
                            std::cout << "error on key " << it->key << std::endl;
                        }
                    }
                }
            }
        }
    }

    return rc;
}

stl_list_test.cpp

#include "stopwatch11.h"
#include "kvstruct.h"
#include "test_driver.h"

#include <iostream>
#include <random>
#include <algorithm>
#include <vector>
#include <functional>
#include <set>
#include <list>


void build_random_vector(std::vector<kvstruct>& v, unsigned count) {
    std::set<unsigned> unique;
    std::default_random_engine e;
    // 从count 到 10*count的均匀分布
    std::uniform_int_distribution<unsigned> d(count, 10* count);
    auto randomizer = std::bind(d, e);
    v.clear();
    while(v.size() < count) {
        unsigned rv = randomizer();
        // 新元素插入
        if(unique.insert(rv).second == true) {
            v.emplace_back(rv);
        }
    }
}

bool test_vector(std::vector<kvstruct> const& random_vector, unsigned long multiplier);
bool test_deque(std::vector<kvstruct> const& random_vector, unsigned long multiplier);
bool test_list(std::vector<kvstruct> const& random_vector, unsigned long multiplier);
bool test_forward_list(std::vector<kvstruct> const& random_vector, unsigned long multiplier);
bool test_map(std::vector<kvstruct> const& random_vector, unsigned long multiplier);
bool test_unordered_map(std::vector<kvstruct> const& random_vector, unsigned long multiplier);


int test_stl(int test_no, unsigned long multiplier) {
    bool rc = true;
    unsigned long table_size = 100000;

    switch (test_no) {
    default:
        return -1;
    case 0: 
        return 2;
    case 1: // 测试kvstruct的各个方法和操作符是否工作
        {
            // 验证10进制转16进制成功
            char buf[9];
            rc &= (strcmp(kvstruct::stringify(0, buf), "0") == 0);
            rc &= (strcmp(kvstruct::stringify(0x123, buf), "123") == 0);
            rc &= (strcmp(kvstruct::stringify(0x1000, buf), "1000") == 0);
            rc &= (strcmp(kvstruct::stringify(0xffffffff, buf), "FFFFFFFF") == 0);

            // 测试build_random_vector返回的值都是唯一的
            std::vector<kvstruct> rnd_vector;
            build_random_vector(rnd_vector, 100);
            std::sort(rnd_vector.begin(), rnd_vector.end());
            for(unsigned i=1; i<rnd_vector.size(); ++i) {
                rc &= (rnd_vector[i-1].key < rnd_vector[i].key);
            }
        }
        break;
    case 2:
        {
            std::vector<kvstruct> rnd_vector;
            build_random_vector(rnd_vector, table_size);

            rc &= test_vector(rnd_vector, multiplier);
            rc &= test_deque(rnd_vector, multiplier);
            rc &= test_list(rnd_vector, multiplier);
            rc &= test_forward_list(rnd_vector, multiplier);
            rc &= test_map(rnd_vector, multiplier);
            rc &= test_unordered_map(rnd_vector, multiplier);
        }
        break;
    }
    return rc ? 1: 0;
}




int main(int argc, char* argv[]) {
    test_driver(test_stl, argc, argv);
    return EXIT_SUCCESS;
}

test_driver.cpp

#include "test_driver.h"
#include "priority_thread.h"

#include <iostream>
#include <cstring>

// 运行多少 千 次
// 默认1*1000
// 参数通过 ./xxx_test  -x2 传入
void test_driver(test_func* flist, int argc, char** argv) {
    unsigned long multiplier = 1;
    if(argc > 1) {
        // 第一个参数的前面两个是 -x,例如 ./xxxx_test -x3
        if(strncmp(argv[1], "-x", 2) == 0) {
            // 从 -x后面的数字开始,转换成ulong
            multiplier = strtoul(argv[1]+2, nullptr, 10);
        }
    } 

    // 测试函数列表为空,多个函数
    if(flist == nullptr) {  
        std::cout << "No test function" << std::endl;
    } else {
        std::cout << "multiplier set to " << multiplier << std::endl;
        // 进程拉到前台
        PriorityThread p;
        // 逐个执行flist中的函数
        for(unsigned f=0; flist[f]!=0; ++f) {
            if(flist[f] == nullptr) {
                continue;
            }

            // 执行测试合集, 合集的测试号为1, 0返回所有测试个数,2-end是单个测试
            if(flist[f](1, multiplier) == 1) {
                std::cout << "All tests pass" << std::endl;
            } else {
                std::cout << "Tests failed" << std::endl;
            }

            for(int i=2, e=flist[f](0, multiplier); i<=e; ++i) {
                if(flist[f](i, multiplier) != 1) {
                    std::cout << "test " << i << " failed" << std::endl;
                }
            }
        }
    }
}

void test_driver(test_func f, int argc, char** argv) {
    unsigned long multiplier = 1;
    if(argc > 1) {
        if(strncmp(argv[1], "-x", 2) == 0) {
            multiplier = strtoul(argv[1]+2, nullptr, 10);
        }
    }

    if(f == nullptr) {
        std::cout << "no test function" << std::endl;
    } else {
        std::cout << "multiplier set to: " << multiplier << std::endl;

        PriorityThread p;
        if(f(1, multiplier) == 1) {
            std::cout << "all tests pass" << std::endl;
        } else {
            std::cout << "tests failed" << std::endl;
        }

        for(int i=2, e=f(0, multiplier); i<=e; ++i) {
            if(f(i, multiplier) != 1) {
                std::cout << "test " << i << " failed" << std::endl;
            }
        }
    }
}

priority_thread.cpp

#include "priority_thread.h"
#include <iostream>

PriorityThread::PriorityThread() {
    // 设置当前进程nice值为最低,设置为最高优先级进程
    nice(-20);

    // 获取当前线程优先级,并保存为老的优先级参数,后续在析构函数中好进行恢复
    pthread_getschedparam(pthread_self(), &policy, &param);
    old_priority = param.sched_priority;

    // 设置当前线程优先级为最高优先级
    param.sched_priority = sched_get_priority_max(policy);
    pthread_setschedparam(pthread_self(), policy, &param);
}

PriorityThread::~PriorityThread() {
    // 析构函数中恢复当前进程和线程的优先级
    // 设置当前nice值为最高,降低优先级
    nice(19);

    // 恢复当前线程优先级为普通优先级
    param.sched_priority = old_priority;
    pthread_setschedparam(pthread_self(), policy, &param);
}

程序输出如下,如果是考虑各种方法的插入,删除,查找和相关效率来优化算法的话,这个数据还是可以参考一下的。


image.png

相关文章

网友评论

      本文标题:STL 容器操作效率测试

      本文链接:https://www.haomeiwen.com/subject/mwkhbdtx.html