set vs unordered_set vs sorted vector

Question

Я начал задаваться вопросом, что представляет собой точная разница в производительности между set/unordered_set/sorted vector.

Таким образом, тестирование кода было написано, чтобы сравнить их время процесса, так что я могу доказать следующие утверждения, что я считаю: - Вектор является лучшим в линейном поиске - Unordered_set лучше при поиске из-за хэширования

#include <string> 
#include <set> 
#include <unordered_set> 
#include <vector> 
#include <iostream> 
#include <iomanip> 
#include <algorithm> 
#define WIN32_LEAN_AND_MEAN 
#include <Windows.h> 


void PrintSep(const std::string& title = "") 
{ 
    unsigned half = (78 - title.size())/2; 
    std::cout << std::string(half, '-') << ' ' << title << ' ' << std::string(half, '-') << std::endl; 
} // PrintSep 

void PrintTable(const char** names, double* times, unsigned count, unsigned colspan = 20) 
{ 
    std::cout << std::setw(colspan) << "type" << std::setw(colspan) << "time" << std::endl; 
    for(unsigned i = 0; i < count; ++i) 
     std::cout << std::setw(colspan) << names[i] << std::setw(colspan) << times[i] << std::endl; 
} 

class PerformanceClock 
{ 
private: 
    LARGE_INTEGER m_begin; 
public: 
    void Begin() 
    { 
     QueryPerformanceCounter(&m_begin); 
    } 
    double Done() 
    { 
     LARGE_INTEGER freq; 
     QueryPerformanceFrequency(&freq); 
     LARGE_INTEGER now; 
     QueryPerformanceCounter(&now); 
     return static_cast<double>(now.QuadPart - m_begin.QuadPart)/freq.QuadPart; 
    } 
}; // class PerformanceClock 

