Руководство по стандартной библиотеке шаблонов (STL)

Адаптеры

Адаптеры - шаблонные классы, которые обеспечивают отображения интерфейса. Например, insert_iterator обеспечивает контейнер интерфейсом итератора вывода.

Адаптеры контейнеров (Container adaptors)

Часто бывает полезно обеспечить ограниченные интерфейсы контейнеров. Библиотека предоставляет stack, queue и priority_queue через адаптеры, которые могут работать с различными типами последовательностей.

Стек (Stack)

Любая последовательность, поддерживающая операции back, push_back и pop_back, может использоваться для модификации stack. В частности, могут использоваться vector, list и deque.

template <class Container>
class stack {
friend bool operator==(const stack<Container>& х, const stack<Container>& y);
friend bool operator<(const stack<Container>& х, const stack<Container>& y);
public:
	typedef Container::value_type value_type;
	typedef Container::size_type size_type;
protected:
	Container c;
public:
	bool empty() const { return c.empty(); }
	size_type size() const { return c.size(); }
	value_type& top() { return c.back(); }
	const value_type& top() const { return c.back(); }
	void push(const value_type& х) { с.push_back(х); }
	void pop() { c.pop_back(); }
 };

template <class Container>
bool operator==(const stack <Container>& х, const stack<Container>& y)
	{ return х.с == у.с;}

template <class Container>
bool operator<(const stack<Container>& х, const stack<Container>& y) 
	{ return х.с < у.с; }

Например, stack<vector<int> > - целочисленный стек, сделанный из vector, а stack<deque<char> > - символьный стек, сделанный из deque.

Очередь (Queue)

Любая последовательность, поддерживающая операции front, push_back и pop_front, может использоваться для модификации queue. В частности, могут использоваться list и deque.

template <class Container>
class queue {
	friend bool operator==(const queue<Container>& х, const queue<Container>& y);
	friend bool operator<(const queue<Container>& х, const queue<Container>& y);
public:
	typedef Container::value_type value_type;
	typedef Container::size_type size_type;
protected:
	Container c;
public:
	bool empty() const { return c.empty(); }
	size_type size() const { return c.size(); }
	value_type& front() { return c.front(); }
	const value_type& front() const { return c.front(); }
	value_type& back() { return c.back(); }
	const value_type& back() const { return c.back(); }
	void push(const value_type& х) { с.push_back(х); }
	void pop() { с.pop_front(); }
};

template <class Container>
	bool operator==(const queue<Container>& х, const queue<Container>& y) 
	{ return х.с == у.с;}

template <class Container>
	bool operator<(const queue<Container>& х, const queue<Container>& y) 
	{ return х.с < у.с; }

Очередь с приоритетами (Priority queue)

Любая последовательность, с итератором произвольного доступа и поддерживающая операции front, push_back и pop_front, может использоваться для модификации priority_queue. В частности, могут использоваться vector и deque.

template <class Container, class Compare = less<Container::value_type> > 
class priority_queue { 
public:
	typedef Container::value_type value_type;
	typedef Container::size_type size_type;
protected:
	Container c;
	Compare comp;
public:
	priority_queue(const Compare& х = Compare()) : c(), comp(х) {}
	template <class InputIterator>
	priority_queue(InputIterator first, InputIterator last,
		const Compare& х = Compare()) : c(first, last), comp(x) 
		{ make_heap(c.begin(), с.end(), comp); }
	bool empty() const { return c.empty(); }
	size_type size() const { return c.size(); }
	const value_type& top() const { return c.front(); }
	void push(const value_type& х) {
		c.push_back(х);
		push_heap(c.begin(), c.end(), comp);
	}
	void pop() {
		pop_heap(c.begin(), c.end(), comp);
		с.рор_bасk(); 
	} 
}; // Никакое равенство не обеспечивается

Адаптеры итераторов (Iterator adaptors)

Обратные итераторы (Reverse iterators)

