 |
Операции с ассоциативными контейнерами
|
|
|
|
Типичная операция – это ассоциативный поиск при помощи операции индексации([]).
mapped_type& operator[] (const key_type& K);
Операция индексации должна найти ключ. Когда ключ не находится, добавляется элемент по умолчанию. Таким образом, индексация может использоваться, если mapped_type имеет значение по умолчанию. Это является следствием того, что pair по умолчанию инициализируется значениями по умолчанию для типов её элементов. Элементы встроенных типов инициализируются нулями, а строки string – пустыми строками.
Пример 8.6.1.
map<string,int> m; Создан пустой контейнер
int x=m[“Иванов”]; Добавляется элемент с ключом “Иванов” и знечение 0.
m[“Петров”]=7; Добавляется элемент с ключом “Петров” и знечение 7.
int y=m[“Иванов”]; y будет иметь значение 0
int z=m[“Петров”]; z будет иметь тзначение 7
m[“Петров”]=9; Изменено значение элемента с ключем “Петров”
Пример 8.6.2. Подсчитать общую стоимость предметов, представленных в виде пар (название предмета,стоимость).
void InitMap(map<string,int,less<string>>& m)
{string name;
int cost=0;
while(cin>>name>>cost)
//выход по ^z(Ctrl+z)
m[name]+=cost;
}
Если вводятся несколько предметов с одинаковым названием, то стоимость суммируется. Это видно в последней строке.
void main(){
map<string,int,less<string>> ware;
InitMap(ware);
int total=0;
typedef map<string,int,less<string>>::const_iterator pware;
for(pware p=ware.begin();p!=ware.end();p++){
total+=(*p).second;
cout<<(*p).first<<‘\t’<<(*p).second<<‘\n’;}
cout<<“--------------\n”;
cout<<“total\t”<<total<<‘\n’
}
В этом примере используется определенная в STL функция сравнения less.
Для доступа к элементам контейнера map можно использовать также функции find (k), lower_bound (k), upper_bound (k), которые возвращают итератор, соответствующий элементу с ключом k или начало/конец последовательности элементов контейнера, имеющих ключ k.
|
|
|
Обычно конец последовательности – это итератор, указывающий на элемент, следующий за последним в последовательности. Если элемента с ключом k нет, возвращается итератор end().
Вводить значения в ассоциативный контейнер принято простым присваиванием с использованием индекса (см. пример 8.6.1).
m[“Петров”]=7;
Это гарантирует, что будет занесена соответствующая запись.
Также можно вставить элемент функцией insert() и удалить функцией erase(). Функция insert() пытается добавить в map пару типа <Key,T>. Вставка производится, только если в map не существует элемента с таким ключом. Возвращаемое значение – пара pair<iterator,bool>. Переменная типа bool принимает значение true, если элемент вставлен. Итератор указывает на элемент с заданным ключом.
Примеры 8.6.3. Типы пар ключ/значение указаны явно в конструкции pair<char,int>.
#include<iostream>
#include<map>
using namespace std;
void main(){
map<char,int> m;
int i;
for(i=0;i<10;i++)m.insert(pair<char,int>(‘A’+i,i));
char ch;
cin>>ch;
map<char,int>::iterator p;
//поиск
p=m.find(ch);
if(p!=m.end())cout<<(*p).second;
else cout<<“Не найден\n”;
}
Примеры 8.6.4. Используем функцию make_pair, которая создает пары объектов на основе типов данных своих параметров.
void main(){
map<char,int> m;
int i;
for(i=0;i<10;i++)m.insert(make_pair(char(‘A’+i),i));
//дальше также, как в примере 8.6.3
Так же, как и в других контейнерах, в ассоциативных контейнерах можно хранить создаваемые пользователем типы данных. Например, создадим map для хранения слов с соответствующими словами антонимами.
Примеры 8.6.5.
#include<iostream.h>
#include<map.h>
#include<string.h>
using namespace std;
class word {
string str;
public:
word(){str=“”;}
word(string s){str=s;}
string get(){return str;}
};
bool operator< (word a,word b){return (a.str<b.str);}
class opposite {
string str;
public:
opposite(){str=“”;}
opposite (string s){str=s;}
string get(){return str;}
};
void main(){
map<word,opposite> m;
m.insert(pair<word,opposite>(word(“хорошо”),opposite(“плохо”)));
//и т.д.
//поиск антонима по слову
string ss;
cin>>ss;
map<word,opposite>::iterator p;
p=m.find(word(ss));
|
|
|
if(p!=m.end())cout<<(*p).second.get();
else cout<<“Такого слова нет\n”;
}
Примеры 8.6.5. Используется контейнер multimap для хранения группы студентов
typedef multimap<string,STUDENT,less<string>> TGroup;
typedef TGroup::value_type TItem;
void PrintStudent(const TItem& s,bool printCourse=true)
{if(printCourse)cout<<s.first;
cout<<s.second<<endl;
}
void main(){
TGroup curs; //студенты курса
Включить всех студентов в контейнер, так как показано ниже
curs.insert(TItem(“АСУ-07-1”,STUDENT(“Иванов”,19,0)));
//Распечатать всех студентов курса
for(TGroup::iterator i=curs.begin(); i!=curs.end(); i++)
{PrintStudent(*i);}
//Распечатаь студентов только заданной группы
for(TGroup::iterator i=curs.lower_bound(“АСУ-07-1”);
(i!=curs.upper_bound(“АСУ-07-1”))&&(i!=curs.end());i++)
PrintStudent(*i,false);
}
Контейнеры set и multiset
Множества можно рассматривать как ассоциативные массивы, в которых значения не играют роли, так что мы отслеживаем только ключи. Шаблон класса контейнера set
template<class T,class Cmp=less<T>,
class Allocator =allocator <T> > class std::set{…};
Множество, как и ассоциативный массив, требует, чтобы для типа T существовала операция «меньше» (<). Оно хранит свои элементы отсортированными, так что перебор происходит по порядку.
Примеры 8.6.6. Множество объектов пользовательского класса
Пользовательский класс, объекты которого будут сохраняться в множестве
class STUDENT {
string name;
float grade;
public:
STUDENT (const string& name1=“”,
float grade1=-1.0):name(name1), grade(grade1){}
STUDENT (const STUDENT& Student){*this=Student;}
const string& GetName ()const{return name;}
float GetGrade ()const{return grade;}
void SetName (string& name1){name=name1;}
void SetGrade (float grade1){grade=grade1;}
STUDENT& operator= (const STUDENT& student)
{if(this!=&student){name=student.name; grade=student.grade;}
return *this;}
bool operator== (const STUDENT& student)const
{return(name==student.name);}
bool operator< (const STUDENT& student)const
{return(name<student.name;}
friend ostream& operator<< (ostream& os,const STUDENT& s)
{os<<s.GetName()<<“grade=”<<s.GetGrade()<<endl;
return os;
}
};
typedef set<STUDENT> STUDENT_SET1;
Класс с перегруженной операцией для сравнения объектов STUTENT по полю grade-рейтинг. Таким образом, студенты в контейнере будут упорядочены по рейтингу.
struct GRADE_COMPARE {
bool operator() (const STUDENT& s1,const STUDENT& s2)const
{return(s1.GetGrade()<s2.GetGrade();}
};
typedef multiset<STUDENT,GRADE_COMPARE>
STUDENT_SET2;
void main (){
Создается два множества
STUDENT_SET1 Set1;
STUDENT_SET2 Set2;
Помещаются студенты в контейнер Set1
Set1.insert(STUDENT(“Иванов”,35.5));
//и т.д.
Просматриваем контейнер Set1 и помещаем студентов в контейнер Set2,
for(STUDENT_SET1::iterator i=Set1.begin();i!=Set1.end();i++){
|
|
|
cout<<*i;
Set2.insert(*i);}
Просматриваем контейнер Set2
for(STUDENT_SET2::iterator i=Set2.begin;i!=Set2.end();i++)cout<<*i;
}
Объекты-функции
Объект-функция – это экземпляр класса, в котором перегружена операция «круглые скобки» (). В ряде случаев удобно заменить функции сравнения на объекты-функции. Когда объект-функция используется в качестве функции, то для её вызова используется operator().
Примеры 8.6.7. Сравнение двух целых
class less{
public:
bool operator()(int x,int y){return x<y;}
};
Можно сделать шаблон класса для сравнения данных любых типов.
template<class T> class less{
public:
bool operator()(const T& x,const T& y)const{return x<y;}};
Следует иметь в виду, что для типа T должна быть определена операция меньше(<).
В STL определены вспомогательные базовые классы, поддерживающие единое определение типов аргументов и типа возвращаемого значения для различных объектов функций с одним и двумя аргументами. Это шаблоны unary functions и binary_function, которые доступны при подключении заголовочного файла< functional >.
template<class Arg, class Result>struct unary_function {typedef Arg argument_type;typedef Result result_type;};Этот шаблон служит базовым для классов, в которых операция «круглые скобки» определена в формеresult_type operator()(argument_type) template<class Arg1, class Arg2, class Result> struct binary_function { typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; };Этот шаблон служит базовым для классов, в которых операция «круглые скобки» определена в формеresult_type operator()(first_argument_type,
second_argument_type)
В STL также определен шаблон less.
template<class T> struct less: public binary_function<T,T,bool>;
Этот шаблон используется для создания класса функции, проверяющей, меньше ли первый операнд второго.
8.8. Алгоритмы
Каждый алгоритм выражается шаблоном функции или набором шаблонов функций. Таким образом, алгоритм может работать с очень разными контейнерами, содержащими значения разнообразных типов. Алгоритмы, которые возвращают итератор, как правило, для сообщения о неудаче используют конец входной последовательности. Алгоритмы не выполняют проверки диапазона на их входе и выходе. Когда алгоритм возвращает итератор, это будет итератор того же типа, что и был на входе. Алгоритмы в STL реализуют большинство распространенных универсальных операций с контейнерами, такие как просмотр, сортировку, поиск, вставку и удаление элементов. Алгоритмы доступны при включении заголовочного файла <algorithm>
|
|
|
Ниже приведены имена некоторых наиболее часто используемых функций – алгоритмов STL.
|
|
|
