Linux下安装MacbookPro的无线网卡驱动

2011年以后的MacbookPro用的是BCM4331无线网卡,这个网卡的Linux驱动很晚才出来,安装过程有一些麻烦。

  1. Linux Kernel 3.2rc3或者更新的版本
  2. 下载最新的firmware 666.2或者更新的版本 http://linuxwireless.org/en/users/Drivers/b43#List_of_firmware
  3. 装b43-fwcutter,Ubuntu下直接apt-get install b43-fwcutter即可
  4. 解压缩firmware文件,找到里面的wl_apsta.o文件,运行 b43-fwcutter -w /lib/firmware  wl_apsta.o 

然后无线网卡就可以用了

关于STL的介绍文章

整理电脑的时候,翻出来一篇不知道是猴年马月写的文章,关于STL的简单介绍,应该是以前写给学生看的吧,贴在这里分享一下。

1       STL简介

STLStandard Template Library的缩写,是C++标准库中最强大、最复杂、最有用的部分。STL主要由容器(container)、跌代子(iterator)、算法(algorithm)所组成。

1.1    容器

容器是存放和管理数据元素的数据结构,容器分为两大类:顺序容器(sequence container)和关联容器(associative container)。

顺序容器有:vector, deque, list

关联容器有:map, set, multi_map, multi_set

特殊的容器:string, array

容器适配器:stack, queue, priority_queue

1.2    跌代子

跌代子是用来访问容器内元素的对象,类似指针。

跌代子分为:随机跌代子,双向跌代子,单向跌代子,输入跌代子,输出跌代子

跌代子适配器

1.3    算法

算法是用来处理容器内的元素的一些操作,比如搜索、排序、拷贝、修改等。

算法分为两大类:更易型和非更易型

仿函数:类似函数指针

 

2       vector

2.1    接口说明

vector类似于数组,但是可以动态分配空间。

#include <vector>

namespace std {

   template< class T, class Allocator = allocator<T> > vector;

}

T可以是任何类型,但是必须满足:assignable, copyable

1.         构造方法:

vector< int > a1; // 构造一个空的vector

vector< int > a2(10); //构造10个元素的vector

vector< int > a3(10, 5); //构造一个10个元素的vector,每个元素都是5

vector < int > a4(a2); //构造一个vectora2完全一样

int values[] = {10, 11, 12, 13, 14};

vector < int > a5( values, values+5);

2.         不变操作和赋值

a1.size( ) //取容器内元素的个数

a1.empty( ) //判断容器是否为空

a1 == a2 //判断两个容器的内容是否相同, 还有!=, <, >, <=, >=

a1 = a2 //a2全部元素赋给a1

a1.assign( values, values+5 ) //values[0]values[4]赋给a1

a1.assign( 10, 5) //a1赋值105

3.         元素访问

a1[ 5 ] //取第5个元素,下标从0开始

a1.at(5) //取第5个元素,带边界检查

a1.front() //取第0个元素

a1.end() //取最后一个元素

4.         跌代子

a1.begin() //随机跌代子,指向a1[0]

a1.end()  //随机跌代子,指向最后一个的下一个

a1.rbegin() //随机跌代子,指向最后一个

a1.rend() //随机跌代子,指向a1[0]的前一个

5.         插入删除操作

a1.insert( a1.begin(), 5); //a1的最前面插入一个5

a1.insert(a1.end(), 10, 6); //a1的最后面插入106

a1.insert(a1.begin(), values, values+5) //a1的最前面插入values[0]values[4]

a1.push_back( 5 ) //a1的最后面插入一个5

a1.pop_back( ) // 删除a1的最后一个元素

a1.erase( a1.begin() ) //删除a1中的第一个元素

a1.erase( a1.begin(), a1.begin() +2) //删除a1最前面2个元素

a1.resize( 10 ) //a1元素个数改为10,增加的部分值为默认构造

a1.resize( 10, 6) //a1元素个数改为10,增加的部分值为6

a1.clear() //清除所有元素

2.2    vector的内存结构

类似于数据结构中的顺序表

a1.capacity() //返回容量的大小

a1.reserve(10); //改变容量的大小

2.3    用法实例

int main() {

vector< string > sentence;

   sentence.reserve( 5 );

   sentence.push_back( “ Hello, “);

   sentence.push_back( “how “);

   sentence.push_back( “are “);

   sentence.push_back( “you “);

   sentence.push_back( “?“);

   copy( sentence.begin(), sentence.end(), ostream_iterator<string>(cout, “  “));

   cout << endl;

  cout << sentence.size() << endl;

   cout << sentence.capacity() << endl;

   swap( sentence[1], sentence[3]);

   sentence.insert( find(sentence.begin(), sentence.end(), “?”), “always”);

   sentence.back() = “!”;

   copy( sentence.rbegin(), sentence.rend(), ostream_iterator<string>(cout, “  “));

   cout << endl;

}

2.4    vector代替数组

vector < int > a(10);

a[0] = 1;

a[1] = 2;

a[2] = a[0] + a[1];

for( int i = 0; i < a.size(); i++)

scanf( “%d”, &a[i] );

3       算法Algorithm

处理容器内的数据的函数

#include <algorithm>  //一般算法

#include <numeric>  //数值算法

#include <functional>  //仿函数

3.1    非变动性算法

for_each

count

count_if

min_element

max_element

find

find_if

search_n

search

find_end

find_first_of

adjacent_find

equal

mismatch

lexicographical_compare

3.2    变动性算法

copy

copy_backward

transform

merge

swap_ranges

fill