int main() 
{ 

    // -------------------- Preparation -------------------- // 

    // Out inputs 
    const char* inputs[] = { "yxu45JRZV4tNdd1QCyna", "cnpcDiZMt7meuWlChRLz", "0A5tfP2dLXIz8koq64tL", "5P9bD9NNRtNfTujr5fio", "UZSnYM58N1meWIhY8rM0", "YQijNudHgBQwn6snPRH4", "xYI8H0Do6pi5RLZRECNY", "JRfGxQ2lDAD8gZwd6tQc", "NcCp2rwV4sP9PbiIuSEg", "i2cpej69faREswPiK7nE", "YdJAbj8E6VNQzAy9oeHo", "VNo3YDlyOeUeFA9BGiXm", "tB3D0j26nx610JPOOAIi", "pscv9tApKaxw14NSVlDv", "bFTCBs5o9mg14F6F4Plo", "f7TTZiWC2mMsvEAUGalq", "gxWkNu86l886MfPHdLzq", "tqRcYTo12xwwXVuEi2d9", "3Uz1t6tOQ7NYShZpUNuV", "aD34baQ18TMod6dfJwZA", "U1fSxmx9YuY1bsllgYar", "fhyEset0jR56qor5zjr5", "VEeQNIHipq2vy141rco7", "4LDjHmvLUe13NOr4SANN", "PoOthnu2Ke27bKEyWTDv", "NPWn9J52xHOOd4G5lrXo", "1xjnMU97qRYAxSmqi8TR", "2pj4vj4kVhwX2nkEKdK7", "Q0XJrYvEB0nzzkkFYlp9", "Uzr64OADHWHVHYWJfc77", "m0SKmbXZNiezdO77O8tZ", "kjPuw6dn4J8xwpRiSKuH", "KBaziJyAIyDlmz1Vzbas", "9qk3ZAK8VvKklXETictj", "1AYnAz8yr03j8ZAZ5iei", "SbhYkDkM63FmK3j3qsCz", "OMuqIu1ZOhBqBL6N1ytH", "2vxtMD2p8FcUVGIT0DnR", "AkrdF0Iy59gE7Dp9JNfM", "stH1IAQ0sXnSDaq1HMoW", "DcMMazqQQpbMzLyELrsU", "lJSdcCnUPhRhfzfSAXQF", "0UVIPfSSXA49eUsxe08K", "wnnfBEKK3Qp473xCFrVY", "wIX3U63r6tkWkIED9Rx5", "XLQF7G8scQrtPXPlIxfC", "FAX2XBVwqKzW8JrgJv48", "deaGGIl8KtPg16C8W3MJ", "AerQR94BvVuf5Zh09L6l", "MA4xrjmVJrDGwr8NJAjE", "liNhTpfwHCULOAGqiGGP", "bimfAY9eGu6fJBg6WV1T", "2B5m95znEnZluRif3cXk", "wGRrV7CiyVC8ibUPJpGU", "TTPxXJzvwCHYDnuTS4ze", "PSgfebaPu9X6ELwQFuhD", "6BNO39hyTDCkuVEhotFe", "HUTInCGeZzaw8os8Lj59", "5BulRf0hkaMVD70EWtW0", "Udge2C4oYujCZtJsPxYf", "4zOYA7utkNX4HAiYWJw5", "vGfHy2MLBYkvzodgN5NN", "QoEGnSP3NJEFwg90XsvP", "Z9MLyLnGBYRzoqeFfGnl", "sCKTWuio4aQAYehB6HCg", "rxzz7ct5IUDy52z0Ybid", "JzaimU3EAYScyPzLxnxO", "4EupGy8hKzovI04s9k3r", "9IyD9IyOTgHGs04AphgW", "wIPaqb92cpn3rA9G3xCJ", "NZezYsWHaSRKtZmlqKss", "K9wbueWp8R88e5imzrHt", "IltUiLOPFRNgQ0jOSt6i", "mrMxaogf1on4sfRx2wvv", "RoLK6lfBBvlE0sUT7hmc", "nJuFEfmfapBMtfxhrLLc", "8oltcyHy1WrVmLNlwhXe", "Q2wniXYZEE32fF0VO9KH", "ithGCjUE8j298nVEQ9za", "oJpwIUdXj39iZ5LEI5xP", "w9gXZxxqgEYXyHkv0E1y", "dP8vwnG0EaetT76YEoKG", "9JjVSweM2bhPQ5wfXZCl", "sCGWtGhdGpEpbC3bv35E", "wf33sMLLuWFEr9mQ6chF", "4lp8prBsejxikiyzdXKA", "zTylzgjl0CT7nO8SkXkm", "Uz0mc5OjfeXS7HkvuqeT", "VIHlV5xgEkiEZhROZ6P9", "vOM2TmFVULfdUJOUg46i", "arZEAcfaQBjfrOffogxd", "w4uBjsZ3rtLFe4PccEey", "yNT0fvxWXVfoSlkVhJwS", "Je7rcoWyxdh82fJGFkNI", "XRlbaICPD9tgHS4QiCoK", "7Vtkdx5fhGM14xRj4rEU", "Q9izPLm7IdVDP64j2XQg", "vp0IJz5UlMunNPuKc1pN", "69zhS3u7fylfFivKagx0", "lr1PwSfqVqNSucWJlGfA", "3iC5lr4tMVviJ2c2kmau", "JJQdbqP2ZjsdMJCdBkFi", "SoSUhRDhOvhArYUtRhtX", "x4fL4SEmo0QiuwAjjj4k", "oI4mbLwhg1QSWVG66SGr", "U2CTAPb1OkknT9pWXBDh", "Pk6TEh0IQmjO8EQP1agb", "o7JwwAjC2LGztObMw7qD", "UcvXFYRVJGqR0lejzvX0", "UqN6wQVfkJnPHzL4WiX6", "nMVsuJNNxXDIYzxMEfvp", "MhYxQdpTV3Ohpr5RAMTx", "HJ8KmYdSqKRh9fz6zlby", "SfeDgzAUQaxiWFiuY08K", "tgJuCx1UaaHVcKo1IPlm", "X6VUsOeAsFTkco7imijI", "yVEOPiM6DOB1UYVhhdk8", "fZRbVxqQFkSr0FRifnCN", "7Izg2Uie5JJGHlG9n7AI", "K7KTsWgcrhSHTTiRSrxt", "Kw0lhrJyE2TzQ2MoqA36", "KTZKnzmPwOmpDm9RhPL0", "XddDsauu6KYBxgR7QgOh", "x577aT0lJuj0AYFAk0TW", "dGlFYstHsmmEsnyisYek", "LLc0mK0pc92AudxCDgO7", "UFCuUiloKuVDAGBdQDnY", "icuNcxGj1xNRkackFEUJ", "WmASq7nN85SlcydJYMDe", "FuCxoPVfxvp74qXVHtdE", "aMPEltF2gFFpwhllz3NS", "Fd1YBdagkYrgcVzZ993f", "P3vEWtm49IoexbAVfWjH", "dPcjFfijFPP5RBPNfAjw", "r1KxB5TgKxbZgIh7n8Kb", "gnEGgTPg0OOtIVsTjbGz", "CDzf6PXyrdXpcG9yOb9k", "nwep76VGfJVvzWrm2ci3", "lH17zVrR57AF4eM6OQQL", "rt0hvdhbYM4MZQ2MNQCA", "XjUwspBBhyXxJ3A4sZcW", "TO66uuWsDb18XJgpZxx9", "PqoTmpxTI526jV46CeD4", "wowLbTpF002PgJeV3NOA", "fVFaW9edrWmj9DagF9Zl", "2wKCKRmuUHXl25H1vzAM", "2iko2TR11skm4CjE2iuD", "hGSyJuZdvSD882TcCx7l", "0aSM7AgV5pvxYYS011Xm", "gIKHT5wi33d2dHglU3r4", "tPuRqjFsGCEQRjVsVt4n", "s1yuSwWO1sKvvD7ijGDv", "Xy2tVRxiRhLpRQ67cgBe", "dN0ZtJWX47Ry974J8grz", "4oALvEi4rsE8q4XV9ibo", "QA3fwYSPrxewIwhl5M33", "MKxUjD5VBqOCBcOSgskP", "i4SUZJ7XjJYHuT1Myd6S", "TAmdTTSwiCTyy33nNKug", "rcRjMeBQMssJZPLTX7Eo", "YWszqu7Jk5qGznZVyRkU", "zkSXYxFFX1u2TPzzekFr", "iwpWWlMTQiin1gP1B725", "dguvfNWyX1F9Kq8CUmio", "mmweJmmGCXfzkiWvrIAf", "0jqq0zp3nI2w3iIG01ev", "I4bVHz3KajVm6f6QPAXS", "QrQtMNo3pGGZjQtYJvQm", "IZyZbFhK1ou9Vs6hU5XT", "JKjlvweHcnxdFtUVsCNu", "lGMqzOFQrq4vvRDujiCW", "zjO04wpUHtUn67bETAdg", "n7ysAW4ml7S8BhwE9ubO", "IjRGqKzqLimHeaTyffcO", "QL25AdNDTwuze9JWNjkD", "q948zpLcMQX0ImQyVaiO", "dUgKdtOzKiiLqONbOkIp", "e4X4df2DzjFzv2Qk4OXw", "d2L8oJgGpIs0qkycSMxN", "kqIYJQDnrGo22j1jA7cF", "Y7gfGAsXWmRNLqSJr0gy", "tZdaBU23aVFajefzyLOF", "qZvD1NMV1uwUD0hgawmw", "sdPIN2HTZE6t2b9Djz7s", "upAwEn0o4KSNdahAC4DW", "Sahw60orUZ8jfNg3t5tC", "otAVTH99oIm0pmLjpxuq", "5s9zcaoMQPJaxYZIizLr", "0INz5juLXNS1qz0S5ZBD", "sdfeGOkVyogYIGlZuKQR", "mrDeLJd2vhobT5pkmHUg", "X4fz8JUHXym1ReuSIfl7", "qW60yaRPSvxnEe93hxsL", "exmEIAOI9PRZFX2Q2ahQ", "PKgWxvU1QFhyrnBkzoon", "OCZBJ6WSnfHz5JN8hrSg", "BPRi6d3TmbAdC2kASDGv", "jCwBs3QNbLLL1BS8ZsWY", "VHmUgSk71PzHpsaVEQaP", "SSqA6435huQqguErI5Om", "j8EWadtp9N09Kg3TionW", "paUS1pfKLqvvRdCatNEA", "U4m0QB6bhzLwcJw8PWUd", "FzMv6nkQOZZ08rbnZzfQ", "JDX4rjAgRIj9484NnN0B", "t33jIgbYP7uK7aU4uPqf", "Jim3d7AbanwSA4dsgYTf", "s79GzWjCnNzCqMP02uXR", "pwV3gzOWRPInyIRab3hl", "KSkC3a1NysnHXmg3hz00", "48RohG5tE4mD1FW6gDxO", "edySUYmPSAWb2SNABx3i", "ZewnjFRsNF2P7FsXFG1J", "P3MKpt0pjsWjCxmzFH1k", "OM9ZkaXWStkeD2D44DQr", "5uLXwJks9bhxGbkbx3PQ", "uwyllRDSx3Rdk4tkE2XK", "CebMT43q8FUOZwC9I3hD", "OP99Uiiau2L86Jb1HLDt", "mNStmnQK57wNhY1xgiWr", "bkqIbxcsGn7a3oUsDUz9", "8B6Nh2fr32FDxa5Zk8EO", "WmoIHtvZBVbJznqn6MDY", "WAWNAksIY9TloCHPMdDp", "h0X2FSzQBGfg858Zr5lI", "U4guPLRmEiWpmwkVfXsk", "07PY0E8w0ynsJJJG6dTT", "1EwuMIgLzZ4QOLSz9KKK", "ZbgGBA5PkbWOAgKa6U3U", "2YP3z0RaIinIJHndQvJ9", "VuTVO86yXm26C1ZC42cv", "czszyFqLJelsDtkB1wGm", "JBSSs9Gq2z1ho5vxKa7b", "WxzstpP8LNFek2sNVO7I", "SdR4zJAFYIUC6Ox7F5Ao", "bqeQdAHhSqq9CMH466EU", "3osfIgWhT0YYWHLuFp6m", "OsYQp5s01CyQsAxxyJ5z", "QmdGehSItOI9ytDJx2tn", "RS7NTVDlt0ae7mG2fNu2", "b70uAiLvD8lWmD4LFhoq", "qYA1LVo2Zk9Yka5qJ69M", "2QteJBZyvfLu4QnwuXZp", "spE7TmutGb9sF3l1WdzK", "wx7fwsIzuPHCPoJMm8Zi", "UTXxyVIFT1MP3piFOj9E", "Sv6X1tpRqaIFKVvOjpy0", "zkCCginO8RH1IQ5gxP9n", "lpzHz0JOAKDEbNzWOLHi", "ga9ThbxxkMjZBISnpM4Z", "XLj9Dc3gI3zspCQUqLAy", "I4B6seBrJYopMfIJPRg8", "y7oFbP2hnfLIx7Loufzb", "qwENxA8OA4xGHB2Y7T7z", "TCJca2HMVXLoBLLTQaMm", "Nm0YLJ6zdfj5EkdYReJR", "04rQlakEagJimcZi0xZF", "5AotlztHKO5FCed44T51", "IIhf1YB3yq0MfKBMDiNJ", "gI8dJJVL8oysEkUROyFF", "ls3nHBIMOdtdd68wSJ8B", "sXt2Pgcq5GLpPRXPDEfX", "RRGLCAXtrjBMtj1UoWWP", "N6GGDjSpvxPrtPFtiBuG", "KM7aQq96bzzokQSkXy2L", "THGWpDuXfiq7ydRtYzGN", "4EDerDQt1cKbzO16436h", "76rXLODN8Ik5KjPKipo2", "k3HKxP0Ek5jSviq8F0Z9", "Tt6ax6fUn2ifsfBoLuZJ", "vuChGzc9hlKnerW0FTS7", "osXjEnlYYN2uLShpDgPa", "kyRWc0KCtFBLtFXHTYbG", "ArJSG0mJY2gUHSJ8MkXs", "nQea6CLRuer8f6clqd3T", "7WIwE0fUplMqQ8HDJyl9", "JoHJzGl8hLk1b2yiea3b", "8AW3Ip8YLf1wdRZkFr0p", "EwyYE9FdzBppUhpmEQkY", "ULpmmACM04oxA89Of4vR", "1ETapZcpVUCMkKY0AAcx", "9u8SaUc6mUethl73dyEN", "SI2EJys3uWiAf93l6G3X", "dc5sWttEbc0ixIdw1YqV", "QV3FRwytDAA3TCsy4jiQ", "KO89nRNbn1sb9QqAnalZ", "fJtl4TSxF3nkStQSZjKV", "W3Zv9VIIfVVDfHYB1MZJ", "Sru5BIe1FBt55353fZBR", "8hbYFsKp0a69zFf8XfME", "SgAxktG5TWZgdT75qlnk", "IlB4M3cfYRsEacB5mxKQ", "v2eSPv7LNCZpJvaIxhNq", "qcfHQFRTaf8hFUC1uGeM", "m309qZaNJJdKVbkqIh0p", "LPRXLy1JxXAgjOpD4SOh", "V3JDPm9ZT7xEF5TGjmQ5", "pm8asJdQlQYP3GAQGg7B", "RNg45uLlAynFdQEiAd1z", "MsBlcLHaoRvarn2Hg9cv", "sptoqa8m9MQoo0Qdv6W5", "LQBNbdGTPe8wd1RnOWL3", "AzzwJ2xV8hy3CZQrwaDJ", "ZcIsPuJn76TKGmTW2uc5", "412GgdvECB1N7g2Q136N", "XLwiWSaE956lBioeusMg", "C8Ark7jlgdKLbw79v1Ga", "Rpgw0jCzvOZywBS1R2cX", "nhXbq1ZmUSnUbBOWmCss", "0EngfF85ZVCv42Gd8LiZ", "JmCOkPve5IWSe3AaN7HM", "iHMI9zUHEucjS64Zq65T", "iRZQmbtj7mIRxYoNXNCW", "87S4t3SekcuxRFLm4Vj8", "pq0iCznEdH2yqryur0ut", "MZ8JUEXA4NvSFJVvagSo", "wYh7K2VqClA0NT2YNz0x", "lEXFwt1QvyLorSrSDxtJ", "Jo8ZBFuR4AdGAlSPrEra", "5OFujFQGmkp7yFpuetg3", "AdBtAYEvesYLPEBQeYve", "yDh3QJ34463eemMIKuI6", "JpIOLAZKKVRw4W83z45f", "0pNXAVcaEnx1xR5MuCB5", "vCj8Lf24T7KfnqDPjLw3", "YOLVtf9CAGxusaJ41VNZ", "82Y5ryW3Li729CEchqti", "kuwMAYq5tFWiSNkSEUGj", "zPXdbe0Ce8iCnNymn6RS", "r6oIYnbLMUvgK5fAhUYX", "r7zlqTEbleJEIQlwTRvx", "P7qHubtylXZL806S2i7z", "FOwjwJ6XHA4YPmeosKCh", "3XNFLqoIJCNXeLT1zcYf", "LimUsGLXzPVwX9wWXMmG", "GPVnnjTikZepjomFMM3G", "ppXlJWH4qbARPsCzrVfP", "bgaHljMhHsBfCN233pGy", "71O4ZgWSIF6pJTHqQCAv", "hgfbHneNpEkaoTjEGi35", "BP29PdJMnGOP8OW8gLyB", "VfrsHKOpMT2cylXUZyNZ", "WZDrZ9SFsEnAWi9EDv2c", "VpeRIGudekAM39Q8JoVy", "oGr06UoFSyt7B7fdmDxE", "rZ21EQAMR2TO726ORH4X", "7GSsIES5eHzhQMfCFVlU", "Ne5DGZdduwtJjeWxoF9r", "SZJ3eKgHGQgXz6mwWQJa", "5tc8iVyeUu83ZX8VGPGa", "1we37HKSas1jzOK3oJ5a", "bAzWv0LXBBFtlQazyXfE", "dKpMfN8bsa2U45RYkSIW", "kyRvCRKKLeB8tO20rB9I", "NV8MBc1pcI71FQYHlWnq", "q2hk3QhTC9lXU85ozlYd", "AhKuywGqS75a3U9PnBaQ", "pfaqxamqrbQFEKyW57fY", "99wBwml3fglePRgmu7ra", "AQAQDqi6L3coCDdDZns1", "pzz5npWyJ6VQPxo74Cke", "GWciE16vRqm8zrHA2NH5", "0kLpyuzVksayvw1fIbgl", "jJb7R3CvU9qHSHEkZhBA", "0I1I7DTYHtzFkiK2vj7B", "4OPP86obIIhBtpdkZRjV", "53D7grILbzHEYjH70Z7g", "n8jUOaamiQksK1Ol5ugK", "XvTe9iN83a8AF7DqFuxM", "yTnjXNaRWHYTQLuomwY3", "6BnEAXXeLFHCc9V33wXx", "E8Ii1r0t9KmUpSO66TKp", "Xk8jCTYopGN3UQX3fQFL", "4dlTkv8BD6tJG98eewke", "aigrOBHoaY0PFEiUm1N5", "osSxqwTcADgvxdMpaKun", "gYHjw5dKudsqKpNROs5U", "ZEObDNpngRApsxWQUqYd", "DC2OG9A2gorJvMAhMqDd", "qYS7T9XKxGmCrLeWndMy", "k9zdcJpkeV7lNpDqu0IC", "LNbnfk5MwyYqHYKdzJG4", "rlZCUvoY0tX7G6XNpKJx", "ZijRJkRmIpni8KDi8bfH", "2CEw7UMYw4IxKsJec6ob", "P3wa9NXkNceWuR1QvFik", "TbK8qSIydMH2ZjN6H2ix", "N5xXx7t9R5aTG0rHqCoA", "IFAjLEo7FuvDCZ3Gz0WR", "f8VWdjXfCXrb9NNkZfX4", "ODNmQDPJ8YbpHrqATVpy", "MIeomMUJskj6pm1hWII9", "vd7FVv3Yq0eaanek6OqM", "gXAFmO9JU3I0kTmRg0RD", "lpYJpvX51YNCYwn9Smgm", "ZIZQtPl8b7pl9cRQDpLg", "6hRbFMiQILcHwfaIWKVH", "xRMJ6qyR7vTCZac8HA7x", "gVc8ZOawXNXBrzUfFuNx", "AHYMYtupBun7guGcGejk", "qB7nzqIm8bSIZzrK2DQc", "rMdCVKrMqLOhInvlQ3eb", "jceVpW9Yv40Mxhue4KiT", "EF35hrtvfaRoEto0SMXT", "Fr9U1rpOOpekZw8GYUbX", "cPiHqe3n1hzGImsptJxB", "cQs2Iit2w5SBlZFd489V", "1Xtoozu8YUB5SAWux8gN", "LTByKhkhNsoxjI5Xc9Ar", "L0dtCYu4IxH5Tx9yp300", "U7Plnx2BfU0ZLT06DVjc", "XL3cL6ycniVo9FVGGmOC", "oldWUOfn24r7wmzlOamz", "2bAxMYiU0DifA8vOp6zm", "ldYJxVP1liqZaBtGr7pv", "khkPHtoOrhqbJim6P7hf", "QAtcZY93vIUr6G7DQ79D", "CtIXVqE81TLHsLajFuKZ", "MtI3raq6Idwwf3O2Bez2", "8VyANkZDN3CUXSib22fB", "iveiownGGZArYd6OMA68", "NbJROsiZikke3jnsiG50", "0tsaeEt6TsMTBhyD0vHk", "XYpNa6xNi3knrKIGoIJ7", "L9Uqgmerw6sAlCmT7TY9", "nzJhgYAEcHqFSzaIy9ZN", "bohzQ8Xz7tCl4uujGj4e", "zl79sgjTnmFxtrgMOrTp", "Mbor4W3HaMgJTRbyqg3l", "GJJswSQacWn0XoD8qFBK", "1J1Hi6SzromDpPpNuFko", "FyyvJWEk9H7nnUGw41zL", "bYuEX8u223s9HVFa8DoQ", "CN0grWgSZH8QK1IEfPwz", "2dcfAvjZS74upCBEs0pJ", "9SOyYA1qf71DQBbbF44R", "DSZPICvixvRbFcE3GZ71", "5ePbE2qCMg3PlhFjvdcg", "Ee1Cmlh7Nw5lQe5ph44T", "x6HrkJBvkPzOxGLfzudt", "HQhBRPa7A0qIoGAB6HHp", "y2EV7W4n6uUwTCr644OB", "iuoLYFYMxl0jumIm7nlD", "pPnvUEdVnwPM5FnMQWIX", "y54cO4vkHpNMqsNRPq44", "eSOP9svhDeKvwlo7zZr0", "cvxRkDvD86cARbS5C9QD", "bHQ0jzP8yYsHqa6cePm9", "qQ3ExNc4Zg5MlWRrWHwI", "5tv0MCv0y6GU2DczrfrP", "l18w5yXH92Tuo4PjpcA5", "CjmsIFwzyJbYzk4Z3cRC", "bA6rZYeQDeC96Dw0snMD", "B1NKqfzOtCovciSQTs2D", "eCzLXBLTvv08ubXDjauH", "m5tx9YJ3CCvgGGpd2F3d", "IZ1Tq2gYgRjYIX3rkGgU", "XgUNhykvIJPFTh07W4xV", "gRkMoVoJbwrBAbCCYtFu", "MEY1mjGeGLFKrimnnIhi", "qlhv8fh4zp0neZIMz5TN", "f1o74eIyWp4j2M49PMdY", "Zy6V98O9sZ10TPuAL1BN", "q6hVlJcPyw7jcqTkwIjB", "X58lDP8cc0AaNtOTPdWG", "EsaklDto1n9KW23y5Rlo", "owi5TngTQK1Yx4SDX6cU", "8q4aatZrm3DxaF8MZqaH", "qHvQxvr52bxbn2Lsz894", "5t7ZhLjwyD4aEbmnbZ8U", "Q4IXLuJ0m6R2LyDIEN1M", "3qlSpGC75FJf35tsESjs", "wj0TVvNPNCFIqdSPzAPW", "fknkisTHnOkouphJ34wi", "aDLCLpGsidQpQMe2buHd", "9bF9XvgkmSk2QaH6b95M", "VO4EuELUxseX8Hjsxe2k", "U22yTKWTUN0pNiQxVSgM", "2hKQqNzCC9qeBWpdFJ4p", "UzCHLW5Uif2ESwvWtMTd", "aeiKCJHqoy5B9UmTSjRo", "VPIaKy589JQSJMOeoLiP", "amFmEUARPm1DjQwXefEg", "M1MTKIsulq4oeDGBkFYy", "hbjLnR2Qx8ZSTjnrsFci", "QEDiz38W4pIBXVRab21U", "lNYCJVRcnBtrxJTsSW8z", "lZKlnovVYV8Rdg9iSpzp", "ZmpuelXNs3MlZU6GcqxX", "uWcwVLBXWWqrkSyAGexd", "H91lUOJFN1AJtyQJ2yrY", "qUOpBXvkdKZe8OsRovc8", "VreNCHBV3pp12fk8Ax6I", "tlgHjVlArf2RagO3jBPZ", "kUjymJiFXv52PgpDcY9z", "5EcD56ZTtObcOq5BxZJt", "wpuNhRrKaUj5yd0QbnHZ", "AIYwGTo9Yt19mLaTkzNI", "zpaJZRLZiMHmhOQ6Jy0j", "6On0n4mUeK4Ics8Q725j", "X560iPqFqijgxv7FXiUn", "HyljDZCwDOKb71iHV2Tm", "kEzYhJ0k8KASaMamU3I4", "hfIuWLaeZtD6hUy8umMw", "87wS1xCo3wZlxPyCO1fj", "5Q6jJZvKQgaI5JgEZLjX", "vmGReyRElWHslAjFGPsp", "kSn4oUIWAfSev6MeaNym", "5ltdUwNsFaV6gHoxgCMI", "zFzljs3uCXXIOBlXTFjm", "r0cGBofX7AWMyQ80ciyC", "J0xgBJOhM1ApHj9ccP8w" }; 

    // Our candidates 
    std::set<std::string> my_set(inputs, inputs + _countof(inputs)); 
    std::unordered_set<std::string> my_unordered_set(inputs, inputs + _countof(inputs)); 
    std::vector<std::string> my_sorted_vector(inputs, inputs + _countof(inputs)); 
    std::sort(my_sorted_vector.begin(),my_sorted_vector.end()); 

    // Time Utility 
    PerformanceClock clock; 

    // Output Formatting 
    std::cout.precision(std::numeric_limits<double>::max_digits10); 
    std::cout.setf(std::ios::fixed); 
    const char* names[] = { "set", "unordered_set", "sorted vector" }; 
    double times[] = {0,0,0}; 


    // -------------------- Binary/Hash Search -------------------- // 
    PrintSep("Binary/Hash Search"); 
    // Find all from set 
    clock.Begin(); 
    for(const char* s : inputs) 
     my_set.find(s); 
    times[0] = clock.Done(); 

    // Find all from unordered_set 
    clock.Begin(); 
    for(const char* s : inputs) 
     my_unordered_set.find(s); 
    times[1] = clock.Done(); 

    // Find all from sorted vector 
    clock.Begin(); 
    for(const char* s : inputs) 
     std::lower_bound(my_sorted_vector.begin(),my_sorted_vector.end(), s); 
    times[2] = clock.Done(); 

    PrintTable(names,times,3); 

    // -------------------- Linear Search -------------------- // 
    PrintSep("Linear Search"); 
    // Find all from set 
    clock.Begin(); 
    for(const char* s : inputs) 
     std::find(my_set.begin(),my_set.end(),s); 
    times[0] = clock.Done(); 

    // Find all from unordered_set 
    clock.Begin(); 
    for(const char* s : inputs) 
     std::find(my_unordered_set.begin(), my_unordered_set.end(), s); 
    times[1] = clock.Done(); 

    // Find all from sorted vector 
    clock.Begin(); 
    for(const char* s : inputs) 
     std::find(my_sorted_vector.begin(),my_sorted_vector.end(), s); 
    times[2] = clock.Done(); 

    PrintTable(names,times,3); 

    return 0; 
} // int main() 

