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

Автор tirupati, история, 9 лет назад, По-английски

I usually use vector arr[n] to represent the adjacency list of a n-vertex graph. What if I use list instead of a vector. I mean it's O(1) to add an edge in the list similar to vector(amortized) also it's O(n) to check if there is an edge between two vertices in both vector and list. I have seen most people using vector instead of list. Are there any performance costs associated with lists compared to vector?

THANK YOU :)

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

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

Are there any performance costs associated with lists compared to vector?

Yes.

  1. Linked lists consume more memory, because they have to store pointers to the next element in addition to elements themselves.

  2. Vectors, unlike lists, occupy a single block of memory which is more cache-efficient.

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

also it's O(n) to check if there is an edge between two vertices in both vector and list

for sorted vector

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    But how can we maintain a sorted vector without incurring any additional cost while adding a new edge?

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

Depends on the purpose:

Why list?

If the problem requires deletion of vertices, or addition of vertices with numbering less than the existing ones, use list.

erase in list: O(1), in vector: propotional to no. of elements after the position (can go upto O(n) )

Why vector?

Easier to implement. Can be accessed directly by indices unlike list.

(ar[i] is permitted in vector, but not in list)

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Iterating trough vector is waaaay faster than iterating trough list (because of the cashe-efficiency [user:skycelote] mentioned above. And it should definitely be your choice if you'd like to iterate trough container fast enough.