當前位置:首頁 » 操作系統 » stlsort源碼

stlsort源碼

發布時間: 2022-09-27 10:19:14

① 為何STL的sort排序效率那麼高用的是什麼演算法

STL的sort在數據量不同的時候,他會自己選用不同的排序演算法。比如插入,快排。這些。

下面是說對STL的sort的源碼分析的,他有說到這些,你可以參考下
http://www.cnblogs.com/imAkaka/articles/2407877.html

② C++中 std::sort 時間復雜度是多少 是用來sort vector的

一般用的都是快速排序,最好、正常和平均時間復雜度都為O(nlog2n),2為底的對數,最壞情況就是數據已經或者近乎有序,當然就是O(n^2)了

③ C++ STL有哪些經典書籍

經典書籍比較多,其中最經典的就是《C++標准程序庫:自修教程與參考手冊》。

④ C++源碼怎麼查看

如果你想看stl裡面的源碼可以去sgi
下載源代碼,download
stl
source
code
去這個網站下載源碼,sgi版本的stl代碼一般來說可讀性比較好,我正在看。
sort函數的代碼在stl_algo.h文件里。侯捷有本書叫做《stl源碼剖析》
如果是vs2008或者2010可以在microsoft
visual
studio
10.0\vc\crt\src查看
另外還有本書叫做《c標准庫》但是現在好像絕版了。
也可以去這個找:在glibc庫里,可去其官方網站下載(最新是2。7的),然後查找一下你要的函數。

⑤ 求幫忙解釋下C++中std::sort()函數中的參數問題,如何得到需要排序的n數量的問題。詳情請看下面:

last不算的, 這是STL的慣例.
STL中的所有演算法, first~last這樣的參數, 都是不算在內的.

int a[4] 這樣的數據排序.
參數就是 first = a last = a+4 一共4個數據, 分別是a+0, a+1, a+2, a+3
last也就是a+4不算在內.

至於內部編碼, std::sort的實現是函數模板.
下面是VC編譯器的源代碼, 在algorithm頭文件中. 這個頭文件就是STL的演算法庫.

template<class _RanIt,
class _Diff,
class _Pr> inline
void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
{ // order [_First, _Last), using _Pred
_Diff _Count;
for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
{ // divide and conquer by quicksort
pair<_RanIt, _RanIt> _Mid =
_Unguarded_partition(_First, _Last, _Pred);
_Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions

if (_Mid.first - _First < _Last - _Mid.second)
{ // loop on second half
_Sort(_First, _Mid.first, _Ideal, _Pred);
_First = _Mid.second;
}
else
{ // loop on first half
_Sort(_Mid.second, _Last, _Ideal, _Pred);
_Last = _Mid.first;
}
}

if (_ISORT_MAX < _Count)
{ // heap sort if too many divisions
_STD make_heap(_First, _Last, _Pred);
_STD sort_heap(_First, _Last, _Pred);
}
else if (1 < _Count)
_Insertion_sort(_First, _Last, _Pred); // small
}

⑥ C++ STL for_each 的用法

for_each第三個參數傳入的是函數名稱,通過模板生成代碼後的函數指針,for_each需要調用,可以看看STL的for_each函數的源碼。
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;

void print(int a)
{
cout << a <<"\t";
}

class myInt
{
public:
void operator()(int x)
{
cout << x << "\t";
}
};

template<int thevalue>
void add(int &ele)
{
ele += thevalue;
}

class AddValue
{
private :
int thevalue;
public:
AddValue(int va) : thevalue(va)
{
}

void operator()(int & element)
{
element += thevalue;
}

};

int main()
{
/*
vector<string> ve;

(istream_iterator<string>(cin),
istream_iterator<string>(),
back_inserter(ve));

sort(ve.begin(),ve.end());

(ve.begin(),ve.end(),
ostream_iterator<string>(cout,"\t"));
*/
vector<int> ve;
for(int i = 0; i< 9; i++)
{
ve.push_back(i);
}

for_each(ve.begin(),ve.end(),print);
cout << endl;

for_each(ve.begin(),ve.end(),myInt());
cout << endl;

cout << "after add --------" << endl;
for_each(ve.begin(),ve.end(),add<10>);

for_each(ve.begin(),ve.end(),print);
cout << endl;
for_each(ve.begin(),ve.end(),AddValue(10));
for_each(ve.begin(),ve.end(),print);
cout << endl;
for_each(ve.begin(),ve.end(),AddValue(*ve.begin()));
for_each(ve.begin(),ve.end(),print);
cout << endl;
}

