0-jij-0's blog

About Implementing Data Structures in C++
By 0-jij-0, history, 4 years ago, In English

Hello everyone,

I've been working on implementing some data structure, and the following question crossed my mind:

In terms of performance, is it better to use STL functions in my class or write them from scratch? For example, if I have a vector and I need to find it's prefix sum, do I write a typical for-loop or use the partial_sum function is the "numeric" library. (This is not my only problem but just an example to explain my question)

In terms of readability I have no doubts that STL is more convenient, but I'm not sure about performance.

Any help would be appreciated. Thank you :)

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

»
4 years ago, # |
  Vote: I like it -29 Vote: I do not like it

I think both will have same perfomance if use prefix instead of postfix increment in for loop. So I think you should just check implementation of each function.

→ Reply
»
4 years ago, # |
  Vote: I like it -39 Vote: I do not like it

A simple recommendation: make your data structure working and then think about its performance if you have any issues with it.

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

    I don't see the point of commenting when you have nothing useful to provide.

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

      I am sorry if you cannot see useful info :(

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

    How exactly does your comment answer his question?

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

      It is bad habit to think about performance before having working code. It is bad habit to think about performance if there is no issues related to it.

      In general, if complexity of self-written code is same as one in STL, then it is better to use STL. However we know nothing about his code, so how can we provide exact answer?

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

The partial_sum function will work slowly as compared to for-loop if optimization are turned off. If turned on, the partial_sum has almost identical performance (a little bit better but not much difference).

You can use chrono library in C++ to measure their performance on large vector size.

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

    Do you mean compiler optimizations or what optimization(s) exactly?

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +13 Vote: I do not like it

You can use the one which is more convenient to you. Calculating prefix sums using loops or using accmulate or partial_sum won't make huge difference and it's very unlikely that you will run into TLE issues using one and AC using other. If something is already implemented than ofcourse it is thourouly tested and then added to the library for our use. When using them, you should know their time complexities or in what cases they should be avoided. This is the reason that every other day there are blogs on codeforces like:
- why my memset not working when filling my array with 1's?
- why my code gives TLE with unordered_map but got AC in just x(ms) using map?
- I used cerr and it gave tle?
- Why lower_bound(begin(s), end(s), num) on set s gives TLE while s.lower_bound(num) got accepted? and the list goes on ...
I think it's hard to answer your question in general, because the answer depends on what stl function you are using/talking about. for e.g. if you say i want to implement my own sorting function, or map or hashtables then the answer is better to use STL because they are more robust and maybe using hybrid algorithms and much more and has guaranteed runtime complexity.
The last point which i think that most people don't use them(partial_sum, accumulate, for_each, count and many more) because we need to remember their syntax how to use them and instead of remembering just write your own. Every single time i use them i always tend to miss something and i need to google to look their syntax.
P.S: Ignore my grammatical mistakes bcz my english is poor.

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

    Thank You! You are right I was aware that the easiest way to get an answer is to test both methods and time them, but I thought maybe experienced users here could help if they already did that before me. Thank you again.

    → Reply