Time Lime Exceeded or TLE can be a significant cause of frustration for competitive coders. If you are getting one, you probably need to change your approach, but if you are stuck in a coding challenge and can’t think of any other method to the problem, you can try using these techniques to get around those sneaky test cases.

超出时间限制或TLE可能是导致竞争性编码人员感到沮丧的重要原因。 如果您正在尝试一种方法，则可能需要更改方法，但是如果您遇到了编码难题，并且无法想到解决问题的任何其他方法，则可以尝试使用这些技术来解决那些狡猾的测试用例。

使您的I / O最快 (Make your I/O fast(est))

C++ developers usually get accustomed to using std::cin and std::cout for standard I/O operations, but they aren’t the fastest ones out there. If you are feeling lazy to change your code, you can just add the statements given below and enjoy the speed boost.

C ++开发人员通常习惯于将std :: cin和std :: cout用于标准的I / O操作，但并不是最快的。 如果您懒于更改代码，则只需添加下面给出的语句即可享受速度的提升。

The first statement disables the sync between C and C++ style I/O, so this may cause unknown errors if you combine them. For competitive coding, it’s usually not required to use both so you can use it without any worries.

第一条语句禁用C和C ++样式I / O之间的同步，因此，如果将它们组合在一起，可能会导致未知错误。 对于竞争性编码，通常不需要同时使用两者，因此您可以毫无后顾之忧地使用它。

The second statement unties std::cin with std::cout. Whenever one of the streams is used, the other is flushed, but when you untie them, they no longer flush each other, which results in better performance. Of course, you can always use your old C friends, scanf, and printf. They are faster than std::cin and std::cout by about three times, but when compared to unsynchronized std::cin and std::cout they don’t give much of a performance boost.

第二条语句将std :: cin与std :: cout结合在一起。 每当使用其中一个流时，都会刷新另一个流，但是当您解开它们时，它们将不再彼此刷新，这将导致更好的性能。 当然，您始终可以使用旧的C朋友， scanf和printf 。 它们比std :: cin和std :: cout快大约三倍，但是与不同步的std :: cin和std :: cout相比，它们的性能提升不多。

Want it to be even more fast? Are you taking integer input? Oh, then you are in luck! Just copy this function, and you can take integer inputs in the fastest, thread-safe way.

希望它更快？ 您要输入整数吗？ 哦，那你真幸运！ 只需复制此函数，即可以最快的线程安全方式获取整数输入。

The function given above reads each character and converts them into an integer. This method is free from a lot of system calls that scanf has to make, like deducing the type of input.

上面给出的函数读取每个字符并将其转换为整数。 此方法免除了scanf必须进行的许多系统调用，例如推断输入类型。

You must be wondering why I wrote “the fastest, thread-safe way.” Well, because there is a faster way, but that makes it thread-unsafe. Want to use it? Replace getchar() with getchar_unlocked() and experience the beast. In competitive programming environments, you don’t need to worry about being thread-safe unless you are doing concurrency related tasks, so go ahead with it!

您一定想知道为什么我写了“最快，线程安全的方法”。 好吧，因为有一种更快的方法，但是这使它成为线程不安全的。 要使用吗？ 用getchar_unlocked()替换getchar()并体验野兽。 在竞争性编程环境中，除非您正在执行与并发相关的任务，否则不必担心线程安全，因此请继续！

How do you believe what I say without any proof? Well, here it is. The different methods were benchmarked, and the results are presented below. If you want to look at the code used in the benchmark, I have uploaded it to a GitHub repository, which you can find here.

没有任何证据，您如何相信我所说的话？ 好吧，这是。 对不同的方法进行了基准测试，结果在下面给出。 如果您想查看基准测试中使用的代码，我已将其上载到GitHub存储库，可以在此处找到。

更快的向量 (Faster Vectors)

While vectors are fantastic because of their expandability, but the same attribute makes them slow too. std::vector is implemented as a dynamic array, which means that each time it needs to increase the size of the array, it creates another array double the size and then copy the elements from the previous array. If you know the size of the vector before you add items, reserving the space eliminates the overhead required to copy the elements because it creates an array at least as big as the reserved size.