Двунаправленные итераторы и итераторы произвольного доступа имеют соответствующие адаптеры обратных итераторов, которые выполняют итерации через структуру данных в противоположном направлении.Они имеют те же самые сигнатуры, как и соответствующие итераторы. Фундаментальное соотношение между обратным итератором и его соответствующим итератором i установлено тождеством &*(reverse_iterator(i)) == &*(i - 1). Это отображение продиктовано тем, что, в то время как после конца массива всегда есть указатель, может не быть допустимого указателя перед началом массива.

template <class BidirectionalIterator, class T, class Reference = T&,
	class Distance = ptrdiff_t> 
class reverse_bidirectionaiIterator
	: public bidirectional_iterator<T, Distance> {
	typedef reverse_bidirectional_iterator<BidirectionalIterator, T,
						Reference, Distance> self;
	friend bool operator==(const self& х, const self& y);
protected:
	BidirectionalIterator current;
public:
	reverse_bidirectional_iterator() {}
	reverse_bidirectional_iterator(BidirectionalIterator х) 
		: current(х) {}
	BidirectionalIterator base() { return current; }
	Reference operator*() const {
		BidirectionalIterator tmp = current;
		return *--tmp;
	}
	self& operator++() {
		--current;
		return *this;
	}
	self operator++(int) {
		self tmp = *this;
		--current;
		return tmp;
	}
	self& operator--() {
		++current;
		return *this;
	}
	self operator--(int) {
		self tmp = *this;
		++current;
		return tmp;
	}
};

template <class BidirectionalIterator, class T, class Reference, 
	class Distance>
inline bool operator==(
	const reverse_bidirectional_iterator<BidirectionalIterator, T,
						Reference, Distance>& x,
	const reverse_bidirectional_iterator<BidirectionalIterator,
						T, Reference, Distance>& y){ 
	return x.current == y.current;
}

template <class RandomAccessIterator, class T, class Reference = T&,
	class Distance = ptrdiff_t>
class reverse_iterator : public random_access_iterator<T, Distance>{
	typedef reverse_iterator<RandomAccessIterator, T, Reference,
				Distance> self;
	friend bool operator==(const self& x, const self& y);
	friend bool operator<(const self& x, const self& y);
	friend Distance operator-(const self& x, const self& y);
	friend self operator+(Distance n, const self& x);
protected:
	RandomAccessIterator current;
public:
	reverse_iterator() {}
	reverse_iterator(RandomAccessIterator x) : current (x) {}
	RandomAccessIterator base() { return current; }
	Reference operator*() const {
		RandomAccessIterator tmp = current;
		return *--tmp;
	}
	self& operator++() {
		--current;
		return *this;
	}
	self operator++(int) {
		self tmp = *this;
		--current;
		return tmp;
	}
	self& operator--() {
		++current;
		return *this;
	}
	self operator--(int) {
		self tmp = *this;
		++current;
		return tmp;
	}
	self operator+(Distance n) const {
		return self (current - n);
	}
	self& operator+=(Distance n) {
		current -= n;
		return *this;
	}
	self operator-(Distance n) const {
		return self(current + n);
	}
	self operator-=(Distance n) {
		current +- n;
		return *this;
	} 
	Reference operator[](Distance n) { return *(*this + n);}
};

template <class RandomAccessIterator, class T, class Reference, class Distance>
inline bool operator==(
	const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& x,
	const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& y) {
	return x.current == y.current;
}

template <class RandomAccessIterator, class T, class Reference, class Distance>
inline bool operator<(
	const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& x,
	const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& y) {
	return y.current < x.current;
}

template <class RandomAccessIterator, class T, class Reference, class Distance>
inline Distance operator-(
	const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& х,
	const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& y) {
	return y.current - x.current;
}

template <class RandomAccessIterator, class T, class Reference, class Distance>
inline reverse_iterator<RandomAccessIterator, T, Reference, Distance> operator+( 
	Distance n, 
	const reverse_iterator<RandomAccessIterator, T, Reference, Distance>& x) {
	return reverse_iterator<RandomAccessIterator, T, Reference, Distance> 
		(x.current - n);
}

