Effective STL

【Effective STL（5）】算法

2018-03-14  本文已影响12人  downdemo

30 确保目标区间足够大

int f(int x); // 此函数从x产生一些新值
vector<int> values;
... // 把数据放入values
vector<int> results;
transform(values.begin(), values.end(), results.end(), f);

vector<int> results;
transform(values.begin(), values.end(), back_inserter(results), f);

list<int> results; // results现在是list
// 在results前端反序插入
transform(values.begin(), values.end(), front_inserter(results), f);

list<int> results;
transform(values.rbegin(), values.rend(), front_inserter(results), f);

vector<int> values;
...
vector<int> results;
...
// 插入到results中间
transform(values.begin(), values.end(), inserter(results, results.begin() + results.size()/2), f);

vector<int> values;
vector<int> results;
...
results.reserve(results.size() + values.size()); // 保证results至少还能装得下values.size()个元素
transform(values.begin(), values.end(), inserter(results, results.begin() + results.size() / 2), f);

vector<int> values;
vector<int> results;
...
results.reserve(results.size() + values.size());
transform(values.begin(), values.end(), results.end(), f);

vector<int> values;
vector<int> results;
results.reserve(results.size() + values.size());
transform(values.begin(), values.end(), back_inserter(results), f);

vector<int> values;
vector<int> results;
...
if (results.size() < values.size()) results.resize(values.size());
transform(values.begin(), values.end(), results.begin(), f);

...
results.clear();
results.reserve(values.size());
transform(values.begin(), values.end(), pack_inserter(results), transmogrify);

31 了解你的排序选择

bool qualityCompare(const Widget& lhs, const Widget& rhs)
{
    // 返回lhs的质量是不是比rhs的质量好
}
// 把最好的20个元素按顺序放在widgets的前端
partial_sort(widgets.begin(), widgets.begin() + 20, widgets.end(), qualityCompare);

nth_element(widgets.begin(), widgets.begin() + 19, widgets.end(), qualityCompare);

vector<Widget>::iterator begin(widgets.begin());
vector<Widget>::iterator end(widgets.end()); 
vector<Widget>::iterator goalPosition;
goalPosition = begin + widgets.size() / 2;
nth_element(begin, goalPosition, end, qualityCompare);
... // goalPosition现在指向中等质量等级的Widget
// 下面的代码能找到质量等级为75%的Widget
vector<Widget>::size_type goalOffset = 0.25 * widgets.size();
nth_element(begin, begin + goalOffset, end,
qualityCompare);
... // begin + goalOffset现在指向质量等级为75%的Widget

bool hasAcceptableQuality(const Widget& w)
{
    // 返回w质量等级是否是2或更高;
}
// 把所有满足hasAcceptableQuality的widgets移动到widgets前端
// 并且返回一个指向第一个不满足的widget的迭代器
vector<Widget>::iterator goodEnd = 
    partition(widgets.begin(), widgets.end(), hasAcceptableQuality);

32 如果你真的想删除东西的话就在类似remove的算法后接上erase

vector<int> v;
v.reserve(10);
for (int i = 1; i <= 10; ++i) v.push_back(i);
cout << v.size(); // 打印10
v[3] = v[5] = v[9] = 99;
remove(v.begin(), v.end(), 99); // 删除所有等于99的元素
cout << v.size(); // 仍然是10
调用remove前 调用后返回newEnd 新逻辑终点后的元素保持原值 移动过程 
v.erase(remove(v.begin(), v.end(), 99), v.end()); // 真正删除所有等于99的元素
cout << v.size(); // 打印7

list<int> li;
...
li.remove(99); // 删除所有等于99的元素

33 提防在指针的容器上使用类似remove的算法

class Widget{
public:
    ...
    bool isCertified() const; // 这个Widget是否通过检验
    ...
};
vector<Widget*> v;
...
v.push_back(new Widget);

v.erase(remove_if(v.begin(), v.end(), not1(mem_fun(&Widget::isCertified))), 
    v.end());
调用remove_if前 调用remove_if后 erase后明显的内存泄漏 
void delAndNullifyUncertified(Widget*& pWidget)
{
    if (!pWidget->isCertified())
    {
        delete pWidget;
        pWidget = 0;
    }
}
for_each(v.begin(), v.end(), delAndNullifyUncertified);
v.erase(remove(v.begin(), v.end(), static_cast<Widget*>(0)), v.end());

typedef shared_ptr<Widget> RCSPW; // RCSP to Widget
vector<RCSPW > v;
...
v.push_back(RCSPW(new Widget));
...
v.erase(remove_if(v.begin(), v.end(), not1 (mem_fun(&Widget::isCertified))), v.end());

