Using STL list, map and set container

C++ 的標準函式庫 (tw) 中提供多種方便的 容器 (cplusplus) 類別, 因為物件化的系統中你除了實作很多自己定義的物件之外, 當有方便好用的工具物件提供給你的時候你也要盡量去使用它, 如此才能夠提昇撰寫軟體的效率

vector 類別是一個能夠自動管理記憶體的循序性容器, 能夠很有效率地在容器的尾端新增和刪除元素, 物件內資料存放在連續的記憶體中, 能夠迅速存取區段中任意元素, 雖然也提供 insert 和 erase 的功能, 能夠在任意地方新增一個元素, 也能夠刪除其中某一元素, 但是效率不會太好

deque 類別的功能很像 vector 類別, 但是額外提供一個功能, 可以很有效率地在容器的最前端新增和刪除元素, 物件內資料存放在一個一個頁面中

list

在 C++ 的標準函式庫 (tw) 中, list (list members) (cplusplus) 是一個運用起來很方便的循序容器 (Sequential Container) 類別, 與 vector 和 deque 最大的差別在於可以很有效率地在任意位置新增或是刪除元素, 可以省掉你自己實作一個「串列」資料結構的時間, 因為串列並沒有辦法根據在容器中的位置迅速算出資料存放的記憶體位址, 所以並不像 vector 或是 deque 提供 operator[] 的資料直接存取運算子

list 樣版容器類別的使用方法如下:

std::list<data_type> mylist;

std::list<data_type>::iterator iterator_name;

例如:

#include <list>
#include <algorithm> // find

    ...

std::list<int> int_list;

int_list.push_front(1);
int_list.push_front(2);

int_list.insert(int_list.end(), 3); // insert an element before the specified iterator

// bad idea
if (int_list.size() == 0)
    ...
// good idea
if (int_list.empty())
    ...

int_list.clear(); // guaranteed to be empty now

int_list.reverse();

int_list.push_back(1);
int_list.push_back(1);
int_list.push_back(8);
int_list.push_back(9);
int_list.push_back(7);
int_list.push_back(8);
int_list.push_back(2);
int_list.push_back(3);
int_list.push_back(3);

int_list.remove(8); // remove all elements that is 8

int_list.sort();
int_list.unique();

std::cout << "The first element of the list is " << int_list.front() << endl;
int_list.pop_front(); // remove the first element in the list.
std::cout << "The last element of the list is " << int_list.back() << endl;
int_list.pop_back(); // remove the last element in the list.

for (std::list<int>::iterator list_iter = int_list.begin(); 
        list_iter != int_list.end(); list_iter++)
{
    std::cout<<*list_iter<<endl;
    if (*list_iter==2) int_list.erase(list_iter);
}
int_list.erase(int_list.begin(), int_list.end());

// initialization of a sequence container from a C int array
int data[] = {9, 2, 8, 11, 35};
std::list<int> mylist(data, data+5); 

std::list<int>::iterator it = find(mylist.begin(), mylist.end(), 11);
mylist.insert(it, 10);

map

在 C++ 的標準函式庫 (tw) 中, map (map Members) 是一個運用起來很方便的關連性容器 (Associative Container, Associative Array, Content Addressable Memory) 類別, 如果你需要維護一堆資料, 需要隨時加入資料, 需要隨時取出指定的資料, 而且資料的數量還沒有大到需要運用資料庫來處理的話, 可以考慮使用這種容器。

map 樣板容器類別的基本使用方法如下:

std::map <key_type, data_type, [comparison_function]>

key_type 需要定義 less-than operator, 也就是 bool operator<(key_type), 否則就需要提供 comparison_function, 這是一個函式或一個 functor (一個有定義 function call operator 的類別的物件, 這種物件使用起來就像是一個函式一樣)

map 容器底層常常是用 binary search tree 來實作的, 每一個節點的資料是一個 pair<key_type, data_type> 的物件:

常常用 value_type 來存取 (typedef pair<const key_type, data_type> value_type;)

例如:

std::map<string, char> grade_list;
		  
grade_list["John"] = 'B';
...
grade_list["John"] = 'A'; // John's grade improves

grade_list.erase("John");

std::cout<<"The class is size "<<grade_list.size()<<std::endl;

if (!grade_list.empty()) ...

grade_list.clear(); // remove all records from the grade_list

 // 這是 binary search, 請不要用 algorithm 裡面的 find(), 沒有效率
if (grade_list.find("Tim") == grade_list.end())
{
    std::cout<<"Tim is not in the map!"<<endl;
}

std::map<string, char>::iterator glIter;
for (glIter=grade_list.begin(); glIter!=grade_list.end(); glIter++)
{
    std::cout<<glIter->first<<endl;  //  "John"
    std::cout<<glIter->second<<endl; //  'A'
}

Exercise:

Find the most frequently occurring substring of a specified length from a given string.

Input

1 thequickbrownfoxjumpsoverthelazydog
3 thequickbrownfoxjumpsoverthelazydog
4 testingthecodetofindtheerrortestandtestagain
5 thearraycanbetoobigsobecarefulandtherecantberarecasescanbe

Output

o:4
the:2
test:3
canbe:2

#include <cstdio>
#include <cstring> // strlen()
#include <string>
#include <map>
using namespace std;

char s[1000001];

