Контейнери STL: карта. Частина 7

Ми роздивились простий приклад використання map<>, але використання такого контейнера вже істотно складніше послідовних контейнерів. контейнер карта<> (таблиця, відображення):

Містить впорядковані пари <ключ,значение>, де ключ і значення можуть належати до довільних типів. Для типу ключа повинна бути або зумовлена, або визначена користувачем операція порівняння;
Елементи з будь-яким значенням ключа повинні бути унікальні;
спроба додати (метод вставити()) до таблиці нову пару з вже наявним значенням ключа завершиться невдачею;
Операція додавання нової пари в таблицю повертає пару типу <итератор, bool>, у якій другий компонент (логічний second) вказує на успішність операції. Якщо він true, то перший компонент повертається результату (first) дає итератор доданого елемента. Якщо ж він false, то повертається итератор існуючого елемента з тим же ключем;
Операції індексації таблиці ( [ ] или at() ) вимагають в якості ключа будь-яке значення типу, певного для ключа;
операція індексації at(), при завданні ключа-параметра, відсутнього в складі елементів таблиці, викликаєвиняток;
навпаки, операція індексації [ ], при завданні ключа-параметра, відсутнього в складі елементів таблиці, виняток не викликає. (навпаки, навіть якщо індексація запрошені тільки з читання, додає до контейнера новий елемент з необхідним значенням ключа, але з нульовим полем значення);

Ці визначення можуть здатися мудрими, але все роз'яснить наступний приклад.

Перш уявлення прикладу, ми повинні підготувати деякі файли тестових даних для роботи з асоціативними контейнерами. Робота саме з об'ємними символьними даними демонструє всю міць використання таблиць STL. Як текстових даних ми підготуємо файли, містять англомовні оригінальні тексти кількох віршів Льюїса Керола.

Нітрохи не складніше використовувати і російськомовні тексти, але в цьому випадку вам доведеться працювати з класами wstring і локалізованими перетвореннями, що тільки збільшить громіздкість прикладів без збільшення їх змістовності.

Вам надано кілька текстів різної довжини для ґрунтовного тестування кодів цієї і наступних частин викладу (файли показані з підрахунком числа рядків їхніх текстів). Здесь, например, Humpty-Dumpty.txt - це текст з частини VI Humpty-Dumpty «Аліса в задзеркаллі».

30 Брат і сестра

11 Дурниця

34 Бармаглот

А Jabberwock.txt - це текст з частини VI Humpty-Dumpty «Аліса в задзеркаллі» - відоме в російськомовному варіанті вірш (у виконанні В. С. Висоцького): Про бійся Бармаглота, син! Він так Свірп і дик…

У нашому оригіналі (авторське, англомовному, для налагодження – Jabberwock.txt файл) цей текст виглядає так:

Twas brillig, і Холявко шорькі
Штрикав для наведення:
Все mimsy були Borogove,
Як мюмзики в мове.

«Стережіться Jabberwock, мій син!
Щелепи, які кусаються, клешні, які ловлять!
Остерігайтеся птиці Jubjub, і цуратися
Злопастний Брандашмиг!» …

текст, безумовно, синтаксично складний, що робить його прекрасним матеріалом для налагодження додатків. Вам надається відмінний матеріал для подальших самостійних експериментів!

Отже ... наш додаток буде підраховувати число входжень кожної з літер алфавіту в пропонований текст, используя карта<>:

#include <iostream> 
#include <sstream> 
#include <map> 
using namespace std;