⑦ List<Int>如何排序或按排序的順序取出

  1. list:

list就是數據結構中的雙向鏈表(根據sgi stl源代碼),因此它的內存空間是不連續的,通過指針來進行數據的訪問,這個特點使得它的隨即存取變的非常沒有效率,因此它沒有提供[]操作符的重載。但由於鏈表的特點,它可以以很好的效率支持任意地方的刪除和插入

由於List的實際存儲空間是非連續的,所以,STL中的sort()對它不起作用。只能使用自帶的list::sort().默認是升序排序。如果是復雜的數據類型,還得自己寫比較函數。示例:

#include<iostream>
#include<list>
#include<algorithm>
usingnamespacestd;

typedeflist<int>LISTINT;

intcmp(constint&a,constint&b){//自定義降序判斷函數。
//對自定義或者比較復雜數據類型,可以在這里完成。
returna>b;
}
voidmain()
{
//用LISTINT創建一個list對象
LISTINTlistOne;
//聲明i為迭代器
LISTINT::iteratori;

listOne.push_front(3);//插入數據到list中
listOne.push_back(2);
listOne.push_back(1);

listOne.push_back(4);
listOne.push_back(5);
listOne.push_front(6);

cout<<"beforesorted:"<<endl;//排序前輸出
for(i=listOne.begin();i!=listOne.end();++i)
cout<<*i<<"";
cout<<endl;

//listOne.sort();//默認升序排序
listOne.sort(cmp);//用自定義判斷函數,實現降序排序
cout<<"aftersorted:"<<endl;//排序後輸出
for(i=listOne.begin();i!=listOne.end();++i)
cout<<*i<<"";
cout<<endl;

}

⑧ 速求教 掌握STL中的vector,list,set,map容器;掌握sort,find方法

1. 編寫一個函數模板, 取const vector 參數並根據vector是否正向逆向都一樣而返回true和false值;編寫main程序來測試該函數。
2. 編寫一個函數模板, 取const list 參數並根據list是否正向逆向都一樣而返回true和false; 編寫main程序來測試該函數。
3. 編寫一個main程序, 使用vector存儲用戶從鍵盤輸入的n個整數, 利用STL中sort演算法排序, 並用find方法查找某個數.

4. 使用set容器存儲整型元素, 編寫函數求兩個集合的交集.

5. 使用map來建立英文單詞zero, one, two, three… ten 到 0- 10 數字到映射關系; 輸入英文數字 one 後輸出數字 1.