Вопросы:

• Do заявления звучит правильно?

• Действительно ли это тестирование? повлияет ли тест на настройку компилятора? (в визуальной студии) Будет ли влияние на тестирование повлиять на переупорядочение компилятора, оптимизацию инструкций?

• Какие еще тестовые примеры необходимо учитывать, кроме бинарного поиска и линейного поиска?

Answer 1

Условные звуки звучат правильно?

• Вектор является лучшим в линейном поиске
• Unordered_set лучше при поиске из-за хэширования

Да,/лучше использовать кэш-вектор лучших в линейном поиске из-за непрерывного использования памяти, меньше преследование. Это также лучше всего подходит для двоичных и интерполяционных (также называемых экстраполяцией) поиска по этим причинам плюс поддержка быстрого доступа к произвольному доступу (то есть [n]), но получение/хранение элементов, отсортированных заранее, может быть более дорогостоящим, чем со многими другими контейнерами.

unordered_set требует хэширования ключей, ключ проверки значение равенства, и может иметь неприятный поведение наихудшего для бедных хэш-функций или злонамеренно сконструированных наборов данных, но в целом - и более того, число элементов растет - это является лучше при поиске определенного значения, чем vector.

Действительно ли это тестирование?

Нет. С этим связано множество проблем ...например, QueryPerformanceCounter не является надежным на большинстве ПК с Windows, если вы не привяжете процесс к определенному ядру, он не уменьшает время, в течение которого ваш процесс приостанавливается, пока выполняется другой код (если вы выбрали неправильное ядро, чтобы привязать себя к системному ведению домашнего хозяйства , драйверы, обработчики прерываний, а также другие процессы). Кроме того, могут быть эффекты утечки кеша, поэтому рекомендуется повторять тесты в разных заказах, прежде чем доверять результатам. Результаты также могут отражать информацию о конкретных типах ключей, размерах контейнеров и т. Д., Которые делают результаты неприменимыми к другим типам данных/наборам.

На тест повлияет установка компилятора?

Конечно.

Какие еще тестовые примеры необходимо учитывать, кроме бинарного поиска и линейного поиска?

Сортированные векторы позволяют выполнять поиск по интерполяциям, что может быть очень полезно быстрее (например, 2-3 раза). Время вставки, время стирания и т. Д. Может быть или не быть релевантным в зависимости от ваших потребностей. Безопасность резьбы. Типы данных и хеш-функции (в том числе, нужна ли вам устойчивость к вредоносным клавишам). Все зависит от совокупности действий вашей программы с данными.

Answer 2

Во-первых, петли в коде не имеют побочных эффектов, поэтому компилятор позволил оптимизировать их полностью, хотя это не произошло для меня на VS2013U3. Вы должны добавить некоторые побочные эффекты, которые не сильно влияет на производительность, например, так:

size_t len = 0; 
clock.Begin(); 
for (const char* s : inputs) 
    len += my_set.find(s)->length(); 
times[0] = clock.Done(); 
std::cout << len << std::endl; 

Во-вторых, набор данных используется слишком мало, поэтому измерения могут быть неточными. Вы должны либо сделать набор данных больше, либо повторить поиск больше раз (и, возможно, вы захотите сделать так, потому что эффект от этих действий отличается).