[C++] Standard Template Library Container: Others (ENG)

 

Set

#include <set>

int main()
{
    std::set<int> scores;
    scores.insert(20);
    scores.insert(100);

    for (std::set<int>::iterator it = scores.begin(); it != scores.end(); ++it)
    {
        std::cout << *it << std::endl;  // 20\n 100\n
    }

    return 0;
}

 

Set is a auto-sorted container. It stores non-duplicated keys as elements. It is based on binary search tree.

 

 

 

Queue

#include <queue>

int main()
{
    std::queue<std::string> studentNameQueue;
    studentNameQueue.push("Coco");
    studentNameQueue.push("Mocha");

    while (!studentNameQueue.empty())
    {
        std::cout << "Waiting student: " << studentNameQueue.front() << std::endl;
        studentNameQueue.pop();  // doesn't return a front data
    }

    return 0;
}

 

// queue<type> name;
std::queue<int> studentIDQueue;
std::queue<std::string> studentNameQueue;
std::queue<StudentInfo> studentInfoQueue;

 

// size_type size();
// returns the number of elements in the queue
int size = studentNameQueue.size();

// bool empty();
// if the queue is empty, it returns true
// if the queue is not empty, returns false
bool bEmpty = studentNameQueue.empty();

 

Queue is a First-in first-out (FIFO) structure.

 

 

 

Stack

#include <stack>

int main()
{
    std::stack<std::string> studentNameStack;
    studentNameStack.push("Coco");
    studentNameStack.push("Mocha");

    while (!studentNameStack.empty())
    {
        std::cout << studentNameStack.top() << std::endl;
        studentNameStack.pop();  // doesn't return a top data
    }

    return 0;
}

 

// stack<type> name;
std::stack<int> studentIDStack;
std::stack<std::string> studentNameStack;
std::stack<StudentInfo> studentInfoStack;

 

// size_type size();
// returns the number of elements in the stack
int size = studentNameStack.size();

// bool empty();
// if the stack is empty, it returns true
// if the stack is not empty, returns false
bool bEmpty = studentNameStack.empty();

 

 

 

List

#include <list>

int main()
{
    std::list<int> scores;
    scores.push_front(10);  // 10
    scores.push_front(20);  // 20, 10
    scores.push_back(30);   // 20, 10, 30

    return 0;
}

 

std::list<int> scores;
std::list<int>::iterator it = scores.begin();

// iterator insert(iterator position, const value_type& value);
scores.insert(it, 99);  // 99

// void push_front(const value_type& value);
scores.push_front(10);  // 10, 99

// void push_back(const value_type& value);
scores.push_back(50);   // 10, 99, 50

 

std::list<int> scores = { 20, 30, 40, 30, 25, 30, 70, 96 };
std::list<int>::iterator it = scores.begin();

// iterator erase(iterator position);
scores.erase(it);   // 30, 40, 30, 25, 30, 70, 96

// void remove(const value_type& value);
scores.remove(30);  // 40, 25, 70, 96

 

Pros

- The time when you insert or remove it takes: O(1)

- You can insert/remove wherever.

 

Cons

- Searching is quite slow.

- You can't access randomly.

- Discontiguous memory

 

 

 

Etc

multi-set

- allows duplicate key

- can't modify the element

 

multi-map

- allows duplicate key

 

deque

- stands for double-ended queue

- can insert and delete elements at both ends

 

priority-queue

- is a auto-sorted queue