Friday, September 04, 2009

A little about C++ Standard Template Library (STL)

به نام دوست

استفاده از توابع کتابخانه‌ای STL مزیتهای گوناگونی برای یک برنامه‌نویس و حتی برای کل پروژه به دنبال دارد. استفاده از کدهای موجود که با توجه به موضوع Performance سعی شده تا به خوبی پیاده‌سازی شوند و همچنین Bug Free بودن آنها از جمله موارد مطلوب در استفاده از این کتابخانه‌ها میباشد.

STL شامل مجموعه‌ای از ساختمان داده‌‌های رایج و تعدادی الگوریتمهای مرسوم برای پردازش داده‌های موجود در آنها میباشد. STL بر مبنای قابلیت Template در C++ نوشته شده است.

STLها به ۳ دسته تقسیم میشوند:
۱- Containors: ساختمان داده‌ها برای ذخیره‌سازی اطلاعات
۲- Iterators: ابزار جابه‌جایی بر روی اطلاعات و یا ابزار دسترسی به اطلاعات ساختمان داده‌ها
۳- Algorithms: ابزار پردازش اطلاعات ساختمان داده‌ها. این ابزار برای دسترسی به اطلاعات ساختمان‌داده‌ها از iteratorها استفاده میکنند
ساختمان‌داده‌‌ها نیز به سه دسته اصلی تقسیم میشوند: First Class, adapters , near Containors

۱- ساختمان داده‌ها (Containors)
انواع ساختمان‌داده‌های موجود به این شرح میباشند:

Standard Library container class

Description

Sequence containers

vector

rapid insertions and deletions at back direct access to any element

deque

rapid insertions and deletions at front or back direct access to any element

list

doubly linked list, rapid insertion and deletion anywhere

Associative containers

set

rapid lookup, no duplicates allowed

multiset

rapid lookup, duplicates allowed

map

one-to-one mapping, no duplicates allowed, rapid key-based lookup

multimap

one-to-many mapping, duplicates allowed, rapid key-based lookup

Container adapters

stack

last-in, first-out (LIFO)

queue

first-in, first-out (FIFO)

priority_queue

highest-priority element is always the first element out


نکته: ساختمان داده‌های Sequence Containers و Associative Containers به عنوان ساختمان‌داده‌‌های First Class شناخته میشوند.

هر ساختمان داده مجموعه‌ای از توابع را برای کار با آن در اختیار کاربر قرار میدهد، در این میان توابعی وجود دارند که در بین تمامی ساختمان داده‌ها مشترک میباشند. لیست این توابع به این شرح است:

Common member functions for all STL containers

Description

default constructor

A constructor to provide a default initialization of the container. Nor-mally, each container has several constructors that provide different initialization methods for the container.

copy constructor

A constructor that initializes the container to be a copy of an existing container of the same type.

destructor

Destructor function for cleanup after a container is no longer needed.

empty

Returns true if there are no elements in the container; otherwise, returns false.

size

Returns the number of elements currently in the container.

operator=

Assigns one container to another.

operator<

Returns true if the first container is less than the second container; otherwise, returns false.

operator<=

Returns TRue if the first container is less than or equal to the second container; otherwise, returns false.

operator>

Returns true if the first container is greater than the second con-tainer; otherwise, returns false.

operator>=

Returns true if the first container is greater than or equal to the sec-ond container; otherwise, returns false.

operator==

Returns true if the first container is equal to the second container; otherwise, returns false.

operator!=

Returns TRue if the first container is not equal to the second con-tainer; otherwise, returns false.

swap

Swaps the elements of two containers.

Functions found only in first-class containers

max_size

Returns the maximum number of elements for a container.

begin

The two versions of this function return either an iterator or a const_iterator that refers to the first element of the container.

end

The two versions of this function return either an iterator or a const_iterator that refers to the next position after the end of the container.

rbegin

The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the last element of the container.

rend

The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the next position after the last element of the reversed container.

erase

Erases one or more elements from the container.

clear

Erases all elements from the container.

Note: Overloaded operators operator<, operator<=, operator>, operator>=, operator== and operator!= are not provided for priority_queues.


برای Sequence Containers فانکشنهای مشترک دیگری به این شرح وجود دارد:
front: ارجاع به اولین عنصر Container را برمیگرداند
back: ارجاع به آخرین عنصر
push_back: درج یک عنصر در انتهای Container
pop_back: حذف یک عنصر از انتهای Container

در Containersها تعدادی typedef جهت راحتی(و یکسان سازی) کار با ساختمان‌داده‌ تعریف شده است. لیست این typedef ها به این شرح است:

typedef

Description

value_type

The type of element stored in the container.

reference

A reference to the type of element stored in the container.

const_reference

A constant reference to the type of element stored in the container. Such a reference can be used only for reading elements in the container and for performing const operations.

pointer

A pointer to the type of element stored in the container.

iterator

An iterator that points to the type of element stored in the container.

const_iterator

A constant iterator that points to the type of element stored in the container and can be used only to read elements.