fill_n

generate

generate_n

replace

replace_if

replace_copy

replace_copy_if

3.3    移除算法

remove

remove_if

remove_copy

remove_copy_if

unique

unique_copy

3.4    变序性算法

reverse

reverse_copy

rotate

rotate_copy

next_permutation

prev_permutation

random_shuffle

partition

stable_partition

3.5    排序算法

sort

stable_sort

partial_sort

partial_sort_copy

nth_element

partition

stable_partition

make_heap

push_heap

pop_heap

sort_heap

3.6    已序区间算法

binary_search

includes

lower_bound

upper_bound

equal_range

merge

set_union

set_intersection

set_difference

set_symmetric_difference

inplace_merge

3.7    数值算法

accumulate

inner_product

adjacent_difference

partial_sum

4       一些常用的算法

4.1    for_each

对区间内每一个元素采用某一种操作

 

实现:

template <class InputIterator, class UnaryFunction>

UnaryFunction for_each(InputIterator first, InputIterator last, UnaryFunction f) {

   while( first != end) {

      f(*first);

      ++first;

}

return f;

}

 

用例1

void print ( int elem) {

   cout << elem << ‘ ‘;

}

int main() {

vector< int > col( 5, 10);

for_each( col.begin(), col.end(), print);

cout << endl;

}

 

用例2

template< class T>

class AddValue{

private:

T value;

public:

AddValue( const T&v) : value(v) {}

void operator()(T&elem) const { elem+=value; }

};

int main() {

vector<int > col(5, 10);

for_each(col.begin(), col.end(), AddValue<int>(10));

   copy( col.begin(), col.end(), ostream_iterator<int>(cout, “  “));

}

 

用例3

class MeanValue {

private:

   int num, sum;

public:

   MeanValue() : num(0), sum(0) {}

   void operator()( int elem ) { num ++; sum+=elem; }

   double value() { return static_cast<double>(sum) / static_cast<double>(num); }

};

int main() {

vector<int> col(5, 10);

MeanValue  mv = for_each(col.begin(), col.end(), MeanValue() );

cout << mv.value();

}

 

4.2    transform

功能1:将区间内每个元素作变换,存储到另一个空间里面

template <class InputIterator, class OutputIterator, class UnaryFunction>

OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op) {

while( first != last ) {

    *result = op(*first);

    ++result;

    ++first;

}

return result;

}

 

功能2:将两个区间内的元素作变换,存储到另一个空间内

template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction>

OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction binary_op) {

while( first1 != last1 ) {

    *result = op(*first1, *first2);

    ++result;

    ++first1;

    ++first2;

}

return result;

}

 

用例1

int main() {

vector< int > c1(5, 10);

transform( c1.begin(), c1.end(), c1.begin(), negate<int>() );

list < int> c2;

transform( c1.begin(), c1.end(), back_inserter(c2), bind2nd(multiplies<int>(), 5));

transform( c2.rbegin(), c2.rend(), ostream_iterator<int>(cout, “ “), negate<int>());

transform( c1.begin(), c1.end(), c1.begin(), c1.begin(), multiplies<int>());

transform( c1.begin(), c1.end(), c2.rbegin(), c1.begin(), plus<int>());

transform( c1.begin(), c1.end(), c1.begin(), ostream_iterator<int>(cout, “ “), minus<int>() );

}

 

5       仿函数(Functor, Function Object)

能像函数一样使用的对象。普通函数、函数指针、定义了operator()的类的对象都可以作为仿函数。

#include <functional>

5.1    Generator

不带参数的仿函数

比如:

rand

5.2    Unary Function

带一个参数的仿函数。

比如:

abs

negate

identity

5.3    Predicate

返回真或假的Unary Function

比如:

logical_not

5.4    Binary Function

带两个参数的仿函数。

plus

minus

multiplies

divides

modulus

5.5    Binary Predicate

返回真或假的Binary Function

less

greater

equal_to

not_equal_to

less_equal

greater_equal

logical_and

logical_or

5.6    auxiliary function

bind1st

bind2nd

not1

not2

mem_fun_ref

mem_fun

ptr_fun

compose1

compose2

5.7    Sample

1

find_if (coll.begin(),coll.end(), bind2nd (greater<int>(),42));

 

2

pos = find_if (coll.begin() , coll.end(), not1 (bind2nd(modulus<int>(),2)));

 

list<int> L;

list<int>::iterator first_positive = find_if(L.begin(), L.end(), bind2nd(greater<int>(), 0));

 

3

class Person {

private:

std::string name;

public:

void print() const {

std::cout << name << std::endl;

}

void printWithPrefix (std::string prefix) const {

std::cout << prefix << name << std::endl;

}

};

void foo (const std::vector<Person>& coll){

for_each (coll.begin(), coll.end(), mem_fun_ref(&Person::print));

for_each (coll.begin(), coll.end(), bind2nd (mem_fun_ref (&Person::printWithPrefix), "person: "));

}

void ptrfoo (const std::vector<Person*>& coll) {

for_each (coll.begin() , coll.end(), mem_fun(&Person::print));

for_each (coll.begin() , coll.end(), bind2nd(mem_fun(&Person::printWithPrefix), "person: "));

}

 

4

bool check(int elem);

pos = find_if (coll.begin(), coll.end(), not1(ptr_fun(check)));

pos = find_if (coll.begin(), coll.end(), bind2nd(ptr_fun(strcmp),""));

transform(first, last, first, compose1(negate<double>, ptr_fun(fabs)));

 

5

list<int> L;

