set vs unordered_set vs sorted vector

Question

I started to wonder what is the exact performance difference between set/unordered_set/sorted vector.

Thus, the testing code has been written to compare their process time, so that I can prove following statements that I believe: - Vector is the best at linear search - Unordered_set is best at search because of hashing

#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()

Questions:

• Do statements sounds right?

• Is this testing valid? will the test be affected by compiler setting?(under visual studio) Will the testing be affected by compiler reordering, optimizing instructions?

• What other test cases needed to be considered other than binary search and linear search?

Answer 1

First, the loops in your code have no side effects, so the compiler is allowed to optimize them out completely, though it didn't happen for me on VS2013U3. You should add some side effect which doesn't affect performance much, for example like this:

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;

Second, the dataset used is too little, so the measurements can be inaccurate. You should either make dataset bigger or repeat the search more times (and you may probably want to do both because the effect of these actions is different).

Answer 2

Do statements sounds right?

• Vector is the best at linear search
• Unordered_set is best at search because of hashing

Yes, vector's best at linear search due to contiguous memory usage / better cache utilisation, less pointer chasing. It's also best at binary and interpolation (also called extrapolation) searching for those reasons plus support for having the fastest possible random access (i.e. [n]), but getting/keeping the elements sorted beforehand can be more expensive than with many other containers.

unordered_set requires hashing keys, key value equality checks, and can have nasty worst-case behaviour for poor hash functions or maliciously engineered data sets, but in general - and increasingly so as the number of elements grows - it is better at searching for a specific value than a vector.

Is this testing valid?

No. There are lots of issues with it... for example, QueryPerformanceCounter isn't reliable on most Windows PCs unless you bind the process to a specific core, it doesn't discount time your process is suspended while other code runs (if you pick the wrong core to pin yourself to - system housekeeping, drivers, interrupt handlers as well as other processes). Further, there can be cache warming effects so it's a good idea to repeat benchmarks in different orders before trusting the results. Results can also reflect things about the specific key types, container sizes etc. that make the results inapplicable to other data types/sets.

will the test be affected by compiler setting?(under visual studio) Will the testing be affected by compiler reordering, optimizing instructions?

Of course.

What other test cases needed to be considered other than binary search and linear search?

Sorted vectors allow interpolation searches, which can very occasionally be usefully faster (e.g. 2-3x). Insertion times, erase times etc. may or may not be relevant depending on your needs. Thread safety. Data types and hash functions (including whether you need resistance to maliciously collision prone keys). All depends on the totality of what your program's doing with the data.