# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | atcoder_official | 163 |
3 | Um_nik | 162 |
3 | maomao90 | 162 |
5 | adamant | 157 |
5 | -is-this-fft- | 157 |
5 | djm03178 | 157 |
8 | awoo | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
Name |
---|
Thanks this is very useful.
Cool stuff. But don't use deque, it's slow.
I always use hull.end()[-2] in convex hull implementation. It's surprising that end(hull) works too.
For most purposes, using a deque is almost as fast as a vector according to some of my submissions.
There are only two issues that I know of that anything using a deque can face:
vector<deque<int>> a((int)1e6);
, it is going to MLE (and if not MLE, TLE) because a deque allocates memory in chunks, and that chunk tends to be large. For example, using GCC on codeforces, it is 512 bytes, and it is quite bad to allocate a vector of $$$10^6$$$ empty deques in this case.I think the second part is the reason behind the comment that deques are slow, but feel free to correct me if this issue showed up in some other context.
Some python people avoid using deque for their BFS by doing something like:
which translates to the following in c++:
I avoid using deque for my BFS by using something like this.
You can either use it like a normal
std::queue
, or plug it right into a range-based for loop. It's kinda crude, but it worksIt is worth noting that
and
andor
are actual keywords on C++ since C++98 or so. Also for BFS I like to use something like this. (probably meaningless rant: why do the container adapters not haveemplace
? this makes things a bit inconvenient compared to things that we haveemplace
for.)Is it possible to declare a,b under while?
Hot take: You generally don't need
std::pair
, and you never needstd::tuple
. Typically, they are juststd::array<T, 2>
orstd::array<T, 3>
expressed in a verbose way.std::pair
can be useful if you need to store different types or do stuff withstd::map
. If you want to pack more than 2 fields in a different type, you need to define structs for basic readability.(I learned this style from Savior-of-Cross's code, I think it makes sense and made my code cleaner, but I'm interested to hear any downside of this approach)
I agree with this, and it is definitely not a hot take in my opinion. In fact, in some competitive scenarios I've observed that using
std::array
helps with vectorization as well andstd::pair
andstd::tuple
have surprising inherent overheads compared to a toned down implementation liketemplate <class T, class U> struct Pair { T first; U second; };
(so much so that some software companies ban their use in their codebases). I would recommend watching this for a good introduction to why this is the case. EDIT: just watched it again, and it seems an important reason in the competitive programming context wasn't covered.std::pair
andstd::tuple
are not forced to be trivial types even if their members are, so this adds some non-zero overhead sometimes. Similarly, sometimes compilers aren't able to reason through all the abstraction that is provided by the suboptimalstd::pair
andstd::tuple
implementations, so that factors in sometimes too.However, I have seen way too many people spamming
std::pair
andstd::tuple
everywhere, and it is quite annoying to look at (even more so to write)push_back(make_pair(...))
all the time. The main idea is that if you usestd::tuple
, you should at least make your code not-so-ugly.There are still examples where you might need
std::tuple
: one reason to not completely abandon it in favor of simple structs is that you can't useranges::elements_view
with structs having different types, becausestd::get
is defined only for them (andstd::array
andstd::pair
). Perhaps this can be fixed with better "accessing" functionality for structs, but I don't see how to do this.nit: you can't do:
works with pair, tuple, not struct
you also can't do:
works with pair, tuple, struct
How to use std::array if you want elements to be not of the same type?
You don't. (I'm not saying you "definitely can't", but you would not appreciate finding out how)
It's not hard, you could use
std::array<std::variant<T1, T2>, 2>
(though this should not be used by any sane person who cares about performance).How do you implement a scanline then? You usually have two types of events (something started and something ended) and you need to sort events firstly by the $$$x$$$ coordinate and then by the type. A tuple of $$$x$$$, type and parameters (usually
tuple<int, bool, int>
) does perfectly fine from my perspective. Do you define a structure with a custom comparator here as well?I just use
std::array<int, 3>
for this case. In my opinionstd::tuple
is fine for quick and dirty operations (like sorting and so on) in cases where the data types aren't convertible or take too much memory, but for more complicated code (such as when you want to store some history on a stack and do divide and conquer on it, or even just DSU with rollbacks), I try to make things more readable and debuggable by making a different struct. As a rule of thumb, I keep my library implementations clean with meaningful variable names. Of course, your mileage may vary.But this is not very clean even in comparison to the
tuple
approach. The second part is semanticallybool
(or even someenum
, but you got the point). Also, what if points are in a floating-point type?array<double, 3>
? I doubt any sane person would usedouble
as a substitute forbool
. Also, the parameters are not of the same type as $$$x$$$ quite often.Besides that, I even think that always substituting
tuple<int, int, int>
witharray<int, 3>
is a bad idea. They are semantically different. The tuple means just the collection of three entities and the array means the collection of three entities of the same type. Just because three types happen to be the same it does not mean they are obliged to be the same.And even defining a separate structure is not always the best solution, because it takes off some transparency of what is happening. For example, if I had to choose between a structure with fields $$$x, y, z$$$ that should mimic the tuple behaviour and an actual tuple, I would have prefer the latter. Obviously, here we all should forget for a second that in C++ specifically you have to write ugly
get<2>(tuple)
to access the third element, but in other a bit more modern languages it is usually done astuple.2
and I fail to see much of a difference fromnot_tuple.z
. Not to mention that structured bindings to your own custom types sometimes work not in the most trivial way.About how morally incorrect using
std::array
is, I agree. It's just thatstd::array
is easier to type and access. I definitely won't use this kind of a thing in "real-world" code, but I think it is convenient for competitive programming.Regarding custom structs, I think I still have reservations about choosing
std::tuple
over them. For instance, if I had to write an implementation of some flow algorithm, I personally won't store the edge as a tuple (a couple of integers to maintain vertex/edge indices, and a couple of flow variables). I don't deny that they're very interoperable, and that they make a lot of sense when you are (only) thinking about what the data does. I think it's a matter of personal preference, though.I didn't get your point about structured bindings not working in the most trivial way, could you elaborate? I almost always use a struct and bind variables in the order of declaration in the struct, is there any place where this fails?
Using structures for edges in graphs/flows are perfectly fine, I actually think that it is more correct way of doing it. But the difference is that here field names are usually
.to
,.from
and.capacity
, i.e. they are meaningful. My example was about the exactly opposite case.I spent about 90 minutes trying to remember what was happening when I decided to be extra cautious with structured binding and, apparently, the point was that binding a tuple-like type and binding to data members are slightly different and you can accidentally switch from one to another. I have no clue how I did that (maybe by inheriting something?), and I failed to recreate an example.
I rarely use bool whenever I can use int, so I don't have such use cases. If you want some symantical restriction, I think it's better to go with structs. In case of floating points — yes, sometimes that happen. I will define custom structs.
Everything here are inherently hacky. If you want industry-style code, you have to not use anything except structs.
I believe that even in industry-style code there are places for tuples, especially in public APIs (see examples above). In particular, STL functions love having pairs in their return types, tuples are not any worse. The reason why they are uncommon in STL is that there was no
std::tuple
until C++11. Another reason, obviously, is that functions that return more than two variables are uncommon in general, but it does not mean their existence inherently means bad design.To be fair, a recent trend in the C++ standard library API is to define a custom structure instead of std::pair or std::tuple and return it.
https://en.cppreference.com/w/cpp/algorithm/ranges/next_permutation
For example C++20 version of
next_permutation
returns a wrapped pair of (iterator, bool) and named its members as.in
,.found
for better readabilityHow do you code Dijkstra?
Thanks! this is useful blog. can anyone tell me where I can download c++20 ?
You should have it if your compiler is up-to-date. Make sure you don't have compiler arguments setting you to an older version (use
-stdc++=20
on GCC/Clang, and/std:c++20
or/std:c++latest
on MSVC).These C++ code is too erotic.
Don't forget there's also reverse iterator so you can also use
rbegin(a)[0]
to access the last element.That's true (and it makes more sense too)! However I almost always use
end(a)[-1]
instead ofrbegin(a)[0]
because:++
instead of--
and vice versa if you mix iterators.For the last element please use .back(), .front() also exist for accessing the first element but [0] is shorter anyway.
Is the AC server a discord server? If so could I get an invite ...
No
It is risky to use deque. Last time someone used 10^6 deques in NOI in China, and got MLE.
Why? I think it's just a double-ended linked list
You can refer to this. It explains in detail why using many deques can cause MLE.
Can someone explain how to use zip and enumerate from the spoiler snippet?
Check this.
You can also use
auto&& [x, y]
instead ofauto [x, y]
if you want references tox
andy
, while taking into account the case of enumerate.