我开始想知道 set/unordered_set/sorted vector 之间的确切性能差异是什么。
因此，已经编写了测试代码来比较它们的处理时间，以便我可以证明以下我认为的陈述: - 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()
问题:
陈述听起来正确吗？
这个测试有效吗？测试会受到编译器设置的影响吗？(在visual studio下)测试会受到编译器重新排序，优化指令的影响吗？
除了二分搜索和线性搜索之外，还需要考虑哪些测试用例？
最佳答案
Do statements sounds right?
- Vector is the best at linear search
- Unordered_set is best at search because of hashing
是的，由于连续内存使用/更好的缓存利用，更少的指针追逐， vector 在线性搜索方面表现最好。它也最擅长二进制和插值(也称为外推)搜索这些原因以及支持尽可能快的随机访问(即 [n])，但预先获取/保持元素排序可能更多比许多其他容器贵。
unordered_set 需要散列键、键值相等性检查，并且对于糟糕的散列函数或恶意设计的数据集可能具有令人讨厌的最坏情况行为，但总的来说 - 并且随着元素数量的增加而越来越多增长 - 它比 vector 更擅长搜索特定值。
Is this testing valid?
没有。它有很多问题...例如，QueryPerformanceCounter 在大多数 Windows PC 上不可靠，除非您将进程绑定(bind)到特定的核心，它不会打折您的进程暂停的时间其他代码运行(如果您选择了错误的核心来固定自己 - 系统管理、驱动程序、中断处理程序以及其他进程)。此外，可能存在缓存预热效应，因此最好在信任结果之前以不同的顺序重复基准测试。结果还可以反射(reflect)有关特定键类型、容器大小等的信息，这些信息使结果不适用于其他数据类型/集。
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?
排序的 vector 允许插值搜索，这有时会非常有用地更快(例如 2-3 倍)。插入时间、删除时间等可能相关也可能不相关，具体取决于您的需要。线程安全。数据类型和散列函数(包括您是否需要抵抗容易发生恶意冲突的 key )。一切都取决于您的程序对数据所做的总体操作。
关于c++ - set vs unordered_set vs 排序 vector ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26522185/