Итераторы вставки (Insert iterators)

Чтобы было возможно иметь дело с вставкой таким же образом, как с записью в массив, в библиотеке обеспечивается специальный вид адаптеров итераторов, называемых итераторами вставки (insert iterators). С обычными классами итераторов
while (first != last) *result++ = *first++;

вызывает копирование диапазона [first, last) в диапазон, начинающийся с result. Тот же самый код с result, являющимся итератором вставки, вставит соответствующие элементы в контейнер. Такой механизм позволяет всем алгоритмам копирования в библиотеке работать в режиме вставки (insert mode) вместо обычного режима наложения записей.

Итератор вставки создаётся из контейнера и, возможно, одного из его итераторов, указывающих, где вставка происходит, если это ни в начале, ни в конце контейнера. Итераторы вставки удовлетворяют требованиям итераторов вывода. operator* возвращает непосредственно сам итератор вставки. Присваивание operator=(const T& х) определено для итераторов вставки, чтобы разрешить запись в них, оно вставляет х прямо перед позицией, куда итератор вставки указывает. Другими словами, итератор вставки подобен курсору, указывающему в контейнер, где происходит вставка. back_insert_iterator вставляет элементы в конце контейнера, front_insert_iterator вставляет элементы в начале контейнера, а insert_iterator вставляет элементы, куда итератор указывает в контейнере. back_inserter, front_inserter и inserter - три функции, создающие итераторы вставки из контейнера.

template <class Container>
class back_insert_iterator : public output_iterator {
protected:
	Container& container;
public:
	back_insert_iterator(Container& x) : container(x) {}
	back_insert_iterator <Container>&
	operator=(const Container::value_type& value) {
		container.push_back(value);
		return *this;
	}
	back_insert_iterator<Container>& operator*() { return *this; } 
	back_insert_iterator<Container>& operator++() { return *this; }
	back_insert_iterator<Container>& operator++(int) { return *this; }
};

template <class Container>
back_insert_iterator<Container> back_inserter(Container& x) { 
	return back_insert_iterator<Container>(x);
}

template <class Container>
class front_insert_iterator : public output_iterator {
protected:
	Container& container;
public:
	front_insert_iterator(Container& x) : container (x) {}
	front_insert_iterator<Container>&
	operator=(const Container::value_type& value) {
		container.push_front(value);
		return *this;
	}
	front_insert_iterator<Container>& operator*() { return *this; }
	front_insert_iterator<Container>& operator++() { return *this; }
	front_insert_iterator<Container>& operator++(int) { return *this;} 
};

template <class Container>
front_insert_iterator<Container> front_inserter(Container& x) { 
	return front_insert_iterator<Container>(х);
}

template <class Container>
class insert_iterator : public output_iterator {
protected:
	Container& container;
	Container::iterator iter;
public:
	insert_iterator(Container& x, Container::iterator i)
		: container (x), iter(i) {}
	insert_iterator<Container>& operator=(const Container::value_type& value) { 
		iter = container.insert(iter, value);
		++iter;
		return *this;
	}
	insert_iterator<Container>& operator*() { return *this; }
	insert_iterator<Container>& operator++() { return *this; }
	insert_iterator<Container>& operator++(int) { return *this; }
};

template <class Container, class Iterator>
insert_iterator&tl;Container> inserter(Container& x, Iterator i) {
	return insert_iterator<Container>(x, Container::iterator(i));
}

Адаптеры функций (Function adaptors)

Функциональные адаптеры работают только с классами функциональных объектов с определёнными типами параметров и типом результата.

Отрицатели (Negators)

Отрицатели not1 и not2 берут унарный и бинарный предикаты соответственно и возвращают их дополнения.

template <class Predicate>
class unary_negate : public unary_function<Predicate::argument_type, bool> {
protected:
	Predicate pred;
public:
	unary_negate(const Predicate& x) : pred(x) {}
	bool operator()(const argument_type& x) const { return !pred(x); }
};

template <class Predicate>
unary_negate<Predicate> not1(const Predicate& pred) { 
	return unary_negate<Predicate>(pred);
}

template <class Predicate>
class binary_negate : public binary_function<Predicate::first_argument_type,
		Predicate::second_argument_type, bool> {
protected:
	Predicate pred;
public:
	binary_negate(const Predicate& x) : pred(x) {}
	bool operator()(const first_argument_type& x,
			const second_argument_type& y) const {
		return !pred(x, y);
	}

};

template <class Predicate>
binary_negate<Predicate> not2(const Predicate& pred) {
	 return binary_negate<Predicate>(pred);
}

Привязки (Binders)

Привязки bind1st и bind2nd берут функциональный объект f двух параметров и значение x и возвращают функциональный объект одного параметра, созданный из f с первым или вторым параметром соответственно, связанным с х.

template <class Predicate>
class binder1st : public unary_function {
protected:
	Operation op;
	Operation::first_argument_type value;
public:
	binder1st(const Operation& x, const Operation::first_argument_type& y)
		: op(x), value(y) {}
	result_type operator()(const argument_type& x) const { 
		return op(value, x); 
	}
};

template <class Operation, class T>
binder1st<0peration> bind1st(const Operation& op, const T& x) {
	return binder1st<0peration>(op, Operation::first_argument_type(x));
}

template <class Operation>
class binder2nd : public unary_function<0peration::first_argument_type,
					Operation::result_type> {
protected:
	Operation op;
	Operation::second_argument_type value;
public:
	binder2nd(const Operation& x, const Operation::second_argument_type& y)
		: op(x), value(y) {}
	result_type operator()(const argument_type& x) const { 
		return op(x, value);
	}
};

template <class Operation, class T>
binder2nd<Operation> bind2nd(const Operation& op, const T& x) {
	return binder2nd<0peration>(op, Operation::second_argument_type(x));
}

Например, find_if(v.begin(), v.end(), bind2nd(greater<int>(), 5)) находит первое целое число в векторе v большее, чем 5; find_if(v.begin(), v.end(), bind1st(greater<int>(), 5)) находит первое целое число в v меньшее, чем 5.

Адаптеры указателей на функции (Adaptors for pointers to functions)

Чтобы позволить указателям на (унарные и бинарные) функции работать с функциональными адаптерами, библиотека обеспечивает следующее:

template <class Arg, class Result>
class pointer_to_unary_function : public unary_function<Arg, Result> {
protected:
	Result (*ptr)(Arg);
public:
	pointer_to_unary_function() {}
	pointer_to_unary_function(Result (*x)(Arg)) : ptr(x) {}
	Result operator()(Arg x) const { return ptr(x); } 
};

template <class Arg, class Result>
pointer_to_unary_function<Arg, Result> ptr_fun(Result (*x)(Arg)) { 
	return pointer_to_unary_function<Arg, Result>(x);
}

template 
class pointer_to_binary_function : public binary_function {
protected:
	Result (*ptr)(Arg1, Arg2);
public:
	pointer_to_binary_function() {}
	pointer_to_binary_function(Result (*x)(Arg1, Arg2)) : ptr(х) {}
	Result operator()(Arg1 x, Arg2 y) const { return ptr(x, y); }
};

template <class Arg1, class Arg2, class Result>
pointer_to_binary_function<Arg1, Arg2, Result>
ptr_fun(Result (*x)(Arg1, Arg2)) {
	return pointer_to_binary_function<Argl, Arg2, Result>(x);
}

Например, replace_if(v.begin(), v.end(), not1(bind2nd(ptr_fun(strcmp), "C")), "C++") заменяет все "С" на "C++" в последовательности v.

Системы трансляции, которые имеют множественный указатель на типы функций, должны обеспечить дополнительные шаблоны функций ptr_fun.

[ Назад ] [ Содержание ] [ Вперед ]

[ Главная ] [ Гостевая ]