list<int>::iterator in_range = find_if(L.begin(), L.end(),

   not1(compose2(logical_and<bool>(), bind2nd(greater_equal<int>(), 1), bind2nd(less_equal<int>(), 10))));

 

6

char str[MAXLEN];

const char* wptr = find_if(str, str + MAXLEN,    compose2(not2(logical_or<bool>()), bind2nd(equal_to<char>(), ' '), bind2nd(equal_to<char>(), '\n')));

6       Iterator迭代子

迭代子是一种能够遍历容器里面的全部或者部分元素的对象,一个迭代子能够表示容器里面一个特定的位置。

使用begin(), end()获得容器的迭代子。迭代子的类型会随着容器的不同而不同,可表示为container<T>::iterator,如果支持双向跌代,则可以通过rbegin(), rend()获得反向跌代子。反向跌代子的类型为:container<T>::reverse_iterator,

6.1    Categories

Input:只能单向读取,比如istream

Output:只能单向写入,比如ostream

Forward:单向读取和写入,具有InputOutput跌代子的全部能力,比如slist

Bidirectional:双向读取和写入,具有Forward跌代子的全部能力,比如list, set, map

Random:随机读取和写入,具有Bidirectional跌代子的全部能力,比如vector, deque

6.2    operators

迭代子最基本的操作有:

iter++, ++iter:让跌代子移动到下一个元素,有前置后置两种形式。

*iter:返回迭代子当前位置上的元素。如果是Input代子,返回元素的值,只能读取;如果是Output跌代子,返回引用,只能写入。

iter1 == iter2 , iter1 != iter2:判断两个跌代子是否指向同一个位置。(Output没有此操作)

iter1 = iter2:改变跌代子指向的位置。(Output没有此操作)

iter ->:如果元素是类(结构体),则可以使用->直接访问元素的成员。

iter --, --iter:使用--移动到前一个元素,有前置后置两种形式。(双向跌代子和随机跌代子)

iter [n]:后面第n个的元素(Random跌代子)

iter += n:往后面移动n个位置(Random跌代子)

iter -= n:往前面移动n个位置(Random跌代子)

iter + n, n + iter:后面第n个位置(Random跌代子)

iter - n:前面第n个位置(Random跌代子)

iter1 - iter2: 两个元素之间的距离(Random跌代子)

iter1<iter2, iter1 > iter2, iter1 <= iter2, iter1 >= iter2: 比较两个跌代子的位置(Random跌代子)

6.3    Auxiliary Iterator Functions

advance(iter, n):将跌代子后移n个位置

distance(iter1, iter2):两个跌代子之间的距离

6.4    Iterator Adapters

reverse iterator

insert iterators(back_inserter, front_inserter, inserter)

Stream Iterators(ostream_iterator, istream_iterator)

6.5    Sample

1

//OK for forward iterators

//IMPOSSIBLE for output iterators

while (pos != coll.end()) {

*pos = foo();

++pos;

}

 

2

int main() {

vector<int> coll;

for (int i=-3; i<=9; ++i) {

coll.push_back (i);

}

cout << "number/distance: " << coll.end()-coll.begin() << endl;

vector<int>::iterator pos;

for (pos=coll.begin(); pos<coll.end(); ++pos) {

cout << *pos << ' ';

}

for (int i=0; i<coll.size(); ++i) {

cout << coll.begin() [i] << ' ';

}

for (pos = coll.begin(); pos < coll.end()-1; pos += 2) {

cout << *pos << ' ';

}

}

 

3

int main() {

list<int> coll;

//insert elements from 1 to 9

for (int i=1; i<=9; ++i) {

coll.push_back(i);

}

list<int>::iterator pos = coll.begin();

cout << *pos << endl;

advance (pos, 3);

cout << *pos << endl;

advance (pos, -1);

cout << *pos << endl;

}

 

4

int main(){

list<int> coll;

for (int i=-3; i<=9; ++i) {

coll.push_back(i);

}

list<int>::iterator pos;

pos = find (coll.begin(), coll.end(), 5);

if (pos != coll.end()) {

cout << distance(coll.begin(),pos) << endl;

}

else {

cout << "5 not found" << endl;

}

}

 

5

void print (int elem) {

cout << elem << ' ';

}

int main() {

list<int> coll;

for (int i=1; i<=9; ++i) {

coll.push_back(i);

}

for_each (coll.begin(), coll.end(), print);

for_each (coll.rbegin(), coll.rend(), print);

}

 

6

int main() {

vector<int> coll;

for (int i=1; i<=9; ++i) {

coll.push_back(i);

}

vector<int>::iterator pos;

pos = find (coll.begin(), coll.end(), 5);

cout << "pos: " << *pos << endl;

vector<int>::reverse_iterator rpos(pos);

cout << "rpos: " << *rpos <<endl;

}

 

7

void print (int elem) {

cout << elem << ' ';

}

int main() {

deque<int> coll;

for (int i=1; i<=9; ++i) {

coll.push_back(i);

}

deque<int>::iterator pos1;

pos1 = find (coll.begin(), coll.end(), 2);

deque<int>::iterator pos2;

pos2 = find (coll.begin(), coll.end(), 7);

for_each (pos1, pos2, print);

deque<int>::reverse_iterator rpos1(pos1);

deque<int>::reverse_iterator rpos2(pos2);

for.each (rpos2, rpos1, print);

}

 

8