reverse_iterator

A reverse iterator that points to the type of element stored in the container. This type of iterator is for iterating through a container in reverse.

const_reverse_iterator

A constant reverse iterator that points to the type of element stored in the container and can be used only to read elements. This type of iterator is for iterating through a container in reverse.

difference_type

The type of the result of subtracting two iterators that refer to the same container (operator - is not defined for iterators of lists and associative containers).

size_type

The type used to count items in a container and index through a sequence container (cannot index through a list).


نکته: هنگامی که یک عنصر به داخل ساختمان‌داده‌ insert میشود یک کپی از ان ایجاد میشود. بنابراین Type عناصر میبایست حداقل عملیات کپی(Copy Constructor) و عملیات انتساب(Assign Operator) را پشتیبانی کند. موارد ذکر شده حداقل قابلیتهای یک عنصر میباشد. باید توجه داشت که هر تایپ میبایست حداقل عملیات مورد نیاز در Containers مورد نظر که از یک ساختمان داده به دیگری متقاوت میباشد را پیاده‌سازی کند.

۲- تکرارکننده‌ها (Iterators)
تکرارکننده‌ها به پنج دسته تقسیم میشوند:

Category

Description

input

Used to read an element from a container. An input iterator can move only in the forward direction (i.e., from the beginning of the container to the end) one element at a time. Input iterators support only one-pass algorithms-the same input iterator cannot be used to pass through a sequence twice.

output

Used to write an element to a container. An output iterator can move only in the forward direction one element at a time. Output iterators support only one-pass algorithms-the same output iterator cannot be used to pass through a sequence twice.

forward

Combines the capabilities of input and output iterators and retains their position in the container (as state information).

bidirectional

Combines the capabilities of a forward iterator with the ability to move in the backward direction (i.e., from the end of the container toward the beginning). Bidirectional iterators support multipass algorithms.

random access

Combines the capabilities of a bidirectional iterator with the ability to directly access any element of the container, i.e., to jump forward or backward by an arbitrary number of elements.





قابل توجه است که الگوریتمها برای کار بر روی ساختمان‌داده‌‌ها نیاز به iteratorهای خاصی دارند و از طرف دیگر ساختمان‌داده‌‌ها نیز نوع خاصی از Iteratorها را پشتیبانی میکنند.
بنابراین شرط استفاده از یک الگوریتم بر روی یک ساختمان‌داده‌ پشتیبانی کردن از Iterator مورد نیاز آن الگوریتم توسط ساختمان‌داده‌ مورد نظر میباشد.
نکته دیگر اینکه هنگامی که یک ساختمان‌داده‌ از یک نوع Iterator پشتیبانی میکند، قابلیت کار با ساختمان‌داده‌ با استفاده از Iteratorهای با قدرت کمتر از Iterator پشتیبانی شده وجود دارد.

در جدول زیر مشخص شده است که هر ساختمان داده از چه نوع تکرار کننده‌ای حمایت میکند:

Container

Type of iterator supported

Sequence containers (first class)

vector

random access

deque

random access

list

bidirectional

Associative containers (first class)

set

bidirectional

multiset

bidirectional

map

bidirectional

multimap

bidirectional

Container adapters

stack

no iterators supported

queue

no iterators supported

priority_queue

no iterators supported



جدول زیر عملگرهای تکرارکننده‌ها را نمایش میدهند. قابل توجه است که در این جدول هر تکرارکننده‌ عملگرهای تکرارکننده‌ قبل خود را نیز شامل میشود.

Iterator operation

Description

All iterators

++p

Preincrement an iterator.

p++

Postincrement an iterator.

Input iterators


*p

Dereference an iterator.

p = p1

Assign one iterator to another.

p == p1

Compare iterators for equality.

p != p1

Compare iterators for inequality.

Output iterators

*p

Dereference an iterator.

p = p1

Assign one iterator to another.

Forward iterators

Forward iterators provide all the functionality of both input iterators and output iterators.

Bidirectional iterators

--p

Predecrement an iterator.

p--

Postdecrement an iterator.

Random-access iterators

p += i

Increment the iterator p by i positions.

p -= i

Decrement the iterator p by i positions.

p + i

Expression value is an iterator positioned at p incremented by i positions.

p - i

Expression value is an iterator positioned at p decremented by i positions.

p[ i ]

Return a reference to the element offset from p by i positions

p <>

Return true if iterator p is less than iterator p1 (i.e., iterator p is before iterator p1 in the container); otherwise, return false.

p <= p1

Return TRue if iterator p is less than or equal to iterator p1 (i.e., iterator p is before iterator p1 or at the same location as iterator p1 in the container); otherwise, return false.

p > p1

Return TRue if iterator p is greater than iterator p1 (i.e., iterator p is after iterator p1 in the container); otherwise, return false.

p >= p1

Return TRue if iterator p is greater than or equal to iterator p1 (i.e., iterator p is after iterator p1 or at the same location as iterator p1 in the container); otherwise, return false.


موفق باشید.