int main(int argc, char **argv) {
	map< char, int > alphabet;

	while (cin) {
		string line;
		getline(cin, line);
		if (line.empty()) continue;
		istringstream ist(line); // строка как поток чтения
		char let;
		while ((let = ist.get()) && let != EOF) { // посимвольно
			pair< map< char, int >::iterator, bool > ret;
			ret = alphabet.insert(pair< char, int >(let, 1));
			// если неудача - буква уже присутствует:
			if (!ret.second) ret.first->second++;
		}
	}

	cout << "alphabet size = " << alphabet.size() << endl;
	// если буква найдена - вывести её:
	for (char c = 'a'; c <= 'z'; c++) {
		cout << c << "(";
		try { cout << alphabet.at(c); }
		catch (exception const& e) { cout << '-'; }
		cout << ") ";
	}
	cout << endl;

	cout << "alphabet size = " << alphabet.size() << endl;

	for (char c = 'a'; c <= 'z'; c++) {
		cout << c << "(" << alphabet[c] << ") ";
	}
	cout << endl;

	cout << "alphabet size = " << alphabet.size() << endl;
}

#include <iostream>

#include <sstream>

#include <map>

using namespace std;

int main(int argc, char **argv) {

map< char, int > alphabet;

while (cin) {

string line;

getline(cin, line);

if (line.empty()) continue;

istringstream ist(line); // строка как поток чтения

char let;

while ((let = ist.get()) && let != EOF) { // посимвольно

pair< map< char, int >::iterator, bool > ret;

ret = alphabet.insert(pair< char, int >(let, 1));

// если неудача - буква уже присутствует:

if (!ret.second) ret.first->second++;

}

cout << "alphabet size = " << alphabet.size() << endl;

// если буква найдена - вывести её:

for (char c = 'a'; c <= 'z'; c++) {

cout << c << "(";

try { cout << alphabet.at(c); }

catch (exception const& e) { cout << '-'; }

cout << ") ";

}

cout << endl;

cout << "alphabet size = " << alphabet.size() << endl;

for (char c = 'a'; c <= 'z'; c++) {

cout << c << "(" << alphabet[c] << ") ";

}

cout << endl;

cout << "alphabet size = " << alphabet.size() << endl;

}

контейнер карта<> - Не найкращий варіант для поставлених цілей: при знаходженні нової літери в тексті ми спробуємо додати її в якості ключа таблиці, але якщо ця літера вже присутній в таблиці, то спроба завершиться невдачею. В этом случае, після невдачі, ми, за індексом ключа, просто інкрементіруем число його входжень. І ось що ми повчає:

клас Карта C ++, STL контейнери, map для початківців — Brother_And_Sister.txt

Зверніть увагу як збільшився розмір таблиці після того, як в ній був індексуванням [ ] здійснений пошук (з читання!) відсутніх ключів ('Д', 'Z', 'Х').

Виникає питання: чому ви бачимо як size() такі значення як 44, 47, 50, 52, якщо ми спостерігаємо тільки розкладку по повторюваності 26 символів від 'a’ до 'Z'? відповідь проста: тому що в текст можуть входити символи пробілу, знаків пунктуації, заголовних літер, яких ми не спостерігаємо у видачі тесту.

Якщо скористатися такою новою можливістю стандарту C ++ 11, як списки ініціалізації, створення і ініціалізація таблиці може виглядати набагато простіше:

#include <iostream> 
#include <map> 
using namespace std;

int main(int argc, char **argv) {
	map< int, char > nums = {
		{ 1, 'a' },{ 3, 'b' },{ 5, 'c' },{ 7, 'd' }
	};
	for (auto i = nums.begin(); i != nums.end(); i++)
		cout << i->first << "->" << i->second << " ";
	cout << endl;
}

#include <iostream>

#include <map>

using namespace std;

int main(int argc, char **argv) {

map< int, char > nums = {

{ 1, 'a' },{ 3, 'b' },{ 5, 'c' },{ 7, 'd' }

};

for (auto i = nums.begin(); i != nums.end(); i++)

cout << i->first << "->" << i->second << " ";

cout << endl;

}

природно, все це стане компілюватиметься тільки при вказівці опцій компілятора для використання стандарту C ++ 11:

Зі сказаного вже має бути зрозуміло, що в якості ключа пошуку в таблиці може використовуватися будь-який тип, при обов'язковій умові, що для нього або визначена природна операція порівняння (int, float, string, ...), або ми самі визначимо таку призначену для користувача функцію, яка буде використовуватися для порівнянь. Кілька способів зробити це показані нижче:

#include <iostream> 
#include <map> 
using namespace std;

template< typename Map > void print_map(Map& m) {
	cout << "{ ";
	for (auto& p : m) // перебор всей таблицы
		cout << p.first << ':' << p.second << ' ';
	cout << "}" << endl;
}
// функция  сравнения:
bool great(int lhs, int rhs) { return lhs > rhs; }
// функтор сравнения:
struct classcomp {
	bool operator()(const int& lhs, const int& rhs) const {
		return lhs > rhs;
	}
};

int main(int argc, char **argv) {
	// таблица, сравнение по умолчанию
	map< int, int, less< int > > ml = {
		{ 1, 2 },{ 2, 3 },{ 3, 4 },{ 4, 5 }
	};
	print_map(ml); 
	// таблица с нашей great() функцией сравнения
	map< int, int, bool(*)(int, int) > mg1(great);
	mg1.insert(ml.begin(), ml.end());
	print_map(mg1);
	// таблица с классом-функтором
	map< int, int, classcomp > mg3(ml.begin(), ml.end());
	print_map(mg3);
}

#include <iostream>

#include <map>

using namespace std;

template< typename Map > void print_map(Map& m) {

cout << "{ ";

for (auto& p : m) // перебор всей таблицы

cout << p.first << ':' << p.second << ' ';

cout << "}" << endl;

}

// функция сравнения:

bool great(int lhs, int rhs) { return lhs > rhs; }

// функтор сравнения:

struct classcomp {

bool operator()(const int& lhs, const int& rhs) const {

return lhs > rhs;

}

};

int main(int argc, char **argv) {

// таблица, сравнение по умолчанию

map< int, int, less< int > > ml = {

{ 1, 2 },{ 2, 3 },{ 3, 4 },{ 4, 5 }

};

print_map(ml);

// таблица с нашей great() функцией сравнения

map< int, int, bool(*)(int, int) > mg1(great);

mg1.insert(ml.begin(), ml.end());

print_map(mg1);

// таблица с классом-функтором

map< int, int, classcomp > mg3(ml.begin(), ml.end());

print_map(mg3);

}

тут ми, змінивши функцію порівняння ключів, змінили порядок сортування елементів при розміщенні їх в таблиці. (У 2-му варіанті використовується функціональний об'єкт, функтор, роботі з якими буде присвячена окрема частина нашого розгляду.)

Дякую за неймовірний праця і допомога у вивченні С ++, однак тепер пішли непонятки. До сих пір нормально було в перебігу уроків. Перш ніж щось писати в якості прикладу, потрібно пояснити що це. Иначе, якщо приклад незрозумілий, то толку немає від навчання, тільки практика запам'ятовується і засвоюється. Ладний символ neupomyanutиy ^ Z (Ctrl-Z) вдається помітити на зображенні результату роботи програми з віршами в консолі і добре, якщо читач знає, що він означає кінець файлу для консолі, без його введення програма не працювала б (цикл не завершився б). Але в наступному прикладі пішло ще важче .

1) функтори не вивчались, що це невідомо і приклад зрозуміти неможливо, тому що там написано bool operator(), а ми так не робили жодного разу, після слова operator перед дужками завжди писали знак оператора (+, -, …). Хорошо, можна подумати, що напевно на увазі той знак, який знаходиться в вираженні після return. А в наступних рядках ще більш незрозуміло:

2) карта< int, int, менше > – це що? Було вивчено що map складається з пари ключ-значення, а less що тут робить і що таке less взагалі незрозуміло. По виду можна припустити що це якийсь шаблонний клас з параметром int. Але швидше за все він вказує порядок сортування за значенням ключа в убуванні або зростанні даних в контейнері map.

