Блог пользователя roy..

Vector or array? starts from 1 or 0?
Автор roy.., история, 15 месяцев назад, По-английски

I know that these habits probably aren't that important at all in terms of improving programming skills. But as I program more often, I find storing items in a vector which is often accompanied by "starting with 0" is handier. Should I make some changes or there's in fact no big difference?

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't quite understand the question about vector and array. A vector is a dynamic STL array, that is, it allows you to add a new element to the end in O(1) on average. Array is a static structure that does not require additional inclusions. Its main differences from a vector are the impossibility of adding a new element without re-creation and the lack of support for iterators. In most cases, if the size of the array is not fixed and no edge cases are known, programmers use a vector. In sports programming, you can use arrays to avoid unnecessary constants in the asymptotics.

About indexing from 1. Most programmers use indexing from 0, it happened historically. You can read Edgar Dijkstra's article "Why numbering should start at zero", where he clearly describes the benefits of such numbering — https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html. In fact, since almost all IT companies use this standard, when applying for a job, you still have to retrain for it :)

→ Ответить
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    the lack of support for iterators

    You always can use pointers as iterators, and there are such helpers as std::begin() and std::end(), which return iterators for arrays too.

    → Ответить
    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      This is true. However, as far as I remember, std::array is used to work with iterators on static arrays.

      → Ответить
      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        iirc, std::array is actually intended to be a zero-overhead wrapper of the C-style array. That's the main point. It enables a lot of features without extra cost, and being able to use iterators is just one of the many benefits that come along.

        → Ответить
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you so much for this convincing response. The question about vectors and arrays derives from top-rated coders' and tutorial preference for vectors over arrays (according to the very limited pieces of code I've seen). So I suggest that vector is a better choice in terms of CP?

    → Ответить
    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Quite a contentious issue. You can use either one or the other. Although, for storing a sparse graph, a vector is obviously indispensable. A vector provides more functionality, but don't forget about memory reallocation on resize, which is O(n). Personally, I use the vector much more often. If the written algorithm has the asymptotics implied by the author, then the vector will not affect the sending verdict in any way. I advise you to read the article — https://clck.ru/33QqUK (I hope the translator will help) for more efficient use of this structure.

      → Ответить
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "if the size of the array is not fixed and no edge cases are known, programmers use a vector" I didn't understand what you meant by "no edge cases are known" can you give an example?

    → Ответить
    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      I assume "edge cases" could be some rare situations that make vectors unusable, that you have to use arrays. For example, since vectors allocate their memory on the heap, it can be slow (usually that doesn't matter that much most of the time).

      → Ответить
    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I called the edge cases the maximum size of the array, which is usually written in the task condition. For example, if n (denote by the size of the array) <= 10^5, then it is enough to create a static array of size 10^5: int a[(int)1e5];

      → Ответить
»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Use std::vector if you have no obvious reason to use array.

→ Ответить