int main(){

list<int> coll;

for (int i=1; i<=9; ++i) {

coll.push_back(i);

}

list<int>::iterator pos;

pos = find (coll.begin(), coll.end(),5);

cout << "pos: " << *pos << endl;

list<int>::reverse_iterator rpos(pos);

cout << "rpos: " << *rpos << endl;

list<int>::iterator rrpos;

rrpos = rpos.base();

cout << "rrpos: " << *rrpos << endl;

}

 

9

int main() {

vector<int> coll;

back_insert_iterator<vector<int> > iter(coll);

*iter = 1;

iter++;

*iter = 2;

iter++;

*iter = 3;

copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));

back_inserter(coll) = 44;

back_inserter(coll) = 55;

copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));

copy (coll .begin(), coll.end(), back_inserter(coll));

copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));

}

 

10

int main() {

list<int> coll;

front_insert_iterator<list<int> > iter(coll);

*iter = 1;

iter++;

*iter = 2;

iter++;

*iter = 3;

copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));

front_inserter(coll) = 44;

front_inserter(coll) = 55;

copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));

copy (coll.begin(), coll.end(), front_inserter(coll));

copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “  “));

}

 

11

int main() {

ostream_iterator<int> intWriter(cout,"\n");

*intWriter = 42;

intWriter++;

*intWriter = 77;

intWriter++;

*intWriter = -5;

vector<int> coll;

for (int i=1; i<=9; ++i) {

coll.push_back(i);

}

copy (coll.begin(), coll.end(), ostream_iterator<int>(cout));

copy (coll.gin(), coll.end(), ostream_iterator<int>(cout," < "));

}

 

12

int main(){

istream_iterator<int> intReader(cin);

istream_iterator<int> intReaderEOF;

while (intReader != intReaderEOF) {

cout << "once: " << *intReader << endl;

cout << "once again: " << *intReader << endl;

++intReader;

}

}

 

13

int main() {

istream_iterator<string> cinPos(cin);

ostream_iterator<string> coutPos(cout," ");

while (cinPos != istream_iterator<string>()) {

advance (cinPos, 2);

if (cinPos != istream_iterator<string>()) {

*coutPos++ = *cinPos++;

}

}

cout << endl;

}

 

14

int main() {

vector<Date> e;

copy( istream_iterator<Date>(cin), istream_iterator<Date>(), back_inserter(e));

vector<Date>::iterator first = find(e.begin(), e.end(), "01/01/95");

vector<Date>::iterator last = find(e.begin(), e.end(), "12/31/95");

*last = "12/30/95";

copy(first, last, ostream_iterator<Date>(cout, "\n"));

e.insert(--e.end(), TodaysDate());

copy( first, last, ostream_iterator<Date>(cout, "\n") );

}

注:早先获得的跌代子在特定的操作后会失效!!vector的迭代子在插入、删除以及重新分配内存后可能会失效。

7       其他容器

7.1    Deque双端队列

#include <deque>

dequevector相似,区别是deque两端都是开放的,两端插入删除都很快。

deque的内存结构

可以随机访问,但比vector稍慢

迭代子是随机跌代子,是一种class而不是原始指针

操作非常相似,增加操作:push_front, pop_front,减少操作:reserve,capacity

任何插入和删除操作都可能使跌代子失效

例子:

int main() {

deque<string> coll;

coll.assign (3, string("string"));

coll.push_back ("last string");

coll.push_front ("first string");

copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n"));

coll.pop_front();

coll.pop_back();

for (int i=1; i<coll.size(); ++i) {

coll[i] = "another " + coll [i];

}

coll.resize (4, "resized string");

copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n"));

}

 

7.2    list链表

一般为双链表实现

#include <list>

提供双向跌代子,不能随机访问

插入删除操作非常快速

插入删除操作不会使跌代子失效

提供了一些移动元素的算法,比通用算法更快

c1.swap(c2):交换两个链表的内容

c.remove(val)

c.remove_if(predictor)

c.unique() 删除重复元素

c.splice() 将一个链表中的元素切一部分到另一个链表

c.sort() 排序

c.merge() 合并两个链表

c.reverse() 倒置

 

void printLists (const list<int>& 11, const list<int>& 12) {

cout << "list1: ";

copy (l1.begin(), l1.end(), ostream_iterator<int>(cout," "));

cout << endl << "list2: ";

copy (12.begin(), 12.end(), ostream_iterator<int>(cout," "));

cout << endl << endl;

}

int main() {

list<int> list1, list2;

for (int i=0; i<6; ++i) {

list1.push_back(i);

list2.push_front(i);

}

printLists(list1, list2);

list2.splice(find(list2.begin(),list2.end(), 3), list1);

printLists(list1, list2);

list2.splice(list2.end(), list2, list2.begin());

printLists(list1, list2);

list2.sort();

list1 = list2;

list2.unique();

printLists(list1, list2);

list1.merge(list2);

printLists(list1, list2);

}

 

7.3    stack

#include <stack>

namespace std {

template <class T, class Container = deque<T> >

class stack;

}

实现:

主要操作

push() 入栈

top() 取栈顶元素

pop() 出栈

例:

int main() {

stack<int> st;

st.push(l);

st.push(2);

st.push(3);

cout << st.top() << ' ';

st.pop() ;

cout << st.top() << ' ';

st.pop() ;

st.top() = 77;

st.push(4);

st.push(5);

st.pop() ;

while (!st.empty()) {

cout << st.top() << ' ';

st.pop() ;

}

cout << endl;

}

7.4    queue队列

#include <queue>

namespace std {

template <class T, class Container = deque<T> >

class queue;

}

实现

主要操作:

push

pop

back

front

 

