Data Structure

1. Vector

• Most common methods:

• push_back() -- O(1)

• [ ] --> bracket operators -- O(1)

• size() -- O(1)

 code:

vector<int> v;                   // v = {}

cout << v.size() << endl;   // outputs 0

v.push_back(20);            // v = {20}

v.push_back(10);            // 20, 10

v.push_back(10);            // 20, 10, 10

cout << v[1]<<endl;         // 10

cout << v.size() << endl;   // 3

 

2. set

 Most common methods:

•  insert() ---> O(logN)

•  find()    --->  O(logN)

•  size()    --->   O(1)

• Code:

   set<int> s;              // s = {}
  cout << s.size() << endl;   // outputs 0
  s.insert(20);            // s = {20}
  s.insert(10);            // 10, 20
  s.insert(10);            // 10, 20
  auto it = s.find(10);   // it is an iterator that points to 10
  cout << (it != s.end() ? "FOUND" : "")<<endl;         // FOUND
  cout << v.size() << endl;   // 2
   

  3. unordered_set

   Most common methods:

•  insert() ---> O(1)

•  find()    --->  O(1)

•  size()    --->   O(1)

Code:

 unordered_set<int> s;              // s = {}
cout << s.size() << endl;   // outputs 0
s.insert(20);            // s = {20}
s.insert(10);            // 10, 20 {could in any order}
s.insert(10);            // 10, 20
auto it = s.find(10);   // it is an iterator that points to 10
cout << (it != s.end() ? "FOUND" : "")<<endl;         // FOUND
cout << v.size() << endl;   // 2

for(auto e: s) {...}

for(auto it = s.begin(); it != s.end(); ++it) {...}

4.map

• Most common methods:

•  insert() ---> O(1)-->O(logN)

•  find()    --->  O(1) -->O(logN)

•  size()    --->   O(1) --> O(1)

  • [ ] --> bracket operators -->O(logN)

          Code:

  map<int, int> m;              // s = {}
  cout << m.size() << endl;   // outputs 0
  m.insert(make_pair(20, 1));  // m = {(20,1)}
  m.insert(make_pair(10, 1));   // m = {(10,1), (20,1)}
  m[10]++                      // m = {(10,2), (20,1)}
  auto it = m.find(10);   // it is an iterator that points to (10,1)
  cout << (it != m.end() ? it->second: 0)<<endl; // 2
  auto it2 = m.find(10);  // it is an iterator that points to (20,1)
  cout << (it2 != m.end() ? it2->first: 0)<<endl; // 20
  cout << v.size() << endl;   // 2
   

  5. Unordered_map

  • Most common methods:

  •  insert() ---> O(1)-->O(1)

  •  find()    --->  O(1) -->O(1)

  •  size()    --->   O(1) --> O(1)

    • [ ] --> bracket operators -->O(1)

     Code:

    map<int, int> m;              // s = {}

    cout << m.size() << endl;   // outputs 0

    m.insert(make_pair(20, 1));  // m = {(20,1)}

    m.insert(make_pair(10, 1));   // m = {(10,1), (20,1)}

    m[10]++                      // m = {(10,2), (20,1)}

    auto it = m.find(10);   // it is an iterator that points to (10,1)

    cout << (it != m.end() ? it->second: 0)<<endl; // 2

    auto it2 = m.find(10);  // it is an iterator that points to (20,1)

    cout << (it2 != m.end() ? it2->first: 0)<<endl; // 20

    cout << v.size() << endl;   // 2

     

 

Share: