Введение в STL, Standard Template Library
Эта статья написана для новичков в 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
|
|
LINUX