hari862's blog

Effective Usage of C++ STL for quick and concise code writing in competitive programming
By hari862, 11 years ago, In English

I am not any expert in competitive programming, so this post is not about teaching you fellow coders any new things that you already don't know. Rather I am asking you high rated Div. 1 people to share your experience, problem solving approach of using STL(vector, pair, queue, priority queue, stack, set, map, algorithm) for good understanding of when and where to use STL.

I have already read the various STL tutorials on Topcoder(by DmitryKorolev): STL Tutorial 1 STL Tutorial 2

Codeforces: DFS using STL by evandrix

But after reading these I found out that they are just meant for giving you some basic understanding of "What is STL and its importance". These were very informative, but not so much helpful for contest programming as they didn't gave any practical idea or insight of in which cases a programmer should go for which STL.

I have very little experience of contest participation but in this short duration I went through codes of various people to learn their way of coding. There I found out that there is a powerful feature of the Standard Template Library (STL) – a great tool that, sometimes, can save you a lot of time in an algorithm competition. I learned that some people often have very short solutions by using the STL. Due to this they are able to write and submit their codes very fast. e.g.

vjudge3's pair usage for 297C - Splitting the Uniqueness

Mr.'s map, pair usage for 402B - Trees in a Row

Rebryk's queue usage for 371B - Fox Dividing Cheese

while for the same problem 404C - Restore Graph ig_dug's vector, pair and kaushik90's easy vectors

Above all I found that I was always relying on using arrays and due to this it was very difficult for me to handle the data and consequently I was not able to implement my approach. One more problem I felt later that I was confused for Which STL should I select for a given problem scenario. It happened at times that I needed pair but I was using two separate vectors.

So in the end I am requesting and inviting codeforces community to share their experiences of effective usage of STL for fast and short code writing. It would be very much benefiting if in your replies you explain your way of thinking in the perspective of using STL, Please explain how do you choose the appropriate STL(as in my case of confusion of selecting pair or 2 vectors) in the contest problem theory. If you want then you can cover all the STLs or you cover just one STL feature, but cover it with good explanation, examples and in detail.

This will really help the new learners.

Thanks. Happy solving.

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

STL gives you a chance to use advanced data structures and algorithms when you don't even know how to use C++ (as it was with me). You can also use simple algorithms like find(), lower_bound(), binary_search() to code faster (but usually it's easier to write several "for"s anyway). How many different values in array A if 1 <= A[i] <= 10^6 , 1 <= n <= 10^5? Just push it in set<>, size is the answer! You don't need to iterate over it with exist[A[i]] = 1, i = 1..n and count += exist[i], i = 1..1000*1000. Why is it better? Because in case 1 <= a[i] <= 10^18 set<> works fine too. Even if A[i] is a string, you simply need to calculate the hash values, and use the same approach. If A[i] is the point (i,j) in table NxM you can use values i*M + j to USE THE SAME APPROACH)) Of course, it's possible to solve this problems in different way, without set<> at all, and with much better complexity than NlogN, but it's a question of your targets)) So, I meant that it's better to try STL in different applications to simplify your code and reduce it's size, but you souldn't try to use it for "prefect code" or super short implementations of dfs or smth else. It smells like an attempt to create universal template for all problems)

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Please, it's the C++ standard library you're talking about, not the STL

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    ... misunderstanding going on forever ...
    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for pointing out, I've changed the title of this post as "C++ STL".

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Now that's even more confusing... but whatever

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Whatever! lets not go into the nomenclature. Lets focus on the improving our problem solving skills. If we learn C++ standard libraries for this goal then this is the real purpose of this post... :)

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sure, see my other comment below for a more constructive constribution ;)

          → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      C++ standart library, not STL.

      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Here is an example where I abuse the C++ standard library in a really cruesome way to implement the fully dynamic variant of the convex hull trick to maintain the upper hull of a collection of linear functions.

Note how I have a multiset<Line> that maintains the set of lines, ordered by slope. Now I had the problem that to search the matching line for a given X coordinate in eval, I need to binary search on the intersection points of adjacent lines. Unfortunately multiset has no option to let me customize the binary search, so I give every line a std::function<const Line*()>, so that it can look up it's successor while comparing. Then I abuse lower_bound to do the binary search, using a special query line. Line::operator< contains a hack so that it behaves differently when comparing against such a special query line.