int main() {

queue<string> q;

q.push("These ");

q.push("are ");

q.push("more than ");

cout << q.front();

q.pop();

cout << q.front();

q.pop();

q.push(''four ");

q.push("words!");

q.pop();

cout << q.front();

q.pop();

cout << q.front() << endl;

q.pop();

cout << "number of elements in the queue: " << q.size() << endl;

}

7.5    priority_queue优先队列

按照大小顺序出队的队列

#include <queue>

namespace std {

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> >

class priority_queue;

}

实现:堆

push() 入队

top() 读取下一个元素

pop() 删除下一个元素

 

 

int main() {

priority_queue<float> q;

q.push(66.6);

q.push(22.2);

q.push(44.4);

cout << q.top() << ' ';

q.pop();

cout << q.top() << endl;

q.pop();

q.push(11.1);

q.push(55.5);

q.push(33.3);

q.pop();

while (!q.empty()) {

cout << q.top() << ' ';

q.pop();

}

cout << endl;

}

 

7.6    setmulti_set

在这两种容器中,元素能够根据指定的排序规则自动的排序,以优化查找。两者区别是:set不允许有重复的元素,multi_set允许有重复的元素。

#include <set>

namespace std {

template <class T,

class Compare = less<T>,

class Allocator = allocator<T> >

class set;

template <class T,

class Compare = less<T>,

class Allocator = allocator<T> >

class multiset;

}

内部结构

例子:

#include <iostream>

#include <set>

using namespace std;

int main() {

typedef set<int,greater<int> > IntSet;

IntSet coll1; // empty set container

coll1.insert(4);

coll1.insert(3);

coll1.insert(5);

coll1.insert(1);

coll1.insert(6);

coll1.insert(2);

coll1.insert(5);

IntSet::iterator pos;

for (pos = coll1.begin(); pos != coll1.end(); ++pos) {

cout << *pos << ' ';

}

cout << endl;

pair<IntSet::iterator,bool> status = coll1.insert(4);

if (status.second) {

cout << "4 inserted as element "<< distance (coll1.begin(),status. first) + 1<< endl;

}else {

cout << "4 already exists" << endl;

}

set<int> coll2(coll1.begin(),

coll1.end());

copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout," "));

cout << endl;

coll2.erase (coll2.begin(), coll2.find(3));

int num;

num = coll2.erase (5);

cout << num << " element(s) removed" << endl;

copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout," "));

cout << endl;

}

7.7    mapmulti_map

存放关键字与对应值的数据结构

#include <map>

namespace std {

template <class Key, class T,

class Compare = less<Key>,

class Allocator = allocator<pair<const Key,T> > >

class map;

template <class Key, class T,

class Compare = less<Key>,

class Allocator = allocator<pair<const Key,T> > >

class multimap;

}

内部结构

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main() {

typedef map<string,float> StringFloatMap;

StringFloatMap stocks; // create empty container

stocks["BASF"] = 369.50;

stocks["VW"] = 413.50;

stocks["Daimler"] = 819.00;

stocks["BMW"] = 834.00;

stocks["Siemens"] = 842.20;

StringFloatMap::iterator pos;

for (pos = stocks.begin(); pos != stocks.end(); ++pos) {

cout << "stock: " << pos->first << "\t" << "price: " << pos->second << endl;

}

cout << endl;

for (pos = stocks.begin(); pos != stocks.end(); ++pos) {

pos->second *= 2;

}

for (pos = stocks.begin(); pos != stocks.end(); ++pos) {

cout << "stock: " << pos->first << "\t"<< "price: " << pos->second << endl;

}

cout << endl;

stocks["Volkswagen"] = stocks["VW"];

stocks.erase("VW");

for (pos = stocks.begin(); pos != stocks.end(); ++pos) {

cout << "stock: " << pos->first << "\t"<< "price: " << pos->second << endl;

}

}

如何防止DNS污染和劫持

由于国内的电信运营商和臭名昭著的墙的存在,在国内用运营商提供的域名服务器解析一个域名是有很大风险的:

  • 任何一个不存在的域名,都会被运营商解析到它的广告服务器上去
  • 任何一个存在的域名,都有一定的概率被运营商解析到它的广告服务器上去
  • 有些域名根本无法解析,比如说godaddy上注册的一些域名
  • 有些域名会解析到错误的无法访问的IP地址,比如说twitter.com, facebook.com
如果不用电信的DNS服务器,将自己的DNS设置直接指向国外的DNS服务器,比如Google或者OPENDNS的,可以解决部分问题,但是不是全部。如何完美解决这个问题?据我所知有下面这些选择:
  1. 通过TCP方式访问国外的DNS服务器可以解决所有问题。但是默认情况下,DNS客户端都是用UDP方式去访问的,除非遇到特殊情况。一般操作系统的DNS客户端也不能配置成强制使用TCP。一个办法是,用一个小程序(比如这个),可以在本地建个DNS服务器,把所有的DNS请求用TCP方式转发到国外服务器。这种方法的缺点是性能比较差,因为TCP方式不如UDP快。
  2. 用SSH Tunneling。SSH的端口转发功能(Port Forwarding)可以转发TCP端口,但是不能转发UDP端口所以不能用它来解决这个问题。不过SSH还有一个tunneling的功能,可以在两端建立一个tun设备,可以实现直连。你需要一台国外主机,有root权限,上面运行一个DNS服务器,国内的主机和这个服务器之间建立一个SSH tunnel,然后将国内主机上的域名服务器指向tunnel过来的IP地址即可。
  3. 用SSH Dynamic Port Forwarding。SSH还有一个用法,就是建立在本地建立一个SOCKS5的代理,可以把所有请求通过服务器转发出去。SOCKS5本身有一个功能就是可以进行域名解析。再配合一个小程序(比如这个),建立一个DNS服务器,转发到SOCKS5代理进行域名解析。
  4. 用DNSCrypt。DNSCrypt是OpenDNS提供的一个客户端工具,可以将DNS客户端和DNS服务器之间的连接加密,不过需要特殊的客户端和服务器支持。现在只有OpenDNS服务器支持。
  5. 如果你有IPV6的地址,可以直接用国外的IPV6的DNS服务器。
  6. VPN连接到国外,直接用国外的DNS服务器。
  7. 。。。
