Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
iakovlev.org

Введение в STL, Standard Template Library

By Scott Field

Эта статья написана для новичков в STL-программировании. Конкретные примеры помогут вам быстрее освоить эту предметную область. В основе STL лежит понятие контейнера . Контейнером может быть список , массив , алгоритм или что-то еще более сложно-составное. Цель STL заключается в многократном использовании компонентов , определенных заранее. STL - это часть C++ , стандартная его часть , которую не нужно отдельно инсталлировать и которая изначально встроена в сам компилятор. Начнем со списка - одного из самых простых контейнеров . Мы увидим как инициализировать список , подсчитать число его элементов , найти элементы в списке , удалить элемент . Мы увидим , что алгоритмы , которые могут работать в STL , можно разделить на 2 группы - которые работают только со списками , и алгоритмы , употребимые со всеми контейнерами. К стандартным STL-алгоритмам относятся алгоритмы сортировки , удаления , подсчета , сравнения , поиска , слияния обьектов . STL-итератор напоминает указатель , который используется для операций над контейнерами. Итератор определяет , какой тип операции выполнять над контейнером - чтение , запись , или то и другое . Он же определяет направление процесса в контейнере . Вы можете получить итератор на начало контейнера вызовом члена-функции begin(). Вы можете вызвать end() для получения последнего элемента контейнера .

Инициализация списка

STL-список можно определить так :
 	#include <string>
 	#include <list>
 	int main (void) {
 	list<string> Milkshakes;
 	} 
Здесь создается обьект класса-шаблона list<string>. Мы применим его для списка строк . Откомпилировать эту программу можно так :
 	g++ test1.cpp -o test1 
Для начала добавим несколько строк в этот список . Несколько слов о типе значения . Тип значения (value type) - тип обьекта список . В данном случае это строка , поскольку список будет хранить строки.

Добавление элементов в список с помощью функций push_back и push_front

 	#include <string>
 	#include <list>
 	int main (void) {
 	list<string> Milkshakes;
 	Milkshakes.push_back("Chocolate");
 	Milkshakes.push_back("Strawberry");
 	Milkshakes.push_front("Lime");
 	Milkshakes.push_front("Vanilla");
 	} 
Теперь мы имеем список из 4-х строк. Функция push_back() размещает обьект в конец списка , функция push_front() - в начало .

Функция empty()

Если список пуст , эта функция возвращает true . Пример :
 	#include <iostream.h>
 	#include <string>
 	#include <list>
 	int main (void) {
 	#define OK 0 
 	#define INFO 1
 	#define WARNING 2
 	int return_code;
 	list<string> InfoMessages;
 	list<string> WarningMessages;
 	// during a program these messages are loaded at various points
 	InfoMessages.push_back("Info: Program started");
 	// do work...
 	WarningMessages.push_back("Warning: No Customer records have been found");
 	// do work...
 	return_code = OK; 
 	if  (!InfoMessages.empty()) {          // there were info messages
 		InfoMessages.push_front("Informational Messages:");
 		// ... print the info messages list, we'll see how later
 		return_code = INFO;
 	}
 	if  (!WarningMessages.empty()) {       // there were warning messages
 		WarningMessages.push_front("Warning Messages:");
 		// ... print the warning messages list, we'll see how later
 		return_code = WARNING;              
 	}
 	// If there were no messages say so.
 	if (InfoMessages.empty() && WarningMessages.empty()) {
 		cout << "There were no messages " << endl;
 	}
 	return return_code;
 	} 

Обработка элементов списка в цикле