3) карта mg1(великий); – це не зрозуміло. Можна здогадуватися в тому чи іншому напрямку, тільки здогадки мало допомагають у таких справах. mg1(великий) – це конструктор з параметром функцією? Такий конструктор для map не вивчалось, і не тільки для map.

4) карта – приблизно те ж саме.

Підводячи підсумок можна сказати, що це за третій параметр з'явився при оголошенні об'єкту-контейнера map всередині кутових дужок? Видно по контексту, що він задає порядок сортування за значенням ключа, але достовірної інформації немає.

відповісти

8 думки про "Контейнери STL: карта. Частина 7”

Олексій говорить:
14.03.2016 at 14:14
Вийшла цікава і зрозуміла стаття.
А буде продовження – видалення, заміна, містить, пошук по ключу і ін.?
відповісти
Olej говорить:
14.03.2016 at 23:05
Обов'язково буде.
Це якась частина? 7-я?
Так вже готових є 16.
чекайте.
відповісти
Дмитро говорить:
09.05.2016 at 12:40
Дякую за неймовірний праця і допомога у вивченні С ++, однак тепер пішли непонятки. До сих пір нормально було в перебігу уроків. Перш ніж щось писати в якості прикладу, потрібно пояснити що це. Иначе, якщо приклад незрозумілий, то толку немає від навчання, тільки практика запам'ятовується і засвоюється. Ладний символ neupomyanutиy ^ Z (Ctrl-Z) вдається помітити на зображенні результату роботи програми з віршами в консолі і добре, якщо читач знає, що він означає кінець файлу для консолі, без його введення програма не працювала б (цикл не завершився б). Але в наступному прикладі пішло ще важче .
1) функтори не вивчались, що це невідомо і приклад зрозуміти неможливо, тому що там написано bool operator(), а ми так не робили жодного разу, після слова operator перед дужками завжди писали знак оператора (+, -, …). Хорошо, можна подумати, що напевно на увазі той знак, який знаходиться в вираженні після return. А в наступних рядках ще більш незрозуміло:
2) карта< int, int, менше > – це що? Було вивчено що map складається з пари ключ-значення, а less що тут робить і що таке less взагалі незрозуміло. По виду можна припустити що це якийсь шаблонний клас з параметром int. Але швидше за все він вказує порядок сортування за значенням ключа в убуванні або зростанні даних в контейнері map.
3) карта mg1(великий); – це не зрозуміло. Можна здогадуватися в тому чи іншому напрямку, тільки здогадки мало допомагають у таких справах. mg1(великий) – це конструктор з параметром функцією? Такий конструктор для map не вивчалось, і не тільки для map.
4) карта – приблизно те ж саме.
Підводячи підсумок можна сказати, що це за третій параметр з'явився при оголошенні об'єкту-контейнера map всередині кутових дужок? Видно по контексту, що він задає порядок сортування за значенням ключа, але достовірної інформації немає.
відповісти
1. Дмитро говорить:
  09.05.2016 at 12:45
  2) карта< int, int, менше >
  відповісти
2. Дмитро говорить:
  09.05.2016 at 12:45
  3) карта mg1(великий);
  відповісти
3. Дмитро говорить:
  09.05.2016 at 12:51
  код в коментах відображається не повністю. Жаль.
  відповісти
4. Дмитро говорить:
  09.05.2016 at 17:31
  Начебто розібрався благо інтернет під рукою.
  відповісти
  1. Olej говорить:
    12.05.2016 at 13:25
    До сих пір нормально було в перебігу уроків. Перш ніж щось писати в якості прикладу, потрібно пояснити що це.
    1. просто “досі” було тільки тому, що до сих пір було тільки квіточки – порушувалися тільки най-най елементарні поняття C ++. Зараз описуються вже досить просунуті засоби.
    2. з матлінгвістікі, теорії мов програмування відомо, що будь-який мова програмування не може бути описаний строго послідовно, і тому описуються вони рекурсивно: використовуючи конструкції, які ще не описувалися раніше. Это теорія.
    Якщо щось вам категорично не зрозуміло – пропустіть це, ви повернетеся до нього пізніше, при “2-м проході”, коли воно вже стане зрозумілим.

Контейнери STL: карта. Частина 7

8 думки про "Контейнери STL: карта. Частина 7”

залишити коментар Скасувати відповідь

Останні повідомлення

недавні коментарі

Статистика