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

Автор nitesh.11911687, история, 23 месяца назад, По-английски

Which is the Most Underrated Data Structure you know and reason for that.
This will help us to learn that and will help in future.

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

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

linked list for sure. Reason : don't know

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

    it's not underrated, it's just useless.

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

      Everything has its uses, for example linked lists are quite nice for stuff like euler circles, and also linked list is very simple and cool to implement on your own

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

      Then implement LRU cache without linked list in O(1) complexity

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

      While they are not super useful, I would definitely agree that they are underrated.

      One nice trick is to combine them with maps to iterators std::map<T, std::list<T>::iterator>, in this way you can get benefits of both map and list. Example: 110657402 (although I don't understand this solution anymore so I am not sure whether that was really necessary).

    • »
      »
      »
      23 месяца назад, # ^ |
        Проголосовать: нравится -16 Проголосовать: не нравится

      bfs with list is delicious

      list q = {0};
      for(int v : q) for(int i : g[v]) if(d[i] == -1) {
      	q.push(i);
      	d[i] = d[v] + 1;
      }
      
»
23 месяца назад, # |
  Проголосовать: нравится +137 Проголосовать: не нравится

A single integer

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

Umm..stack and deque. They can be pretty useful sometimes!

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

set with custom comparator

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

the rope. It does string operations in O(logN) time complexity and I think it can be very useful sometimes

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

    it's actually very useful, but sadly Splay Tree does almost everything it can do :(

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

      its actually just a splay tree/rb tree/skip list/any dynamic O(logN) data structure with strings in fact

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

        one advantage) rope can be used like this:

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

unordered_map and reason is it cause TLE due to collision problems .

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

I'd say maps but everyone uses maps xd

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

STL std::list<..>, it's sometime useful when we need insertions and deletions in O(1).

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

Cartesian tree

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

bitset

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

Trie

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

Maps. They are the best