青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

C++ Programmer's Cookbook

{C++ 基礎} {C++ 高級} {C#界面,C++核心算法} {設計模式} {C#基礎}

理解STL---understanding stl

Introduction

STL has a lot of powerful features which are undiscovered for many programmers. Complexity of templates stops people from discovering the scope of STL. Here, I am removing that complexity by explaining with template’s generated code with commonly used data types. This article intends to trigger you for exploring the internals of STL and use its powerful features. Once you understand the features of STL, you will get addicted of using it in your development. Explaining all the container and algorithm internals are out of the scope of this article. I choose vector and some sample algorithms to explain the usage of STL.

What is STL?

The Standard Template Library (STL) is a general-purpose C++ library of algorithms and data structures, originated by Alexander Stepanov and Meng Lee. The STL, based on a concept known as generic programming, is part of the standard ANSI C++ library. The STL is implemented by means of the C++ template mechanism, hence its name. While some aspects of the library are very complex, it can often be applied in a very straightforward way, facilitating reuse of the sophisticated data structures and algorithms it contains.

Why should I learn STL?

STL gives generic collections and algorithms which can be applied on those collections. STL code can be used across the platforms. Since STL containers and algorithms are C++ templates, you are able to use any data type, if it satisfies the requirement of the templates. You can make generic code which will accept all types of container classes. Examples of STL containers are deque, list, map, multimap, multiset, set, and vector; and examples of algorithms are find, copy, remove, max, sort, and accumulate.

Vector and Algorithm Relation

Let us try to have an idea of how algorithm ‘remove’ works on a vector. Vector is an STL container which grows dynamically and have similar features of an array.

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
using namespace std;
void main()
{  
    typedef /*list/deque*/vector<int > intVect ;
    typedef intVect::iterator intVectIt ;
    intVectIt end ,it,last;
            
    intVect Numbers ;  
    Numbers.push_back ( 10 );Numbers.push_back ( 33 ); Numbers.push_back(50);
    Numbers.push_back(33);    
    cout << "Before calling remove" << endl ;
    end = Numbers.end();
    cout << "Numbers { " ;
    for( it = Numbers.begin(); it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;
    last = remove(Numbers.begin(), end, 33) ;
    cout << "After calling remove" << endl ;
    cout << "Numbers { " ;
    for(it = Numbers.begin(); it != last; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;
}

Output of the program

Before calling remove
Numbers { 10 33 50 33  }
 
After calling remove
Numbers { 10 50  }

In the above example, we insert 10, 33, 50, and 33 into vector Numbers. Algorithm ‘remove’ is used to remove all the elements which has a value 33. ‘remove’ uses iterator of vector for this operation. iterators have similarities to pointers and are used to traverse an array of objects. In implementation of vector<int>, it's iterator is int*.

Now, change vector to deque or list in the first line. You can see our program is working exactly same as in the vector case! For changing the container implementation, we had to change only one line of code. This is one of the big benefits which is offered by STL. Now, take the above piece of code to some other operating system (I tested with Windows and Linux ), build and run it. Without any change, it works! This is another big advantage STL offers. You can try different data types instead of int for vector container.

Constructors of vector

Now, let us look at how default constructor and constructor with an integer argument work. I will be using object of the following class for inserting into the vector.

class A
{
    int iValue;
    A()
    {
        cout << "A()" << endl;
    }
};

Class vector<A> has four member variables: allocator, _First, _Last, and _End. allocator is of type std::allocator<A>, and _First, _Last, and _End are iterators which come out to be A*. Default constructor of vector<A> initializes allocator with std::allocator<A> object. _First, _Last, _End are initialized to null pointers.

Now, let us see how constructor vector(size_type _N, const _Ty& _V = _Ty(), const _A& _Al = _A()) works. By removing template variables for class A, prototype of the constructor becomes:

vector ( unsigned int _N , const A& _V = A(), 
  const std::allocator<A> & _A1 = std::allocator<A> () )

This constructor does the following things to initialize its member variables:

  1. _First = allocator.allocate(_N, (void *)0);
  2. _Ufill(_First, _N, _V);
  3. _Last = _First + _N;
  4. _End = _Last;

allocator.allocate calls template function _Allocate passing number of objects to be created (_N). For class A, this template function is generated to A* _Allocate ( int , A * ).

This function allocates _N * sizeof ( A ) memory and returns the starting address. This is assigned to _First. _Ufill does something like this:

for (; 0 < _N; --_N, ++_F)
    allocator.construct(_F, _X);

Here, _F ( of type A* ) points to the address where object to be constructed from _X through A ( const A & ).

_Ufill copies the one object constructed (const reference to object is _V. Refer line 2.) to all _N locations. allocator.construct calls template function _Consturct passing the same arguments. A new object is created at location _F from reference to object _X (new placement operator is used here). In line 3, _Last is assigned to address after last object. _End and _Last point to the same location.

Now, let us have a look at how the destructor works. Destructor of the vector does the following things:

_Destroy(_First, _Last);
allocator.deallocate(_First, _End - _First);
_First = 0, _Last = 0, _End = 0;

_Destroy calls allocator.destroy ( _F ) for each A* _F from _First through _Last. This function will call destructor ~A() explicitly to destroy the object (remember, we allocated using placement new operator). allocator.deallocate deletes the memory pointed to by (_First) which will free memory allocated for all the objects in the vector.

How push_back works?

Most complicated and most frequently used function in a vector is push_back. Let us analyze how push_back works? push_back will insert new data at the end of the vector. It calls insert ( end(), _X). (Member function end() returns _Last and _X is reference to the object (class A) to be added.) insert calls another overloaded function insert (_Last , 1 , _X).

For class A, this function definition becomes:

void insert(A* _P, unsigned int _M, const A& _X)
{
    if (_End - _Last < _M)
    {
        unsigned int _N = size() + (_M < size() ? size() : _M);
        A* _S = allocator.allocate(_N, (void *)0);
        A* _Q = _Ucopy(_First, _P, _S);
        _Ufill(_Q, _M, _X);
        _Ucopy(_P, _Last, _Q + _M);
        _Destroy(_First, _Last);
        allocator.deallocate(_First, _End - _First);
        _End = _S + _N;
        _Last = _S + size() + _M;
        _First = _S;
    }
    else if (_Last - _P < _M)
    {
        _Ucopy(_P, _Last, _P + _M);
        _Ufill(_Last, _M - (_Last - _P), _X);
        fill(_P, _Last, _X);
        _Last += _M; 
    }
    else if (0 < _M)
    {
        _Ucopy(_Last - _M, _Last, _Last);
        copy_backward(_P, _Last - _M, _Last);
        fill(_P, _P + _M, _X);
        _Last += _M; 
    }
}

Before explaining this code, we should look at the difference between _End and _Last. _End is the end of the buffer allocated to the vector, and _Last is the end of the last value inserted. To make it clear, take the case of pushing back object of A to a vector which currently contains three objects, and assume _End and _Last point to the same location. In this case, allocator will allocate memory for 3+3 objects even though we have to insert only one. This is to reduce reallocations. After push_back, _End will point to the end of 6th object, and _Last will point to the end of the 4th object. During push_back, insert checks whether reallocation is needed ((_End - _Last < _M)). If reallocation is needed, it allocates double size or size() + _M, whichever is higher. It copies all the data to the new buffer and removes the earlier buffer. It then inserts new data at the _Last position and reassigns _Last and _End. If we have enough space to insert a new element (i.e., _End - _Last > _M), new element is inserted at _Last, and _Last is reassigned.

STL Algorithms (how it works with a vector)

Before understanding algorithms, we will have to learn how function objects work. Class of a function object defines operator()(). The result is, a template function can not detect whether you passed a pointer to a function or object of a class having operator()(). Following example will give you a clear idea about what are function objects:

#include <iostream.h>
void  f ()
{
    cout << "f()" << endl;
}
 
class X
{
public:
    void operator()()
    {
        cout << "X::operator()" << endl;
    }
};
 
template < class T >
void test_func ( T f1 )
{
    f1();
}
void main()
{
    X a;
    test_func(f );
    test_func(a);
}

Output of the program is:

f()
X::operator()

Function objects can be classified as Generator (no argument), UnaryFunction (single argument), and BinaryFunction (takes two arguments). A special case of unary and binary functions are predicates (UnaryPredicate, BinaryPredicate) which simply means function returns a bool. STL has, in the header file <functional>, a set of templates that automatically create function objects for you. It is powerful not only because it’s a reasonably complete library of tools, but also because it provides a vocabulary for thinking about problem solutions, and because it is a framework for creating additional tools.

How copy works?

Problem: copy all the data of one vector<A> to another vector<A>.

Analysis: For class A, function definition becomes (you have to pass arguments which support operator ++ () and operator *(). You can apply * and ++ to iterators.):

copy ( A* first , A* last , A* x )

Function copy evaluates *(x+N) = * ( first + N ) for all N in the range [0, last-first]. It returns x+N. Consider vector<A> objects sourceA, DestA. For copying all data from sourceA to DestA, you have to call copy (sourceA.begin() , sourceA.end() , DestA.begin()).

Before calling copy, ensure that destination vector has enough space to accommodate all the data in source vector.

How transform works?

Problem: you have a vector<int> of three members and you want to store square of each element in another vector<int>.

Solution: following piece of code does the job for you:

int square_it ( const int x)
{
    return x*x;
}
void main ()
{
    vector < int > v1, v2(3);
    v1.push_back(2);
    v1.push_back(5);
    v1.push_back(83);
    transform ( v1.begin() , v1.end() , v2.begin() , square_it );
    for ( vector<int>::iterator it = v2.begin(); it != v2.end() ; it++ )
        cout << *it;
}

For the above code, function prototype generated for transform is:

int * trnsform ( int * First , int * Last , int* x, int (*f) (const int) )

transform evaluates *(x + N ) = square_it (*(First + N ) ) for all N in the range [0, Last - First]. Note: v2 has enough memory allocated (memory for three integers) before calling transform.

How generate works?

Problem: insert three ascending numbers in a vector without using push_back.

Solution: following piece of code does the job for you:

int f ()
{
    static int x = 1;
    return ++x;
}
void main ()
{
    vector < int > v2(3);
    generate ( v2.begin() , v2.end() , f );
    for ( vector<int>::iterator it = v2.begin(); it != v2.end() ; it++ )
        cout << *it;
}

For the above code, generated function prototype for ‘generate’ is:

void generate ( int* first , int* last , int (*f)() )

generate evaluates *(first + N ) = f ( ) for all N in the range [0 , last - first].

How replace_if works?

Problem: change all 0 to -1 in the vector<int>.

Solution: assume vector<int> v contains integers 1, 2, 0, 6, 0. Following code will change all the 0s to -1:

int f (const int x)
{
   if ( x ==  0 )
       return true;
   else
       return false;
}
replace_if( v.begin() , v.end() , f , -1);

Generated prototype for replace_if is:

void replace_if ( int * first , int * last , int (*f) ( const int) , -1 )

For all N in the range [0, last-first], replace_if evaluates to:

if ( f ( *(first+N) ) )
    *(first + N ) = -1;

How for_each works?

Problem: print all the members of vector.

Solution: following piece of code does the work for you:

void f (const int x)
{
    cout << x << endl;
}
for_each ( v.begin() , v.end() , f);

Prototype generated for the above code is:

void for_each ( int * first , int* last , void (*f) (const int ) );

for_each will evaluate to:

f ( *( first + N ) ) for all N in the range [0 , last - first ]

How fill works?

Problem: fill vector<int> v with value 10.

Solution: following code does the work for you:

fill ( v.begin() , v.end() , 10 );

Generated function prototype for the above invocation of fill is:

void fill(int * first, int * last, const int &) ;

fill evaluates *(first + N) = x once for each N in the range [0, last - first].

How count_if works?

Problem: count number of '2's in an integer array.

Solution: following code does the work for you:

bool f2 ( const int x )
{
    if ( x == 2 )
        return true;
    else
        return false;
}

Assume vector<int> v contains integers. Following code will return number of '2's in the vector:

int iNoof2s = count_if( v.begin() , v.end() , f2 );

Generated function prototype for the above code is:

unsigned int count_if (  int * first , int * last , bool (*fn) ( const int ) );

count_if sets a count n to zero. It then executes ++n for each N in the range [0, last - first] for which the predicate fn(*(first + N)) is true. It evaluates the predicate exactly last - first times.

Conclusion

You have got an idea about how vector and some of the algorithms work. Try using other containers and explore more algorithms. You will discover more interesting things. Happy coding with STL.

About Jais Joy


5+ year in software industry.Currently working for IBM Bangalore
Looking forward to contribute to software industry.

Click here to view Jais Joy's online profile.

posted on 2005-12-28 08:46 夢在天涯 閱讀(2365) 評論(2)  編輯 收藏 引用 所屬分類: STL/Boost

評論

# re: 理解STL---understanding stl 2006-01-10 11:35 shanzy

CP網站上評分才1.98,可見文章的可看程度是多少??

原文作者使用的是VC自帶的STL,都知道這個可讀性幾乎為0

另外,文章的出處還沒有注明:

http://www.codeproject.com/vcpp/stl/stl_by_code_walk.asp  回復  更多評論   

# re: 理解STL---understanding stl 2006-01-10 12:11 shanzy

總的來說,原文作者的文章還是不錯,不過有的地方說的有點含糊

http://www.codeproject.com/vcpp/stl/stlintroduction.asp

This example declares a class Value, which stores a parameterized value, _value, of type T.

value不應該算:template parameter list中的1個,要算也要算是類的成員函數的參數列表中的一個  回復  更多評論   

公告

EMail:itech001#126.com

導航

統計

  • 隨筆 - 461
  • 文章 - 4
  • 評論 - 746
  • 引用 - 0

常用鏈接

隨筆分類

隨筆檔案

收藏夾

Blogs

c#(csharp)

C++(cpp)

Enlish

Forums(bbs)

My self

Often go

Useful Webs

Xml/Uml/html

搜索

  •  

積分與排名

  • 積分 - 1811979
  • 排名 - 5

最新評論

閱讀排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
      <noscript id="pjuwb"></noscript>
            <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
              <dd id="pjuwb"></dd>
              <abbr id="pjuwb"></abbr>
              免费观看成人网| 在线欧美日韩国产| av成人免费在线观看| 亚洲高清在线观看| 欧美一区视频| 在线播放国产一区中文字幕剧情欧美| 久久精品国产一区二区三区| 香港久久久电影| 在线播放国产一区中文字幕剧情欧美| 一区二区三区免费网站| 亚洲韩国青草视频| 欧美日韩国产精品一区二区亚洲| 亚洲欧美日韩国产| 久久成人一区二区| 亚洲三级影院| 亚洲午夜视频在线观看| 韩国欧美一区| 亚洲日韩第九十九页| 国产精品久久久一区二区| 久久久91精品国产| 欧美gay视频激情| 亚洲综合精品四区| 欧美在线不卡视频| 99国产精品视频免费观看一公开| 亚洲一区免费网站| 黄色日韩网站视频| 99国产精品久久久久老师| 国产手机视频一区二区| 亚洲高清影视| 国产在线精品二区| 亚洲日本欧美| 国产一区视频观看| 99av国产精品欲麻豆| 国产一区成人| 日韩亚洲成人av在线| 国产一区二三区| 一区二区三区你懂的| 在线播放一区| 亚洲在线成人精品| 日韩亚洲精品在线| 久久激五月天综合精品| 亚洲午夜视频在线| 欧美日韩大片| 久久久久国产一区二区| 欧美视频日韩| 狂野欧美一区| 国产女主播一区二区三区| 亚洲国产精品小视频| 国产欧美日韩免费看aⅴ视频| 亚洲区中文字幕| 在线观看一区欧美| 亚洲免费在线观看| 亚洲一区二区三区高清不卡| 免费成人av资源网| 亚洲欧美国产va在线影院| 一本一本久久| 最新日韩在线视频| 久久精品国产亚洲高清剧情介绍| 夜夜嗨av一区二区三区四区| 久久久亚洲国产美女国产盗摄| 欧美亚洲视频在线观看| 欧美视频一区二区三区在线观看| 亚洲激情视频在线| 亚洲欧洲日本国产| 另类av导航| 欧美激情在线| 亚洲精品视频在线看| 欧美成人免费在线观看| 欧美激情精品| 亚洲欧洲一区二区在线观看| 久久久亚洲国产天美传媒修理工| 麻豆国产精品777777在线 | 久久不射网站| 欧美一级一区| 一本色道久久综合亚洲二区三区| 亚洲免费精品| 欧美福利一区二区| 亚洲免费观看在线观看| 中文欧美日韩| 国产三区精品| 久久人人精品| 亚洲国产欧美一区二区三区久久 | 一区二区av| 国产精品v亚洲精品v日韩精品 | 欧美日韩亚洲一区| 中文av字幕一区| 欧美伊久线香蕉线新在线| 国产日韩欧美自拍| 鲁鲁狠狠狠7777一区二区| 亚洲高清成人| 亚洲性视频网站| 国产午夜亚洲精品羞羞网站| 久久综合给合久久狠狠色| 亚洲黄页一区| 亚洲欧美日韩视频二区| 狠狠88综合久久久久综合网| 欧美成人午夜剧场免费观看| 亚洲网址在线| 美女黄网久久| 一区二区三区日韩欧美精品| 国产欧美日韩91| 亚洲欧美成人一区二区在线电影| 亚洲丝袜av一区| 久久一区二区三区四区五区| 一片黄亚洲嫩模| 狠狠久久婷婷| 国产精品爱啪在线线免费观看| 欧美专区日韩视频| 男人插女人欧美| 一区二区不卡在线视频 午夜欧美不卡在 | 欧美激情国产精品| 欧美一区二区| 亚洲美女在线一区| 国产一区二区中文| 欧美日韩亚洲综合在线| 久久久久欧美| 亚洲在线网站| 亚洲乱码国产乱码精品精天堂| 久久久www成人免费无遮挡大片| 日韩视频在线播放| 一区在线免费观看| 国产精品免费网站| 欧美国产大片| 久久综合色88| 先锋影音久久久| 99精品国产在热久久| 欧美成人第一页| 久久久噜久噜久久综合| 亚洲午夜女主播在线直播| 亚洲美女在线国产| 亚洲国产另类久久精品| 国产一区二区按摩在线观看| 国产日韩欧美夫妻视频在线观看| 欧美国产精品一区| 美女啪啪无遮挡免费久久网站| 欧美在线播放一区| 午夜电影亚洲| 亚洲免费影视| 亚洲欧美日韩爽爽影院| 亚洲午夜精品久久久久久浪潮| 日韩午夜一区| 一本不卡影院| av成人福利| 亚洲欧洲精品一区二区三区| 欧美激情女人20p| 亚洲第一二三四五区| 欧美激情第9页| 欧美国产精品| 欧美国产1区2区| 欧美激情久久久久久| 亚洲第一天堂av| 91久久一区二区| 91久久香蕉国产日韩欧美9色| 亚洲精品1区2区| 亚洲精品四区| 在线性视频日韩欧美| 亚洲桃花岛网站| 亚洲一区二区三区视频播放| 亚洲伊人第一页| 欧美亚洲日本国产| 久久久久久久久久看片| 久久影音先锋| 欧美国产欧美亚州国产日韩mv天天看完整| 免费亚洲电影在线| 欧美日韩无遮挡| 国产乱码精品| 亚洲第一页中文字幕| 日韩小视频在线观看| 亚洲免费在线精品一区| 欧美在线亚洲在线| 欧美成人黑人xx视频免费观看| 亚洲电影自拍| 亚洲午夜久久久| 久久久久久久999| 国产伦精品一区二区三区四区免费 | 欧美91视频| 欧美色中文字幕| 国产深夜精品| 欧美日本一区二区高清播放视频| 亚洲一区精品视频| 久久视频在线视频| 欧美精品久久久久久久久老牛影院 | 久久久国产精品一区| 亚洲国产精品成人精品| 亚洲一区二区三区视频播放| 麻豆精品视频在线| 国产精品视区| 亚洲精品一区二区三区四区高清| 亚洲欧美一区二区三区久久 | 日韩一区二区电影网| 午夜精品999| 欧美成年人视频| 午夜精品视频在线观看| 欧美aa在线视频| 国产一区999| 亚洲在线免费视频| 欧美韩日一区| 久久九九电影| 国产拍揄自揄精品视频麻豆| 亚洲美女在线观看|