Следующий пример показывает , как перемещаться по элементам списка :
 	#include <iostream.h>
 	#include <string>
 	#include <list>
 
 	int main (void) {
 	list<string> Milkshakes;
 	list<string>::iterator MilkshakeIterator;
 
 	Milkshakes.push_back("Chocolate");
 	Milkshakes.push_back("Strawberry");
 	Milkshakes.push_front("Lime");
 	Milkshakes.push_front("Vanilla");
 
 	// print the milkshakes
 	Milkshakes.push_front("The Milkshake Menu");
 	Milkshakes.push_back("*** Thats the end ***");
 	for (MilkshakeIterator=Milkshakes.begin(); 
 			MilkshakeIterator!=Milkshakes.end(); 
 			++MilkshakeIterator) {
 		// dereference the iterator to get the element
 		cout << *MilkshakeIterator << endl;
 	}	
 	} 
В программе определяется итератор MilkshakeIterator. Устанавливаем его на первый элемент списка - Milkshakes.begin(). Затем сравниваем его со значением Milkshakes.end(). Функция end() сравнивает итератор с последним элементом контейнера . Итератор MilkshakeIterator переназначается в цикле . Данный стандартный контейнер-список не поддерживает вставку элемента на произвольную позицию списка , потому что он реализован как 2-связный список . Такую операцию можно реализовать в другом контейнере - векторе.

Обработка элементов списка с помощью for_each

Перемещаться по контейнеру можно и без итератора - для этого существует алгоритм for_each :
 	#include <iostream.h>
 	#include <string>
 	#include <list>
 	#include <algorithm>
 
 	PrintIt (string& StringToPrint) {
 	cout << StringToPrint << endl;
 	}
 
 	int main (void) {
 	list<string> FruitAndVegetables;
 	FruitAndVegetables.push_back("carrot");
 	FruitAndVegetables.push_back("pumpkin");
 	FruitAndVegetables.push_back("potato");
 	FruitAndVegetables.push_front("apple");
 	FruitAndVegetables.push_front("pineapple");
 
 	for_each  (FruitAndVegetables.begin(), FruitAndVegetables.end(), PrintIt);
 	} 
В цикле for_each для каждого обьекта вызывается наша функция PrintIt() . for_each реализует концепцию рангового итератора - iterator range.

Подсчет элементов с помощью count()

Алгоритмы count() и count_if() подсчитывают число обьектов в контейнере. Пример :
 	#include <list>
 	#include <algorithm>
 
 	int main (void) {
 	list<int> Scores;
 
 	Scores.push_back(100); Scores.push_back(80);
 	Scores.push_back(45); Scores.push_back(75);
 	Scores.push_back(99); Scores.push_back(100);
 
 	int NumberOf100Scores(0);	
 	count (Scores.begin(), Scores.end(), 100, NumberOf100Scores);
 
 	cout << "There were " << NumberOf100Scores << " scores of 100" << endl;
 	} 
В данном примере подсчитывается число обьектов , равных 100 , и вывод будет : There were 2 scores of 100

Подсчет элементов списка с помощью count_if()

count_if() - это пример обьекта-функции . Обьект-функция - это класс , в котором определен хотя бы один член - operator () . Она возвращает true или false. В следующем примере мы будем ссылаться на запись , включающую код продукта и описание продукта :
 	#include <string>
 	#include <list>
 	#include <algorithm>
 
 	const string ToothbrushCode("0003");
 
 	class IsAToothbrush {
 	public:  
 	bool operator() ( string& SalesRecord ) {
 		return SalesRecord.substr(0,4)==ToothbrushCode;
 	}	
 	};
 
 	int main (void) {
 	list<string> SalesRecords;
 
 	SalesRecords.push_back("0001 Soap");
 	SalesRecords.push_back("0002 Shampoo");
 	SalesRecords.push_back("0003 Toothbrush");
 	SalesRecords.push_back("0004 Toothpaste");
 	SalesRecords.push_back("0003 Toothbrush");
 
 	int NumberOfToothbrushes(0);	
 	count_if (SalesRecords.begin(), SalesRecords.end(), 
 				IsAToothbrush(), NumberOfToothbrushes);
 
 	cout << "There were " 
 		<< NumberOfToothbrushes 
 		<< " toothbrushes sold" << endl;
 	} 