这些方法都有一个共同的缺点,就是这些方法都将DNS请求以各种方法转向国外,除了速度慢以外,对于国内一些大型网站,可能解析出来的结果在国内访问会很慢。


将squid打造成能自动重试的代理服务

我希望有这样一种HTTP代理服务软件,它首先会尝试直接连接目标服务器,当连接出现问题时,自动通过另外一个上级代理进行重试。Squid是个很有名很强大的代理服务软件,所以我先想到能不能把它配置成这样。

翻看Squid的文档,一下子就看到了这样两个参数:

  • prefer_direct: Normally Squid tries to use parents for most requests. If you for some reason like it to first try going direct and only use a parent if going direct fails set this to on. By combining nonhierarchical_direct off and prefer_direct on you can set up Squid to use a parent as a backup path if going direct fails. Note: If you want Squid to use parents for all requests see the never_direct directive. prefer_direct only modifies how Squid acts on cacheable requests.
  • retry_on_error: If set to ON Squid will automatically retry requests when receiving an error response with status 403 (Forbidden), 500 (Internal Error), 501 or 503 (Service not available). Status 502 and 504 (Gateway errors) are always retried. This is mainly useful if you are in a complex cache hierarchy to work around access control errors. NOTE: This retry will attempt to find another working destination. Which is different from the server which just failed.
在squid中如果配置了上级代理,默认会优先走上级代理,再尝试直连。prefer_direct参数让squid优先选择直连。squid会通过一个叫peerSelect函数,检查所有的acl规则后,产生一个可用的上级代理列表,如果有prefer_direct参数,表示直连的DIRECT会在列表的最前面,否则在最后面。另外squid还有个never_direct参数,如果加了这个参数,这个列表里面就没有DIRECT了。

squid默认只会在连接代理出现502(bad gateway)和504(gateway timeout)时,换个代理进行重试。如果是直连没有成功,不是这两个错误,通常是503(Service Unavailable)。加上retry_on_error参数后,对于直连失败也会换代理进行重试。

貌似加上这两个参数,就可以让squid达到我的效果了。我在ubuntu自带的squid3.1.14上尝试了以后,发现这组参数对于HTTP请求工作得很好,但是对于HTTPS(通过CONNECT方法)的请求没有用。看了内部实现后,发现squid内部在处理HTTPS (CONNECT方法)时,peerSelect是共用的,prefer_direct有效。但是连接处理是完全分开的,处理http请求在forward模块中,处理https请求在一个叫tunnel的模块中,完全不理会retry_on_error参数。

继续看文档,发现SQUID3.2版本新增了这样一个新功能:
  • CONNECT tunnel method retries. Are possible up until some bytes get transferred. (1)
换squid3.2再试。squid3.2还是beta版,所有linux发行版中都没有,可以从官网下载源代码编译安装。装完后发现这个功能并不能正常工作。看squid的debug log发现,第一次直接连接一个IP没有连上,底层通讯模块会尝试重连这个IP地址,重连竟然显示成功,但是后续所有读写操作失败。此时上层模块并不会换个代理服务器再连,因为底层报告成功后,上层就会给客户端发送HTTP200的返回表示成功了,此时如果底层再产生通讯问题,上层就没有办法换代理重试了。

这个问题出现在src/comm/ConnOpener.cc里面的timeout函数里:

void
Comm::ConnOpener::timeout(const CommTimeoutCbParams &)
{
     connect();
}
这个函数处理连接超时的情况,连接超时后,直接调用connect,connect函数会调用更底层的comm_connect_addr进行连接,但这时是第二次调用,底层会说你以前调用过了直接返回状态OK,然后上层就以为连接成功了。一个workaround的办法(更好的办法还没想到,可以给squid报bug先)是,timeout这里不要对同一个IP进行重试了,直接返回失败。做法是这样的:
void
Comm::ConnOpener::timeout(const CommTimeoutCbParams &io)
{
    debugs(5, 5, HERE << conn_ << ": * - ERR took too long to connect. (czk)");
    calls_.earlyAbort_->cancel("Comm::ConnOpener::connect timed out");
    calls_.earlyAbort_ = NULL;
    conn_->close();
    doneConnecting(COMM_ERR_CONNECT, io.xerrno);
}
改完代码再试一次。这里发现squid的编译系统也有点问题,改完这个文件需要make clean然后再make all否则不会生效。编译安装完后进行测试,发现这样确实解决了https重试的问题。

