Minggu, 19 Januari 2014

Tipe-Tipe Data yang Disupport C++

Kayaknya udah seminggu gak ngeblog, daripada ini blog karatan, dan saya masih mengumpulkan niat buat nulis cerita pelatnas november kemaren, mending saya bahas sesuatu yang berhubungan dengan CP :v kali ini saya mau ngebahas sesuatu yang simple, yakni tipe-tipe data yang-mungkin-ribet-dibikin-sendiri-tapi-ada-di-C++ :v oiya, penulisannya mungkin mirip sama urutan di Uhunt, maklum saya sering pakai UVa gara-gara belajar pake Buku Competitive Programming buatan Steven Halim dan Felix Halim (promosi? gak kok :p) format penulisannya kurang lebih nama_tipe (header_yang_dipakai)

  1. Linear Data Structure
    Kenapa namanya linear? karena emang bentuknya linear..
    • Static Array (Ada dari sononya)
      Bentuk paling simple, deklarasinya seperti berikut:
      Tipe_Data Nama[n]
      Dengan n merupakan banyaknya index pada array tersebut.Oiya, index tersebut dari 0 sampai n-1, jadi hati-hati dalam mendeklarasikan nilai n, usahakan lebihin dikit.Selain itu, dimensinya juga tergantung dari banyaknya tanda [], contohnya int arr[30][50][20] memiliki 3 dimensi dengan space 30*50*20
      Notable usage:Hampir semua yang perlu dicatat, seperti tabel DP yang nanti akan dibahas
    • Dynamic Array/Vector (<vector>)
      Salah satu tipe data yang menurut saya keren.Kenapa? karena bentuknya gak fixed seperti Static Array, yakni bisa berubah-rubah sesuai kebutuhan :D tapi hati-hati dalam penggunaan vector, karena lebih lambat dari menggunakan Static Array
      Referensi : Vector
      Notable usage : Representasi Adjacency List,Edge List,dll
    • Queue (<queue>)
      Tipe data yang menggunakan prinsip FIFO(First in First out), atau dalam kehidupan nyata biasa kita lihat dalam bentuk "antrian".Bisa dipakai dalam soal yang mensimulasikan kejadian, cuma biasanya pembuat soal gak mau bisa disimulasikan :v
      Referensi : Queue
      Notable usage : BFS,Topological Sort
    • Deque (<dequeu>)
      Singkatan dari Double Ended Queue.Tipe data yang mirip seperti queue, namun data juga bisa diekstrak dari bagian belakang queue,dan juga memperbolehkan insersi dari depan.
      Referensi : Deque
    • Stack (<stack>)
      Tipe data yang menggunakan prinsip LIFO(Last in First out), atau dalam kehidupan nyata biasa kita lihat dalam "tumpukan".Stack juga merupakan bentuk asli dari rekursi, namun stack tersebut punya batas memory yang berbeda.
      Referensi : Stack
      Notable usage : DFS,Topological Sort, SCC,dll
    • Linked List (<list>)
      Gak tau gak pernah make :v tapi katanya bahaya dipakai, karena menggunakan pointer yang bikin lambat dan bisa Runtime Error :/
      Referensi : List
     
  2.  Non-Linear Data Structure
    Struktur data yang bentuknya gak bisa digambarin secara linear, biasanya jadi kayak tree
    • Map (<map>)
      Map memiliki bentuk asli Binary Search Tree, lebih spesifik Red-Black Tree.Map kurang lebih memetakan key ke valuenya.Map ini menurut saya keren, karena membantu compression dengan mengurangi banyaknya space yang dipakai, tapi mengorbankan time karena pemanggilannya tidak O(1) tapi O(log N)
      Referensi : Map
      Notable usage : Compression,memetakan yang tidak berupa integer
    • Set (<set>)
      Seperti Map, hanya saja set cuma menyimpan value tanpa key
      Referensi : Set
      Notable usage : Mencari Cycle,Dijkstra's Algorithm
    • Priority_queue (<queue>)
      Struktur data yang mirip Heap.By default, Priority_queue punya prioritas nilai max berada di top, tapi ini juga bisa diakali
      Referensi : Priority_queue
      Notable usage : Prim's,Dijkstra's,Variasi Sliding Window
     
  3. Pengganti Struct
    Saya rasa pembaca sudah mengerti apa itu struct.Struct ekivalen dengan record di pascal, atau tipe data yang menyatukan beberapa informasi menjadi satu.Pada C++,ada tipe data yang membantu penyatuannya, tapi jika repot mungkin lebih mudah mendeklarasikan struct sendiri.Tipe data itu adalah:
    • Pair (<utility> atau <algorithm>)
      Referensi : Pair
     
Oiya, sekedar tips buat pembaca:
  1. Selalu declare ukuran array lebih besar dari yang diperlukan.Gak mau kan, karena suatu kecelakaan ukuran arranya kurang dikit?
  2. Pada vector, terdapat operasi push_back dan pada pair terdapat first,second,serta make_pair yang mungkin cukup lama dan ribet diketik.ada baiknya menggunakan macro agar mempermudah penulisan, seperti berikut:
    #define pb push_back
    #define mp make_pair
    #define fi first
    #define se second
    Pendefinisian terserah pembaca masing-masing, pendefinisian di atas juga cuma pendefinisian yang sering saya pakai :p
  3. Seperti contoh di atas, gunakan typedef untuk mendefinisikan tipe data yang mungkin ribet untuk ditulis berkali-kali, seperti pair<int,int> menjadi pii
Sekian tulisan yang bisa saya buat malam ini, semoga bisa bermanfaat bagi pembaca sekalian :)

Referensi :
www.cplusplus.com

0 komentar:

Posting Komentar