В примере будут найдены 2 записи с кодом 0003 Здесь в качестве одного из аргументов count_if служит класс IsAToothbrush , оперетор которого возвращает true или false. Этот обьект является временным обьектом, который создает default-конструктор этого класса.

Еще один пример count_if()

Если нам нужно создать обьект-функцию , которая будет возвращать больше информации , чем true/false , нам нужно создать еще один конструктор в классе :
 	#include <iostream.h>
 	#include <string>
 	#include <list>
 	#include <algorithm>
 
 	class IsAToothbrush {
 	public:
 	IsAToothbrush(string& InToothbrushCode) : 
 		ToothbrushCode(InToothbrushCode) {}
 	bool operator() (string& SalesRecord) {
 		return SalesRecord.substr(0,4)==ToothbrushCode;
 	}	
 	private:
 	string ToothbrushCode; 	
 	};
 
 	int main (void) {
 	list<string> SalesRecords;
 
 	SalesRecords.push_back("0001 Soap");
 	SalesRecords.push_back("0002 Shampoo");
 	SalesRecords.push_back("0003 Toothbrush");
 	SalesRecords.push_back("0004 Toothpaste");
 	SalesRecords.push_back("0003 Toothbrush");
 
 	string VariableToothbrushCode("0003");
 
 	int NumberOfToothbrushes(0);	
 	count_if (SalesRecords.begin(), SalesRecords.end(), 
 				IsAToothbrush(VariableToothbrushCode),
 					NumberOfToothbrushes);
 	cout << "There were  "
 		<< NumberOfToothbrushes 
 		<< " toothbrushes matching code "
 		<< VariableToothbrushCode
 		<< " sold" 
 		<< endl;
 	} 
Вывод программы : There were 2 toothbrushes matching code 0003 sold Можно создать еще более сложный non-default-конструктор .

Поиск обьектов списка с помощью find()

Для поиска обьектов существуют find() и find_if() . Они работают в стиле iterator range. 2 итератора служат для обозначения начала и конца интервала.
 	#include <string>
 	#include <list>
 	#include <algorithm>
 
 	int main (void) {
 	list<string> Fruit;
 	list<string>::iterator FruitIterator;
 
 	Fruit.push_back("Apple");
 	Fruit.push_back("Pineapple");
 	Fruit.push_back("Star Apple");
 
 	FruitIterator = find (Fruit.begin(), Fruit.end(), "Pineapple");
 
 	if (FruitIterator == Fruit.end()) {  
 		cout << "Fruit not found in list" << endl; 
 	}
 	else {
 	cout << *FruitIterator << endl;
 	}
 	} 
Вывод программы : Pineapple

Поиск обьектов в списке с помощью find_if()

В следующем примере мы имеем запись , состоящую из 2-х полей - событие и время . Найдем первое событие которое произошло в 1997 .
 	#include <string>
 	#include <list>
 	#include <algorithm>
 
 	class EventIsIn1997 {
 	public:
 	bool operator () (string& EventRecord) {
 	// year field is at position 12 for 4 characters in EventRecord	
 	return EventRecord.substr(12,4)=="1997";
 	}  
 	};
 
 	int main (void) {
 	list<string> Events;
 
 	// string positions 0123456789012345678901234567890123456789012345	
 	Events.push_back("07 January  1995  Draft plan of house prepared");
 	Events.push_back("07 February 1996  Detailed plan of house prepared");
 	Events.push_back("10 January  1997  Client agrees to job");
 	Events.push_back("15 January  1997  Builder starts work on bedroom");
 	Events.push_back("30 April    1997  Builder finishes work");
 
 	list<string>::iterator EventIterator = 
 		find_if (Events.begin(), Events.end(), EventIsIn1997());
 
 	// find_if completes the first time EventIsIn1997()() returns true 
 	// for any object. It returns an iterator to that object which we 
 	// can dereference to get the object, or if EventIsIn1997()() never
 	// returned true, find_if returns end()
 	if (EventIterator==Events.end()) {  
 		cout << "Event not found in list" << endl; 
 	}
 	else {
 	cout << *EventIterator << endl;
 	}
 	} 