但是发现切换到squid3.2以后,http重试不如以前稳定了。看debug log发现,squid3.2的peerSelect准备了一张很长的重试列表,也不再称作server list或者peer list了,而是叫做path list。它会和3.1一样,先准备一个服务器列表,根据我们的需求,里面只会放两个服务器,一个DIRECT,和一个上级代理。然后它做了更多的事情,它把这个列表里面的域名拿去做dns解析,然后把每个服务器解析出来的所有IP地址都放在path列表里面。然后tunnel或者forward模块会根据path列表进行重试。比如连接www.youtube.com,DNS解析返回6个IP地址,peerSelect就返回了一张这样的重试列表:
DIRECT = local=0.0.0.0 remote=72.14.203.102:80 flags=1
DIRECT = local=0.0.0.0 remote=72.14.203.101:80 flags=1
DIRECT = local=0.0.0.0 remote=72.14.203.139:80 flags=1
DIRECT = local=0.0.0.0 remote=72.14.203.100:80 flags=1
DIRECT = local=0.0.0.0 remote=72.14.203.113:80 flags=1
DIRECT = local=0.0.0.0 remote=72.14.203.138:80 flags=1
cache_peer = local=0.0.0.0 remote=127.0.0.1:58118 flags=1
cache_peer = local=0.0.0.0 remote=127.0.0.1:58118 flags=1
cache_peer = local=0.0.0.0 remote=127.0.0.1:58118 flags=1
这个列表的总长度受一个叫forward_max_tries的参数控制,如果不幸这个域名返回的IP地址个数大于forward_max_tries,那么就不会有上级代理出现在这个列表里面了。查看代码src/peer_select.cc里面的peerSelectDnsResults函数,里面有一个循环把每一个IP加入path列表:
for (int n = 0; n < ia->count; n++, ip++) {
简单的做法就是在这里加个限制,每个域名最多2个IP加入path列表:
for (int n = 0; n < (ia->count>2?2:ia->count); n++, ip++) {
当然更好的做法是有一个参数能控制这个事情,可以给squid发个feature request。

改了这么多,还没有完。发现HTTPS重试的功能在twitter、facebook等网站上工作得都很好,但是对于google的网站,经常会失败。检查debug log发现,是臭名昭著的墙的随机RESET谷歌的HTTPS连接的问题。这个问题没有好的解决办法,因为连接已经建立再断开的,和前面说的那个bug产生的效果一样。解决的办法只能是把google网站的https链接手动加入never_direct。最简单配置是这样的:

acl CONNECT method CONNECT
acl google dstdomain .google.com
acl google dstdomain .blogger.com
never_direct allow CONNECT google 

加上下面一些必要的参数,就是一个最简单的可以自动重试的squid配置了:


http_access allow all
http_port 3128
cache_peer 127.0.0.1 parent 8123 0 no-query default name=polipo
forward_timeout 15 seconds
connect_timeout 3 seconds
nonhierarchical_direct off
prefer_direct on
dns_nameservers 127.0.0.1
retry_on_error on
forward_max_tries 5
其中有些参数需要说明一下,connect_timeout控制重试列表里面每一项的连接超时时间,forward_timeout控制整个重试列表的尝试时间,如果超过这个时间,直接就会返回失败不会继续尝试重试列表中剩余项。dns_nameservers用来指定一个与系统配置不同的域名服务器,这里用它指向一个没有被污染的安全的域名服务器。

补充:后来发现,POST方法也会遭遇CONNECT方法一样的待遇,当内容传输到一半连接被RESET时,不会重试。解决办法也只能和CONNECT一样。

Spring Python

I am doing Spring related work recently, but I knew nothing about Spring before. When I was looking for docs about Spring, I found this – Spring Python -  a Spring Framework written in Python.

As far as I know, the main function of Spring framework is that objects can be created and initialized with an xml configuration file. It’s great for Java because compilation is no longer necessary when the initialization parameters are modified or the implementation class is replaced by another. But for Python, it’s already a sort of scripting language, no compilation is required. Is it really necessary to customize creation of python objects in xml configuration file instead python scripts? More study is required for this.

Why Python is More Productive than Java

I wrote an EMA clone in Python recently. I was asked why Python is more productive than Java after the demo. So I collected some proof from Internet.

interpreted vs. compiled is a big productivity win for Python/Ruby

dynamic typing is a big productivity win for Python/Ruby

Java is way faster than Python or Ruby

minimal scaffolding is a big productivity win for Python/Ruby. Makes programming more pleasant not to have to build all the infrastructure.

mostly first class functions a big win for Python/Ruby.

built-in lists/arrays and hashes/dictionaries a big win over Java [] and library based collections. 

dynamic code loading in Python/Ruby is a big win. Yes you can do it in Java but again, the cruft.

C++ vs Java vs Python vs Ruby : a first impression

No need for set/get methods in Python

Python has useful constructs Java lacks (Function Objects, Closures, Array and String support, Dictionary Syntax)

Introspection is easier in Python

Why is Python more fun than Java

A friend of mine who knows nearly all the widely used languages uses Python for most of his projects. He says the main reason is that he likes the way source code looks. That may seem a frivolous reason to choose one language over another. But it is not so frivolous as it sounds: when you program, you spend more time reading code than writing it.

The Python Paradox

I was generating working code nearly as fast as I could type. When I realized this, I was quite startled.

Why Python

5-10 times productivity (really!)

image

image

Why I Love Python

How much more productive? The most widely accepted estimate is 5-10 times. On the basis of my own personal experience with the two languages, I agree with this estimate.

In my personal estimate, I spend 5 times as much time fixing such errors (omitting or duplicating control characters) in Java as I do in Python. It really cuts into your productivity — and your creative energy — when you spend that much of your time just trying to satisfy the compiler.

Python & Java: A Side-by-Side Comparison

image

Programming Language Productivity

image 

An empirical comparison of C, C++, Java, Perl, Python, Rexx, and Tcl

 

One is that Python requires a lot less typing.

Another source of productivity is Python's powerful built-in data types.

Planning is good and bad. If you know where you're going, planning is good. If you don't know what you'll encounter on the way, you should be more open-minded and improvisational. I certainly see a place for planning, but if the language forces you to plan everything, there may be trips you'll never undertake because it would require too much thinking ahead.

Programming at Python Speed

image

Python + Django vs. C# + ASP.NET: Productivity Showdown

And more references:

Comparing Python to Java

Quotes about Python

Python Compared to Java

Amazingly bad API

Recovery from Addiction

Comparing Python to Other Languages

Virtualbox 3.2 Comes with Exciting New Features

VirtualBox 3.2 has released a beta version recently. Many new features are presented:

  • Mac OS X guest support. (It means you can install unmodified Mac OS X in VirtualBox now.)
  • Hardware clock in UTC time
  • Absolute pointing device (now it’s not necessary to capture the mouse even if Guest Addition is not installed)

image

  • Memory ballooning. (dynamically increase or decrease memory)
  • CPU hot-plugging. (dynamically increase or decrease CPU)
  • Multi-Monitor

image

  • Performance improvements. (VPID and unrestricted guest execution are supported now. Use VBoxManage modifyvm --vtxvpid and –largepages to turn these features on.)
  • Execute guest application from host

C:\Program Files\Oracle VM VirtualBox>VBoxManage.exe guestcontrol execute ubuntu
/bin/ls --wait-for stdout
Oracle VM VirtualBox Command Line Management Interface Version 3.2.0_BETA2
(C) 2005-2010 Oracle Corporation
All rights reserved.

bin
boot
cdrom
dev
etc
home
initrd.img
initrd.img.old
...

More features and bug fixes can be found here. But one problem of VirtualBox still remains that many functions are only available through CLI instead of GUI.

什么是Debian


Debian项目是一个由一些有着共同目标的人所组成的组织,他们的共同目标是创建一个自由的操作系统。我们创建的这个操作系统被称作Debian GNU/Linux,或者简单的称作Debian

一个操作系统是一些让你的电脑能够运行的基本的程序和实用工具的集合。一个操作系统的核心是它的内核。内核是计算机上最基础的程序,负责所有基本的管理工作,让你的计算机能够运行其他程序。

Debian系统现在使用Linux内核。Linux是一个完全自由的软件,它由Linus Torvalds创立,并被成千上万的程序员所支持。

然而,为Debian提供其他内核的工作也在进行中,主要是Hurd。Hurd是一个运行在微内核(比如Mach)之上的服务器的集合,来实现各种操作系统特性。Hurd是一个由GNU工程创立的自由软件。

操作系统中大量的基本工具都来自GNU工程;因此有这样的名字:GNU/Linux和GNU/Hurd。那些工具也是自由软件。

当然,人们需要的是应用软件??能够帮助人们完成他们想做的事,比如编辑文档、处理商务、玩游戏、编写软件等。Debian附带了8710个软件包(预先编译好的、容易安装的、打包的软件)—所有的都是自由的。

这有点像一座塔。塔基是内核,之上是所有的基本工具,再上面是你在计算机上运行的所有软件。塔顶就是Debian — 它小心的管理和装配所有东西,让它们能够一起良好的工作。

C++相关资源

C++语言





C++编译器



有些编译器可以自由下载(商用前务必先看清他们的条件或者许可):





有些编译器必须收费(其中一些或许可以试用):





C++库





C++经典著作





  • Bjarne Stroustrup, The C++ Programming Language, Special

    Edition, 2000


  • Stanley B. Lippman, Josée LaJoie, C++ Primer, 3/E,

    1998


  • Bjarne Stroustrup, The Design and Evolution of C++, D&E,

    1994


  • Margaret A. Ellis, Bjarne Stroustrup, The Annotated C++ Reference

    Manual
    , ARM, 1990


  • Stanley B. Lippman, Essential C++, 2000


  • Andrei Alexandrescu, Modern C++ Design: Generic Programming and

    Design Patterns Applied
    , 2001


  • Herb Sutter, Exceptional C++: 47 Engineering Puzzles, Programming

    Problems, and Solutions
    , 1999


  • Nicolai M. Josuttis, The C++ Standard Library: A Tutorial and Reference,

    1999


  • Scott Meyers, Effective C++: 50 Specific Ways to Improve Your Programs

    and Design
    , 2/E, 1998


  • Douglas C. Schmidt, Stephen D. Huston, C++ Network Programming,

    Volume 2: Systematic Reuse with ACE and Frameworks
    , 2003


  • Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine, The Boost Graph

    Library: User Guide and Reference Manual
    , 2001


  • Herb Sutter, More Exceptional C: 40 New Engineering Puzzles, Programming

    Problems, and Solutions
    , 2001


  • Scott Meyers, Effective STL: 50 Specific Ways to Improve Your Use

    of the Standard Template Library
    , 2001


  • Scott Meyers, Effective C++ CD: 85 Specific Ways to Improve Your Programs

    and Designs, 1999


  • Andrew Koenig, Barbara E. Moo, Ruminations on C++: A Decade of Programming

    Insight and Experience
    , 1997


  • Stanley B. Lippman, Inside the C++ Object Model, 1996


  • Scott Meyers, More Effective C++: 35 New Ways to Improve Your Programs

    and Designs
    , 1996


  • Martin D. Carroll, Margaret A. Ellis, Designing and Coding Reusable

    C++
    , 1995


  • Tom Cargill, C++ Programming Style, 1992






其他链接