6.編寫main函數,用map來來統計一篇英文文章中單詞出現的頻率(為簡單起見,假定依次從鍵盤輸入該文章;

7. 模擬網上交易系統的中購物車;
本題目用Order模擬用戶的訂單,用Cart模擬用戶的購物車;具體聲明如下:
class Order//描述訂單
{
public:
Order(int gid, int gnum);//構造函數;
void print();//顯示訂購的商品編號: 數量
bool operator == (int gid);//判斷當前商品編號是否與參數gid相同,相同返回true,否則返回false
private:
int goods_id; //商品編號
int goods_number;//商品數量
};

class Cart//描述購物車, 存儲了多了產品的訂單
{
public:
void add(Order* or);//增加一個訂單
void print();//顯示所有訂單信息
bool del(int gid); //如果有商品編號為gid的訂單就刪除,並返回true,否則返回false
private:
list<Order*> l_goods;//存儲了多了產品的訂單
};
請實現上述兩個類的成員函數,並且利用下面的main程序進行測試。

void main()
{
Cart c;
int n,i;
int gid,gnum;
cout << "你要訂購多少商品" <<endl;
cin >> n;
//測試 Cart::add方法
cout << "測試 Cart::add方法---------------" << endl;
for(i = 0;i<n;i++)
{
cout << "請輸入第"<< i+1 <<"個訂單信息"<<endl;
cin >> gid >> gnum;
c.add(new Order(gid,gnum));
}
//測試Cart::print方法
cout << "你的訂單信息如下"<<endl;
c.print();
//測試Cart::del方法
cout <<"測試Cart::del方法, 請輸入要刪除的訂單的產品編號"<<endl;
cin >> gid;
c.del(gid);
cout <<"現在你的訂單信息如下"<<endl;
c.print();

}

8.模擬網上拍賣系統中的客戶分組

客戶類 Client
客戶類表示拍賣系統的注冊用戶。這個類封裝了以下私有數據成員: firstname,lastname,email,password。封裝了以下的公有成員函數:
(1)默認構造函數:將數據成員初始化化為默認值。
(2)具有四個參數的構造函數:用參數值為數據成員初始化
(3) 拷貝構造;
(4) 訪問和存取私有數據成員的方法;
(5)驗證密碼的函數: virtual bool verifyPasswd(string passwd); 如果參數與對象的用戶密碼相同返回true,否則返回false。
(6)重載輸入運算符函數operator>> ,可以 接受如下格式的客戶信息:
firstname \n lastname \n email \n password \n

Group類
Group類表示用戶集合.這個類有一個私有數據成員 vector<Client*>, 存儲用戶的指針。
該類有以下成員函數:
(1)virtual void add(Client* ptr); 增加一個用戶指針
(2)virtual iterator begin(); 返回第一個用戶指針的迭代器。
(3)virtual iterator end();返回最後一個用戶指針的迭代器。
(4)virtual Client* operator[](const string& email);返回郵箱地址與參數相同的用戶的地址。

?handout-files.zip 含有以下兩個文件:
oGroup.h - class Group 的聲明.
oClient.h –class Client 的聲明

------Solutions------
考題?
------Solutions------
標題和內容不符。
想掌握那些容器,看書,如 c++ primer
------Solutions------
找本C++的書看看吧。基礎
------Solutions------
c++標准程序庫和STL源碼剖析撒
------Solutions------
《C++ Primer》

⑨ 編寫一個sort函數,它用於對任何類型的數組進行排序

如下,為了簡便,程序中使用了一些標准庫函數,所以需要包含兩個頭文件,sort()函數利用選擇排序演算法對數組進行排序,調用時需要傳入的參數和標准庫函數qsort()一致

#include <stdlib.h>
#include <string.h>

void sort(void *base,unsigned int n,unsigned int width,int (*comp)(void *a,void *b))
{
char *p=(char *)base;
char *te=(char *)malloc(width);
char *ptr;
char *pn=p+width;
const char *cp=p+(n-1)*width;

for (; p<cp; p+=width) {
ptr=p;
for (pn=p+width; pn<=cp; pn+=width)
if ((*comp)(ptr,pn)>0) ptr=pn;
if (ptr!=p) {
memcpy(te,p,width);
memmove(p,ptr,width);
memmove(ptr,te,width);
}
}

free(te);
}

⑩ C++中STL的代碼分類有哪些

STL六大組件
1、容器 vector set list map deque
2、演算法 sort search erase
3、迭代器 iterators
4、仿函數
5、配接器:修飾容器、仿函數、迭代器的東東
6、配置器:空間配置
學STL建議看<STL源碼剖析>一書,個人感覺寫的挺詳細的

熱點內容
編程畫櫻花 發布:2024-03-29 02:11:24 瀏覽:471
騰訊雲伺服器1mb老掉線 發布:2024-03-29 01:56:11 瀏覽:213
執行sql語句的存儲過程 發布:2024-03-29 01:52:37 瀏覽:695
婚紗攝影腳本 發布:2024-03-29 01:47:40 瀏覽:899
我的世界伺服器咋開外掛 發布:2024-03-29 01:07:45 瀏覽:455
sql寫報表 發布:2024-03-29 01:03:23 瀏覽:305
家用伺服器怎麼選 發布:2024-03-29 00:49:18 瀏覽:401
Ap6510dn如何配置 發布:2024-03-29 00:38:47 瀏覽:333
安卓和蘋果哪個更佔用內存 發布:2024-03-29 00:37:02 瀏覽:424
編譯錯誤算bug嗎 發布:2024-03-29 00:23:03 瀏覽:34