34 注意哪个算法需要有序区间

// 下列使用二分查找
binary_search
lower_bound
upper_bound
equal_range
// 下列提供了线性时间复杂度
set_union
set_intersection
set_difference
set_symmetric_difference
// 归并排序
merge
inplace_merge
// 检测是否一个区间的所有对象也在另一个区间
includes

35 通过mismatch或lexicographical比较实现简单的忽略大小写字符串比较

int ciCharCompare(char c1, char c2)
{
    int Ic1 = tolower(static_cast<unsigned char>(c1));
    int Ic2 = tolower(static_cast<unsigned char>(c2));
    if (Ic1 < Ic2) return -1;
    if (lc1 > Ic2) return 1;
    return 0;
}

int ciStringCompareImpl(const string& s1, const string& s2);
int ciStringCompare(const string& s1, const string& s2)
{
    if (s1.size() <= s2.size()) return ciStringCompareImpl(s1, s2);
    else return -ciStringCompareImpl(s2, s1);
}

int ciStringCompareImpl(const string& si, const strings s2)
{
    typedef pair<string::const_iterator, string::const_iterator> PSCI; // pair of string::const_iterator
    PSCI p = mismatch(s1.begin(), s1.end(), s2.begin(), not2(ptr_fun(ciCharCompare))); 
    if (p.first== s1.end())
    {
        if (p.second == s2.end()) return 0;
        else return -1;
    }
    return ciCharCompare(*p.first, *p.second);
}

bool ciCharLess(char c1, char c2) // 函数对象
{
    tolower(static_cast<unsigned char>(c1)) < 
        tolower(static_cast<unsigned char>(c2));
}
bool ciStringCompare(const string& s1, const string& s2)
{
    return lexicographical_compare(s1.begin(), s1.end(),
        s2.begin(), s2.end(), ciCharLess);
}

36 了解copy_if的正确实现

copy
copy_backward
replace_copy
reverse_copy
replace_copy_if
unique_copy
remove_copy
rotate_copy
remove_copy_if
partial_sort_copy
unintialized_copy

// 一个copy_if的正确实现
template<typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator copy_if(InputIterator begin, InputIterator end,
    OutputIterator destBegin, Predicate p)
{
    while (begin != end)
    {
        if (p(*begin))*destBegin++ = *begin;
        ++begin;
    }
    return destBegin;
}

37 用accumulate或for_each来统计区间

list<double> ld;
...
double sum = accumulate(ld.begin(), Id.end(), 0.0); // 从0.0开始计算它们的和

double sum = accumulate(ld.begin(), Id.end(), 0); // 结果不是double

cout << "The sum of the ints on the standard input is" // 打印cin中int的和
<< accumulate(istream_iterator<int>(cin), istream_iterator<int>(), 0);

string::size_type stringLengthSum(string::size_type sumSoFar, const string& s)
{
    return sumSoFar + s.size();
}
set<string> ss;
...
string::size_type lengthSum = accumulate(ss.begin(), ss.end(), 0, stringLengthSum); 

vector<float> vf;
...
// 因为是乘法，记得把1.0而不是0.0作为初始统计值
float product = accumulate(vf.begin(), vf.end(), 1.0f, multiplies<float>());

struct Point {
    Point(double initX, double initY): x(initX), y(initY) {}
    double x, y;
};
list<Point> lp;
...
// 求和函数应该是一个叫做PointAverage的仿函数类的对象
Point avg = accumulate(lp.begin(), lp.end(), Point(0, 0), PointAverage());

class PointAverage : public binary_function<Point, Point, Point> {
public:
    PointAverage(): numPoints(0), xSum(0), ySum(0) {}
    const Point operator()(const Point& avgSoFar, const Point& p) {
        ++numPoints;
        xSum += p.x;
        ySum += p.y;
        return Point(xSum/numPoints, ySum/numPoints);
    }
private:
    size_t numPoints;
    double xSum;
    double ySum;
};

struct Point {
    Point(double initX, double initY): x(initX), y(initY) {}
    double x, y;
};
class PointAverage : public unary_function<Point, void> {
public:
    PointAverage(): xSum(0), ySum(0), numPoints(0) {}
    void operator()(const Point& p)
    {
        ++numPoints;
        xSum += p.x;
        ySum += p.y;
    }
    Point result() const
    {
        return Point(xSum/numPoints, ySum/numPoints);
    }
private:
    size_t numPoints;
    double xSum;
    double ySum;
};
list<Point> Ip;
...
Point avg = for_each(lp.begin(), lp.end(), PointAverage()).result;
上一篇 下一篇

猜你喜欢

热点阅读