尽管向量由于其可扩展性而非常出色，但是相同的属性也使它们变慢。 std :: vector实现为动态数组，这意味着每次需要增加数组的大小时，它都会创建另一个数组，其大小增加一倍，然后从上一个数组中复制元素。 如果在添加项目之前知道向量的大小，则保留空间可消除复制元素所需的开销，因为它创建的数组至少与保留的大小一样大。

Where max is the number of elements you are going to store in the vector.

其中max是要存储在向量中的元素数。

Adding a reserve makes your code about 1.2x faster.

添加一个保留使您的代码快约1.2倍。

Again C style arrays or std::array is faster than using a vector any day, but its size has to be known at compile-time and thus isn’t always feasible to use. So vectors are your best bet, and it’s better to reserve the space beforehand.

同样，C样式数组或std :: array每天都比使用向量更快，但是必须在编译时知道其大小，因此使用起来并不总是可行的。 因此，向量是最好的选择，最好事先预留空间。

Another surprising thing about std::vector is the at() function. It seems to do the same thing as subscript operator [] but when the performance is measured it is actually 3.1 times slower.

关于std :: vector的另一个令人惊讶的事情是at()函数。 它似乎和下标运算符[]做同样的事情，但是当测量性能时，它实际上慢了3.1倍。

That can do a lot of damage to the time taken by your program. The reason being is that the at operator has builtin checks for out of range values that the subscript operator doesn’t, so if you give a value that is out of range it might give you a segmentation fault or cause unknown errors without telling you what has gone wrong while at will throw an exception.

这可能会严重破坏程序所花费的时间。 原因是at运算符已内置检查下标运算符没有的超出范围的值，因此，如果您给出的值超出范围，则可能会给您带来细分错误或导致未知错误而不告诉您什么在出错时会抛出异常。

One final thing that you should know about std::vector is that you should never copy an std::vector to another manually using a loop and push_back(), rather you should use assignment operator =. The difference in speed is huge as apparent by the chart below.

关于std :: vector您应该了解的最后一件事是，永远不要使用循环和push_back()手动将std :: vector复制到另一个对象，而应该使用赋值运算符= 。 如下表所示，速度差异巨大。

This difference in performance is caused because when you are doing assignment it knows the size of the vector it is copying, and needs to call the memory manager only once to create the assigned vector’s space and copy all the elements unlike the push_back() operation which makes a call to the manager for every element.

造成这种性能差异的原因是，在执行分配时，它知道要复制的向量的大小，并且只需要调用一次内存管理器即可创建分配的向量的空间并复制所有元素，这与push_back()操作不同。呼叫每个要素的经理。

不只是添加，附加 (Don’t just add, append)

The fastest way to work with strings in C++ would be to use C style strings, i.e. character arrays, equivalent performance to character arrays, but one mistake programmers frequently make is to use the + operator to append to a string. The reason it is not suitable to use is that it creates another character array of the total size of both the operand strings and copies the first one to the array while concatenating the other to the newly created array. What you should do instead is use the append() function, or it’s equivalent += operator:

在C ++中使用字符串的最快方法是使用C样式字符串，即字符数组，与字符数组具有同等的性能，但是程序员经常犯的一个错误是使用+运算符附加到字符串上。 不适合使用的原因是，它创建了两个操作数字符串总大小的另一个字符数组，并将第一个字符数组复制到该数组，同时将另一个字符串连接到新创建的数组。 相反，您应该使用append()函数，或者等效的+ =运算符：

s.append("appended string");

OR

要么

s += "appended string";

Using the += operator instead of + operator is better for any class that supports it. This helps in reducing the time taken and memory to create a new object and copy the first and then add the second object to it.

对于支持它的所有类，使用+ =运算符代替+运算符更好。 这有助于减少创建新对象并复制第一个对象然后向其添加第二个对象所花费的时间和内存。

Also, when using std::string or any other class, it’s best to initialize it using the constructor than using the assignment operator.

另外，使用std :: string或任何其他类时，最好使用构造函数进行初始化，而不是使用赋值运算符进行初始化。

您不需要std :: list (You don’t need std::list)

If you don’t know about std::list, we are done here, but if you do and you are thinking about using it, then think again. std::list is a doubly-linked list, so the advantage it gives over std::vector is that it can remove and insert at any position in constant time. That can seem great when you need it, but vectors can be cached by the processor so sequential access is faster than when using std::list.