Вывод : 10 January 1997 Client agrees to job

Поиск последовательностей в списке с использованием search

Список для хранения символов можно определить так :
   list<char> Characters;
 Добавим несколько символов в список :
   Characters.push_back('\0');
   Characters.push_back('\0');
   Characters.push_back('1');
   Characters.push_back('2');
Определим , сколько в этом контейнере нулевых символов:
   int NumberOfNullCharacters(0);
   count(Characters.begin(), Characters.end(), '\0', NumberOfNullCharacters);
   cout << "We have " << NumberOfNullCharacters << endl;
 Найдем символ '1' :
   list<char>::iterator Iter;
   Iter = find(Characters.begin(), Characters.end(), '1');
   cout << "We found " << *Iter << endl; 
 Пример работы search :
 	#include <string>
 	#include <list>
 	#include <algorithm>
 
 	int main ( void ) { 
 
 	list<char> TargetCharacters;
 	list<char> ListOfCharacters;
 
 	TargetCharacters.push_back('\0');
 	TargetCharacters.push_back('\0');
 
 	ListOfCharacters.push_back('1');
 	ListOfCharacters.push_back('2');
 	ListOfCharacters.push_back('\0');
 	ListOfCharacters.push_back('\0');
 
 	list<char>::iterator PositionOfNulls = 
 		search(ListOfCharacters.begin(), ListOfCharacters.end(), 
 				TargetCharacters.begin(), TargetCharacters.end());
 
 	if (PositionOfNulls!=ListOfCharacters.end())
 		cout << "We found the nulls" << endl;
 	}	 
Вывод программы : We found the nulls search-алгоритм в данном случае определяет первую последовательность внутри другой последовательности . Параметрами search являются уже 2 итератора .

Сортировка списка с помощью sort()

Здесь используется функция сортировки , встроенная именно в список , в отличие от всех функций , которые были показаны до этого . Данный вариант адаптирован под список для оптимизации .
 	#include <string>
 	#include <list>
 	#include <algorithm>
 
 	PrintIt (string& StringToPrint) { cout << StringToPrint << endl;}
 
 	int main (void) {
 	list<string> Staff;
 	list<string>::iterator PeopleIterator;
 
 	Staff.push_back("John");
 	Staff.push_back("Bill");
 	Staff.push_back("Tony");
 	Staff.push_back("Fidel");
 	Staff.push_back("Nelson"); 
 
 	cout << "The unsorted list " << endl;
 	for_each(Staff.begin(), Staff.end(), PrintIt );
 
 	Staff.sort();
 
 	cout << "The sorted list " << endl;
 	for_each(Staff.begin(), Staff.end(), PrintIt); 
 	} 
 Вывод:
 	The unsorted list 
 	John
 	Bill
 	Tony
 	Fidel
 	Nelson
 	The sorted list 
 	Bill
 	Fidel
 	John
 	Nelson
 	Tony

Вставка элементов в список с помощью insert()

Функция может вставлять в произвольную позицию контейнера как один обьект , так и несколько :
 	#include <list>
 
 	int main (void) {
 	list<int> list1;
 
 	/*
 	|| Put integers 0 to 9 in the list
 	*/
 	for (int i = 0; i < 10; ++i)  list1.push_back(i);   
 
 	/*
 	|| Insert -1 using the insert member function
 	|| Our list will contain -1,0,1,2,3,4,5,6,7,8,9
 	*/
 	list1.insert(list1.begin(), -1); 
 
 	/*
 	|| Insert an element at the end using insert
 	|| Our list will contain -1,0,1,2,3,4,5,6,7,8,9,10
 	*/
 	list1.insert(list1.end(), 10);
 
 	/*
 	|| Inserting a range from another container
 	|| Our list will contain -1,0,1,2,3,4,5,6,7,8,9,10,11,12
 	*/
 	int IntArray[2] = {11,12};
 	list1.insert(list1.end(), &IntArray[0], &IntArray[2]);
 
 	/*
 	|| As an exercise put the code in here to print the lists!
 	|| Hint: use PrintIt and accept an interger
 	*/
 	} 

