Summary of common stl container usage for algorithm problems

Table of contents

vector

stack

map

set

queue

priority_queue

therefore

[vector]

  • add element

vector<int> vec;
vec.push_back(i);

  • Get size and judge non-null

(all stl are the same)

  • initialization

vector vec;

  • delete

delete all elements

vector<int> vec = { 1,2,3,4,5 };
    vec.erase(vec.begin()+i);

Delete the i-th element and start counting from 0. If i=3, delete the element “4”.

vector<int> vec = { 1,2,3,4,5 };
    vec.pop_back();
//The output result is 1234

remove the last element

bool cmp(int a, int b) {
}
int main() {
    vector<int> vec = { 1,-2,0,-4,5 };
    sort(vec.begin(), vec.end(),cmp);

}

  • sort

vector<int> vec{ 1,2 };
    i = find(vec.begin(), vec.end(), 1);
    else cout << *i;

  • Inquire

The query method returns an iterator

#include <iostream> 
#include <vector> 
using namespace std;
int main()
{
    vector<int> demo{ 1,2 };
    Insert an element at the i-th position, that is, occupy the position of the i-th element
    demo.insert(demo.begin() + 1, 3);//{1,3,2}

    Add n corresponding elements after the position of the iterator
    demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}

    How to merge arrays
    vector<int> test{ 7,8,9 };
    demo.insert(demo.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}


    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
    return 0;
}

  • insert

#include <iostream> 
#include <map>
#include<string>
using namespace std;
int main()
{
    map<string, int> strMap;
    strMap["123"] = 1;
    strMap["234"] = 2;
    for (auto val : strMap) {
        cout << val.first << " " << val.second<<endl;
    }

    for (auto i = strMap.begin(); i != strMap.end(); ++i) {
        cout << i->first << " "<< i->second << endl;
    }
}

stack

pop() removes the top element from the stack

push() adds an element to the top of the stack

size() returns the number of elements in the stack

top() returns the top element of the stack

The stack cannot be traversed using the for(auto val:stack) method, only the head element can be obtained, and then exit one by one.

map

The map will be automatically sorted according to the size of the key. If sorting is not required to increase efficiency, use unordered_map

  • Initialization and assignment, traversal

#include<queue>
using namespace std;
int main()
{
    vector<pair<string, int>> vec;
    priority_queue< pair<string, int>> pq;
    map<string, int> strMap;
    strMap["123"] = 1;
    strMap["234"] = 2;

    for (auto val : strMap) {
        vec.push_back(val);
        pq.push(val);

    }

}

  • insert

In addition to using the [] character to directly assign, you can also do this:
Since the elements in the map are originally of the pair type, you can

map<string,int> mp;
    mp["abe"] = 2;
    mp["abd"] = 3;
    mp["abf"] = 3;

    map<string, int>::iterator iter = mp.find("abd");
    mp.erase(iter);
    mp.erase("abd");

Conversely, the elements in the map can be directly inserted into the container whose element is a pair element.

set < int > q; //Take the int type as an example, the default key value is in ascending order

set < int ,greater< int >> p; //sort in descending order

The same is true for iterators:

  • delete by key

The following two methods are equivalent

int x;
q.insert(x);     //insert x into q 
q.erase(x);      //delete the x element in q, return 0 or 1, 0 means that x does not exist in the set

  • delete by value

For map, if it needs to be deleted according to certain conditions, it cannot be deleted directly at this time, for example:

  • Points to note when using map!

  • In the map, when looking up the value by the key, it is first necessary to determine whether the map contains the key.

  • If you do not check and return map[key] directly, unexpected behavior may occur. If the map contains the key, there is no problem. If the map does not contain the key, the use of subscripts has a dangerous side effect. An element of the key will be inserted into the map. The value takes the default value and returns the value. That is, it is impossible for map[key] to return null.

It can be observed that this element is automatically created at this point:

set

The set container has two characteristics, which are automatically sorted and deduplicated

unordered_set has all the features of set except for automatic ordering

  • initialization

//small top heap 
priority_queue < int , vector < int >,greater< int > > q;
 //big top heap 
priority_queue < int , vector < int >,less< int > >q;
 //default big top heap 
priority_queue< int > a;

  • Insert and delete

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <string>

using namespace std;

class  cmp { 
    /* on the left (that is, at the end of the queue), the lower the priority
     * The default is less, the lower the priority of decimals on the left
     * Optional greater, larger numbers on the left have lower priority
     *
     * */ 
    bool  operator  () ( int a, int b) {
         return a<b; //The small one is placed on the left, that is, less
    }
};

class  cmp2 { 
    bool  operator  () ( int a, int b) {
         return a>b; //The big one is placed on the left, that is, greater
    }
};

int main(){
    priority_queue<int,vector<int>,cmp> pq;
    pq.push(4);
    pq.push(8);
    pq.push(1);
    pq.push(5);

    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
}

queue

  • front(): Returns a reference to the first element in the queue.
  • back(): Returns a reference to the last element in the queue.
  • push(const T& obj): Add a copy of the element to the end of the queue.
  • pop(): removes the first element in the queue.
  • emplace(): Generate an object at the end of the queue.

priority_queue

Priority queue, the bottom layer is the heap:

dec.pop_back();   //remove tail 
dec.pop_front();   //delete head

//iterator erase (iterator position);
dec.erase(dec.begin());
//iterator erase (iterator first, iterator last);
dec.erase(dec.end()-3, dec.end());

The big top heap is the largest root element

The default method is the same as queue, but it has its own sorting method. Add the sorting method of priority_queue.

dec.back();   //return the last element 
    dec.front();   //return the first element

therefore

therefore

  • insert

  • delete

dec.pop_back();   //remove tail 
dec.pop_front();   //delete head

//iterator erase (iterator position);
dec.erase(dec.begin());
//iterator erase (iterator first, iterator last);
dec.erase(dec.end()-3, dec.end());

  • get element

dec.back();   //return the last element 
    dec.front();   //return the first element

Leave a Comment

Your email address will not be published. Required fields are marked *