如果您不了解std :: list ，我们已经在这里完成了，但是如果您知道并且正在考虑使用它，请再考虑一下。 std :: list是一个双向链接的列表，因此它比std :: vector更具优势，因为它可以在恒定时间内删除和插入任何位置。 当您需要时，这似乎很棒，但是向量可以由处理器缓存，因此顺序访问比使用std :: list时要快。

If you have to remove several elements from the middle of a vector, you can use erase_if(). erase_if() was introduced in C++ 20, but you can combine remove_if() and erase() together to create your custom erase_if() for previous versions of C++.

如果必须从向量的中间删除几个元素，则可以使用delete_if() 。 erase_if()在C ++ 20引入的，但你可以结合的remove_if()和删除()共同打造的C ++以前的版本中您的自定义erase_if()。

v.erase(std::remove_if(v.begin(), v.end(), predicate), v.end());

You might see there is a variable called predicate. The predicate is a function that takes in an element from the vector and returns a bool. Typically, each time you erase an item from a vector, the ones after it are shifted forward, but if you use an erase_if() construct, the shifting is done after all the elements have been deleted, so it is great for removing multiple elements. An example predicate is given below.

您可能会看到一个名为谓词的变量。 谓词是从向量中获取元素并返回布尔值的函数。 通常，每次从向量中删除一个项目时，其后的对象都会向前移动，但是如果使用了asel_if()构造，则在删除所有元素之后才进行移动，因此对于删除多个元素非常有用 。 下面给出了一个示例谓词。

bool is_zero(int i)
{
  return i == 0;
}

If you use the above function in the erase_if() expression:

如果在delete_if()表达式中使用上述函数：

v.erase(std::remove_if(v.begin(), v.end(), is_zero), v.end());

It will remove all the zeros from the vector v.

它将从向量v中删除所有零。

If you want to see a comprehensive benchmark between std::vector and std::list you can take a look at this beautiful post by Baptiste Wicht here. After reading the post, you might have a question in mind, “If std::list is worse than using std::vector, then why is it even there in the standard library?” It’s because there are a few places where lists are better, i.e., when the elements being stored in the list are huge and not a lot of them can be fit in the cache, lists can dominate over vectors.

如果要查看std :: vector和std :: list之间的综合基准，可以在此处查看 Baptiste Wicht的这篇精美文章。 阅读该文章后，您可能会想到一个问题：“如果std :: list比使用std :: vector更糟糕，那么为什么即使在标准库中也是如此？” 这是因为在某些地方列表会更好，例如，当存储在列表中的元素很大且缓存中无法容纳很多元素时，列表可能会优先于向量。

结识unordered_map (Befriend unordered_map)

std::map is maintained as a binary search tree, and the main advantage of using map over unordered_map is that it sorts the elements according to the key. One other benefit of using std::map over std::unordered_map is that it supports pairs out of the box. However, the difference between O(log n) and O(1) can be the difference between a TLE and an AC solution. So let’s look at how you can create your hash function for a pair of integers.

std :: map被维护为二进制搜索树，与unordered_map相比，使用map的主要优点是它根据键对元素进行排序。 使用std :: map而不是std :: unordered_map的另一个好处是，它支持开箱即用的对。 但是，O(log n)和O(1)之间的差异可能是TLE和AC解决方案之间的差异。 因此，让我们看一下如何为一对整数创建哈希函数。

This structure tries to return a unique integer for every pair it gets. You just need to plug this struct into your unordered_map and voila! Your hash table now supports std::pair<int, int>.

此结构尝试为其获取的每对返回唯一的整数。 您只需要将此结构插入您的unordered_map中，瞧！ 您的哈希表现在支持std :: pair <int，int> 。

std::unordered_map< std::pair<int,int>, int, HASH > hash_table;

You can Google many more hash functions suited for different needs and choose your flavor.

您可以使用Google的更多哈希函数来满足不同需求，并选择自己的风格。

std::map should be only used when sorting of elements is required other than that std::unordered_map is your friend. The same goes for std::set and std::unordered_set.