int main() {
    int N;
    map<long long, int> cont;
    
    while (scanf("%d%s",&N,s) == 2) 
    {
        int L = strlen(s);
        cont.clear();
        
        for (int i=0; i+N<=L; ++i) 
        {
            long long aux = 0;
            
            for (int j=0; j<N; ++j)
                aux = aux*26 + (s[i+j]-'a');
            
            cont[aux]++;
        }
        
        long long ans_hash;
        int best = -1;
        
        for (map<long long, int>::iterator it=cont.begin(); it!=cont.end(); ++it)
        {
            if (it->second > best) 
            {
                ans_hash = it->first;
                best = it->second;
            }
        }
        
        string ans;
        
        for (int i=0; i<N; ++i)
        {
            ans = (char)(ans_hash % 26 + 'a') + ans;
            ans_hash /= 26;
        }
        
        printf("%s:%d\n", ans.c_str(), best);
    }
    
    return 0;
}

這個程式在 N<=13 時才可以得到正確答案, 為什麼?

bool mystrcmp(const char* str1, const char* str2)
{
    return strcmp(str1, str2)<0;
}
map<char*, int, bool (*)(const char*, const char*)> conv1(mystrcmp);

class MyCompare
{
public:
    bool operator()(char *&str1, char *&str2) const 
    {
        return (strcmp(str1,str2)<0);
    }
};
map<char*, int, MyCompare> conv2;

該怎麼修改才能讓程式在 N = 25 時還能夠運作?

set

在 C++ 的標準函式庫 (tw) 中, set (set Members) 是一個運用起來很方便的關連性容器 (Associative Container) 類別

set 樣板容器類別的定義如下:

template < class T, // set::key_type/value_type
                      class Compare = less<T>, // set::key_compare/value_compare
                      class Alloc = allocator<T> // set::allocator_type
                  > class set;

如果類別 T 沒有提供比較的 operator< 函式的話, 就需要提供 Compare 物件或是函式

例如:

#include <set>
#include <string>
#include <iostream>
using namespace std;

class Student
{
    friend class Comp;
public:
    Student(int num1, string name1):num(num1), name(name1) {}
    void print(ostream &os) {os << num << "\t" << name << endl;}
private:
    int num;
    string name;
};

class Comp
{
public:
    bool operator()(Student s1, Student s2)
    {
        if (s1.num < s2.num)
            return true;
        else
            return false;
    }
};

int main()
{
    set<Student, Comp> myStudents;

    Student a1(10, "Anwar"), a2(5, "Ziale"), a3(17, "Tauman");
    myStudents.insert(a1);
    myStudents.insert(a3);
    myStudents.insert(a2);
    myStudents.insert(a1); // would merge together

    cout << "The number of students " << myStudents.size() << endl;

    set<Student, Comp>::iterator iter;
    for (iter=myStudents.begin(); iter != myStudents.end(); iter++)
        iter->print(cout);

    iter = myStudents.find(Student(17, ""));
    if (iter != myStudents.end())
        iter->print(cout);
    else
        cout << "Not found!" << endl;
    return 0;
}

/*
The number of students 3
5       Ziale
10      Anwar
17      Tauman
17      Tauman
*/

VC2010 STL

Sequence Container

在 C++ 的標準函式庫 (tw) 中包含下列的循序性容器 (Sequence Container) 類別:

1. deque (double-ended queue): members
   
   
2. list: members
   
   
3. vector: members

Contents of deque and vector can be efficiently random accessed.

Associative Container

在 C++ 的標準函式庫 (tw) 中包含下列的關連性容器 (Associative Container) 類別:

1. map: members
   Each stored element is a pair that has both a data value and a sort key. The value of the key is unique and is used to automatically sort the data.
   The value of an element in a map can be changed directly. The key value is a constant and cannot be changed. Instead, key values associated with old elements must be deleted, and new key values must be inserted for new elements.
   
   
2. multimap: members
   Each element is a pair that has both a data value and a sort key. The value of the key does not need to be unique and is used to order the data automatically. The value of an element in a multimap, but not its associated key value, may be changed directly. Instead, key values associated with old elements must be deleted and new key values associated with new elements inserted.
   
3. hash_map: members
   Extension of map and is used for storage and fast retrievall of data from a collection in which each element is a pair that has a sort key whose value is unique and an associated data value.
   
   
4. hash_multimap: members
   Extension of multimap and is used for the storage and fast retrieval of data from a collection in which each element is a pair that has a sort key whose value need not be unique and an associated data value.
   
5. set: members
   The key values of the elements contained are unique and serve as the key values according to which the data is automatically ordered. The value of an element in a set may not be changed directly. Instead, you must delete old values and insert elements with new values.
   
   
6. multiset: members
   The key values of the elements contained need not be unique and in which they serve as the key values according to which the data is automatically ordered. The key value of an element in a multiset may not be changed directly. Instead, old values must be deleted and elements with new values inserted.
   
   
7. hash_set: members
   Extension of set and is used for the storage and fast retrieval of data from a collection in which the values of the elements contained are unique and serve as the key values.
   
   
8. hash_multi_set: members
   Extension of the multiset and is used for the storage and fast retrieval of data from a collection in which the values of the elements contained serve as the key values and are not required to be unique.
   

Container Adapter

在 C++ 的標準函式庫 (tw) 中包含下列的衍生容器 (Container Adapter) 類別:

1. priority queue: members
   It organized such that the element with the highest value is always first in the queue.
   
   
2. queue: members
   It follows FIFO (first in, first out) semantics. The first element inserted (pushed) into the queue is the first to be removed (popped).
   
   
3. stack: members
   It follows LIFO (last in, first out) semantics. The last element to be inserted (pushed) on the stack is the first element to be removed (popped).