Конструкторы списков

Можно список определить так :
   list<int> Fred; 
 Можно так :
   // define a list of 10 elements and initialise them all to 0
   list<int> Fred(10, 0);
   // list now contains 0,0,0,0,0,0,0,0,0,0
 А можно так - вставка с помощью вектора :
   vector<int> Harry;
   Harry.push_back(1); 
   Harry.push_back(2); 
   // define a list and initialise it with the elements in Harry
   list<int> Bill(Harry.begin(), Harry.end());
   // Bill now contains 1,2

Удаление элементов из списка

Функция pop_front() удаляет первый обьект. pop_back() удаляет последний. erase() удаляет обьект , на который указывает итератор.
 	#include <list>
 
 	int main (void) {
 	list<int> list1;   // define a list of integers
 
 	/*
 	|| Put some numbers in the list
 	|| It now contains 0,1,2,3,4,5,6,7,8,9
 	*/
 	for (int i = 0; i < 10; ++i)  list1.push_back(i);
 
 	list1.pop_front();    // erase the first element 0
 
 	list1.pop_back();     // erase the last element 9
 
 list1.erase(list1.begin());  // erase the first element (1) using an iterator
 
 list1.erase(list1.begin(), list1.end());  // erase all the remaining elements
 
 cout << "list contains " << list1.size() << " elements" << endl;
 	} 
Вывод : list contains 0 elements

Удаление элементов из списка с помощью remove()

Эта функция удаляет обьекты из списка :
 	#include <string>
 	#include <list>
 	#include <algorithm>
 
 	PrintIt (const string& StringToPrint) {
 	cout << StringToPrint << endl;
 	}
 
 	int main (void) {
 	list<string> Birds;
 
 	Birds.push_back("cockatoo");
 	Birds.push_back("galah");
 	Birds.push_back("cockatoo");
 	Birds.push_back("rosella");
 	Birds.push_back("corella");
 
 	cout << "Original list with cockatoos" << endl;
 	for_each(Birds.begin(), Birds.end(), PrintIt); 
 
 	Birds.remove("cockatoo"); 
 
 	cout << "Now no cockatoos" << endl;
 	for_each(Birds.begin(), Birds.end(), PrintIt); 
 	  
 	} 
 Вывод :
 	Original list with cockatoos
 	cockatoo
 	galah
 	cockatoo
 	rosella
 	corella
 	Now no cockatoos
 	galah
 	rosella
 	corella

Удаление из списка

В отличие от предыдущего примера , где использовалась встроенная в list функция remove(), здесь используется базовая функция remove() .
 	#include <string>
 	#include <list>
 	#include <algorithm>
 
 	PrintIt(string& AString) { cout << AString << endl; }
 
 	int main (void) {
 	list<string> Birds;
 	list<string>::iterator NewEnd;
 
 	Birds.push_back("cockatoo");
 	Birds.push_back("galah");
 	Birds.push_back("cockatoo");
 	Birds.push_back("rosella");
 	Birds.push_back("king parrot");
 
 	cout << "Original list" << endl; 
 	for_each(Birds.begin(), Birds.end(), PrintIt);
 
 	NewEnd = remove(Birds.begin(), Birds.end(), "cockatoo"); 
 
 	cout << endl << "List according to new past the end iterator" << endl; 
 	for_each(Birds.begin(), NewEnd, PrintIt);
 
 	cout << endl << "Original list now. Care required!" << endl; 
 	for_each(Birds.begin(), Birds.end(), PrintIt);
 	} 
 Вывод :
 	Original list
 	cockatoo
 	galah
 	cockatoo
 	rosella
 	king parrot
 	