This is nasty, but it's short, fast enough and gets the job done, which is all that matters for me

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, you could get much shorter code if your structure were to inherit from multiset<Line> :) Then instead of e.g. begin(lines) you have begin(), instead of lines.insert(...) you have just insert(...), and you can use iterator as a type (instead of the typedef-ed It). You also have empty() automatically :)

    Otherwise it's a neat implementation, I like it. Although instead of succ I prefer to have a double xLeft which is the x-coordinate of the intersection with the previous line in the set. It is easy to binary-search on in eval.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @dj3500 Good observation about the inheritance. I guess having xLeft instead of succ avoids a lot of the ugly hackiness here, not sure why I didn't think of that. I guess I didn't think it was easy to maintain, but it seems to be.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yes, it is sufficient to compute it for y and next(y) at the end of insert.

        I thought that succ was considered your technical/C++11-features tour-de-force here, not ugly hacking :P

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it +8 Vote: I do not like it

          No I would never dare to do something like this if it was avoidable at a reasonable cost :P It's interesting that it's possible, but it's not anywhere near elegant or clean

          → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it +8 Vote: I do not like it

          Ahh now I remember. The problem was that I wanted to represent the intersection implicitly using two lines, rather than expressing it as an imprecise floating point value. Still I could just have a mutable Line* predecessor property instead of the std::function, which should be a bit simpler. And simple is always better :)

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, I see. But the doubles are not that bad. For example, I recently solved a problem with this structure where I needed to use long doubles anyway (instead of long longs) in the final line of bad to get accepted.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes, I had the same problem in the CodeChef challenge that I used this for. I guess I would need to get incredibly unlucky for this to shoot me in the foot, but if there is a choice, I'd rather be safe than sorry :)

              → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That was brilliant @niklasb , I can understand the algorithm for Dynamic variant of the trick, but i have never seen such usage of STL.

    I have a few doubts regarding C++ usage (I am only asking because i could not find much on google). 1. How does this work in language** auto y = insert({ m, b });** line 25 2. what is the name or the idea behind , this mutable function<const Line*()> succ; in Line 4 ? 3. How does the ** bool operator<(const Line& rhs) const** work ?

    These questions might sound really dumb,but i just need a stack-overflow link to the name of these ideas i will learn them myself..

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      (1) is just just the auto keyword from C++11 together with an initializer list as the constructor argument for std::pair. (2) is a usage of the class std::function introduced by the C++11 standard. It's a hack because I need an iterator to the element successor in the comparator (3) is just a standard operator overload, with the trick that it behaves differently when comparing a line and a query and when comparing a line to another line

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After some time with the code I think it has a problem. When a new line is inserted, the function succ must be updated for the new line after all the erases. Also, the succ of the new line's previous should be updated as well.

    my suggestion for fixing this issue:

    const ll is_query = -(1LL<<62);
struct Line {
    ll m, b;
    mutable function<const Line*()> succ;
    bool operator<(const Line& rhs) const {
        if (rhs.b != is_query) return m < rhs.m;
        const Line* s = succ();
        if (!s) return 0;
        ll x = rhs.m;
        return b - s->b < (s->m - m) * x;
    }
};
struct HullDynamic : public multiset<Line> { // will maintain upper hull for maximum
    bool bad(iterator y) {
        auto z = next(y);
        if (y == begin()) {
            if (z == end()) return 0;
            return y->m == z->m && y->b <= z->b;
        }
        auto x = prev(y);
        if (z == end()) return y->m == x->m && y->b <= x->b;
        return (x->b - y->b)*(z->m - y->m) >= (y->b - z->b)*(y->m - x->m);
    }
    void insert_line(ll m, ll b) {
        auto y = insert({ m, b });
        ********removed line******
        if (bad(y)) { erase(y); return; }
        while (next(y) != end() && bad(next(y))) erase(next(y));
        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
        while (y != begin() && bad(prev(y))) erase(prev(y));*****added line*****
        **if(y != begin()) prev(y)->succ = [=] { return &*y; };*****added line*****
    }
    ll eval(ll x) {
        auto l = *lower_bound((Line) { x, is_query });
        return l.m * x + l.b;
    }
};
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do you have a test case where the version without your fix gives the wrong answer?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, I found the problem while solving 91E - Igloo Skyscraper (I've built a segment tree of CHT's). When I relied on the original code the first input example wasn't correct. This is the WA solution 59667839. This is the submission with my fix that got Accepted 59662177. These solutions are identical except the changes in the "insertLine" function. (The code is a bit different for the purpose of the question)

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you very much, but as mentioned above this implementation has some issues and bugs. For those wondering, here is the better version of Convex Hull Trick online.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I also use map<vector> in 404C- Restore Graph problem to make much simpler implementation : 6083798

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    one suggestion. rather than using map<int,vi> path u can use vi path[MAX]. this will reduce ur time complexity by a factor of , and the rest of the code can remain exactly the same.

    PS: note that this will not work if u want to access large indices like path[1<<30]. in that case u will have to use map only.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I see. Since the problem only in range 10^5 using array is more efficient right?

      I didnt notice this while implementing. Thank you

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        As long as you have enough memory it will be a lot of more efficient.

        → Reply