std :: map仅在需要对元素排序时才使用，而不是std :: unordered_map是您的朋友。 std :: set和std :: unordered_set也是如此 。

Also, you can use reserve with std::unordered_map too. In my benchmarks, it sped up the process of adding elements to the hash table 1.3x times.

另外，您也可以在std :: unordered_map中使用reserve。 在我的基准测试中，它加快了将元素添加到哈希表的过程1.3倍。

If you want a faster hash table than unordered_map and you or your CP platform uses g++, there is excellent news. You can use __gnu_pbds::gp_hash_table! It isn’t part of the standard library but has almost the same interface as std::unordered_map but is much faster.

如果您想要一个比unordered_map更快的哈希表，并且您或您的CP平台使用g ++，则有个好消息。 您可以使用__gnu_pbds :: gp_hash_table ！ 它不是标准库的一部分，但具有与std :: unordered_map几乎相同的接口，但速度更快。

__gnu_pbds::gp_hash_table is faster than std::unordered_map because it drops a lot of many unnecessary features that STL has to retain. If you want a better explanation, you can look at the comment here, and if you want more insight, you can see this post here.

__gnu_pbds :: gp_hash_table比std :: unordered_map更快，因为它删除了STL必须保留的许多不必要的功能。 如果您想得到更好的解释，可以在这里查看评论，如果您想获得更多的见解，可以在这里看到这篇文章。

There is one more optimization that you can do for std::unordered_map that is setting its max_load_factor to 0.25. The load factor is defined as the ratio of the number of elements in the hash table to the number of buckets. Keeping max_load_factor at 0.25 means at least ¾ of the buckets will be empty. This reduces collisions in the hash table; therefore, the lookup time but also increases the space taken by your hash table. I couldn’t find much of a performance gain when using it, but you can try it if std::unordered_map seems to perform worse than you expected, and you can’t switch to gp_hash_table.

您还可以对std :: unordered_map进行另一项优化，将其max_load_factor设置为0.25。 负载因子定义为哈希表中元素数与存储桶数之比。 将max_load_factor保持在0.25意味着至少3/4的存储桶将为空。 这样可以减少哈希表中的冲突； 因此，查找时间还会增加哈希表占用的空间。 使用它时，我找不到很多性能提升，但是如果std :: unordered_map的表现似乎比预期的要差，并且无法切换到gp_hash_table ，则可以尝试使用它。

结论 (Conclusion)

To summarize:

总结一下：

1. Use fastscan() for the fastest integer input and std::cin without sync for the rest.

   使用fastscan()获取最快的整数输入，并使用std :: cin其余部分不同步。

2. Use reserve with std::vector and std::unordered_map as much as possible.

   最好将reserve与std :: vector和std :: unordered_map一起使用。

3. Use assignment operator to copy vectors and operator [] instead of at() function

   使用赋值运算符复制矢量和运算符[]代替at()函数

4. Use addition assignment operator instead of addition and then assignment for strings as well as other classes that support it.
   使用加法赋值运算符代替加法，然后为字符串以及支持它的其他类赋值。

5. Don’t use std::list use std::vector instead.

   不要使用std :: list而是使用std :: vector 。

6. Use std::map and std::set when the keys need to be sorted otherwise use std::unordered_map or std::unordered_set, respectively.

   当需要对键进行排序时，请使用std :: map和std :: set ，否则请分别使用std :: unordered_map或std :: unordered_se t。

There are a lot more optimizations that you can achieve in C++. An example of a small one would be to use bit shift operators instead of multiplying or dividing by powers of 2, as shown here.

在C ++中可以实现更多的优化。 一个小的一个例子将是使用，而不是乘以或由2的幂除比特移位运算符，如图这里 。

I would encourage you to explore more on your own, benchmark any such tips you may find, and maybe comment them down below. I had fun making this post and hope you had fun reading it too and learned something new.

我鼓励您自己探索更多内容，对可能找到的任何此类技巧进行基准测试，并在下面进行评论。 我很高兴撰写这篇文章，希望您也能阅读愉快并学到新东西。

P.S.: I have assumed that the code is compiled without any compiler optimization because the primary target audience of this article is competitive coders.

PS：我假设代码是在没有任何编译器优化的情况下编译的，因为本文的主要目标读者是有竞争力的编码人员。