List according to new past the end iterator galah rosella king parrot
Original list now. Care required! galah rosella king parrot rosella king parrot

Разбиение списка с помощью базовой функции stable_partition() и встроенной splice()

stable_partition() переопределяет список так , что вначале становятся его элементы , которые отвечают определенному условию . Splice добавляет элементы одного списка в другой . В следующем примере в командной строке нужно набрать 6 параметров после имени программы . Также используются флаги :
 	#include <string>
 	#include <list>
 	#include <algorithm>
 
 	PrintIt ( string& AString ) { cout << AString << endl; }
 
 	class IsAFlag {
 	public: 
 	bool operator () (string& PossibleFlag) {
 		return PossibleFlag.substr(0,1)=="-";
 	}
 	};
 
 	class IsAFileName {
 	public:  
 	bool operator () (string& StringToCheck) {
 		return !IsAFlag()(StringToCheck);
 	}
 	};
 
 	class IsHelpFlag {
 	public:  
 	bool operator () (string& PossibleHelpFlag) {
 		return PossibleHelpFlag=="-h";
 	}
 	};
 
 	int main (int argc, char *argv[]) {
 
 	list<string> CmdLineParameters;       // the command line parameters
 	list<string>::iterator StartOfFiles;  // start of filenames 
 	list<string> Flags;                   // list of flags
 	list<string> FileNames;               // list of filenames
 
 	for (int i = 0; i < argc; ++i) CmdLineParameters.push_back(argv[i]);
 
 	CmdLineParameters.pop_front(); // we don't want the program name
 
 	// make sure we have the four mandatory file names
 	int NumberOfFiles(0);
 	count_if(CmdLineParameters.begin(), CmdLineParameters.end(), 
 		IsAFileName(), NumberOfFiles);
 
 	cout << "The " 
 		<< (NumberOfFiles == 4 ? "correct " : "wrong ")
 		<< "number (" 
 		<< NumberOfFiles 
 		<< ") of file names were specified" << endl;
 
 	// move any flags to the beginning
 	StartOfFiles = 
 	stable_partition(CmdLineParameters.begin(), CmdLineParameters.end(), 
 			IsAFlag()); 
 
 	cout << "Command line parameters after stable partition" << endl;
 	for_each(CmdLineParameters.begin(), CmdLineParameters.end(), PrintIt);
 
 // Splice any flags from the original CmdLineParameters list into Flags list. 
 	Flags.splice(Flags.begin(), CmdLineParameters,
 		CmdLineParameters.begin(), StartOfFiles);
 
 	if (!Flags.empty()) {
 	cout << "Flags specified were:" << endl;
 	for_each(Flags.begin(), Flags.end(), PrintIt);
 	}
 	else {
 	cout << "No flags were specified" << endl;
 	} 
 
 // parameters list now contains only filenames. Splice them into FileNames list.
 	FileNames.splice(FileNames.begin(), CmdLineParameters, 
 		CmdLineParameters.begin(), CmdLineParameters.end());
 
 	if (!FileNames.empty()) {
 	cout << "Files specified (in order) were:" << endl;
 	for_each(FileNames.begin(), FileNames.end(), PrintIt);
 	}
 	else {
 	cout << "No files were specified" << endl;
 	} 
 
 	// check if the help flag was specified
 	if (find_if(Flags.begin(), Flags.end(), IsHelpFlag())!=Flags.end()) {
 	cout << "The help flag was specified" << endl;
 	}
 
 	// open the files and do whatever you do
 
 	} 
 Командная строка :
 	test17 -w linux -o is -w great
 Вывод :
 	The wrong number (3) of file names were specified
 	Command line parameters after stable partition
 	-w
 	-o
 	-w
 	linux
 	is
 	great
 	Flags specified were:
 	-w
 	-o
 	-w
 	Files specified (in order) were:
 	linux
 	is
 	great 
Copyright © 1998, Scott Field
Published in Issue 34 of Linux Gazette, November 1998
Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье