随笔 - 7  文章 - 6  trackbacks - 0
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(1)

随笔档案

文章分类

搜索

  •  

积分与排名

  • 积分 - 32912
  • 排名 - 607

最新评论

阅读排行榜

评论排行榜

        今天看到有人在问这个问题,写了下代码,标准库分离了算法和数据结构,按照这个框架写程序确实比较方便,个人认为熟读和透彻理解标准库源码是每个想成为资深c++程序员的必修课,就框架结构而论,stl很好的分离了算法和数据结构,就算法而论,标准库里有很多常见算法的经典实现,所以有非常高的研究价值。

#include <iostream>
#include 
<stddef.h>
#include 
<stdlib.h>
#include 
<string>
#include 
<iterator>
#include 
<algorithm>
#include 
<vector>

using namespace std;

template 
<typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator delete_intersection(InputIterator1 first1, InputIterator1 last1, 
         InputIterator2 first2, InputIterator2 last2, OutputIterator dest) 
{
    
while (first1 != last1 && first2 != last2) {
        
if (*first1 > *first2) {
            
*dest = *first2;
            
++first2;
            
++dest;
        }
 else if (*first1 < *first2) {
            
*dest = *first1;
            
++first1;
            
++dest;
        }
 else {
            
++first1;
            
++first2;
        }

    }


    
for (;first2 != last2; ++first2) *dest = *first2;

    
return dest;
}


int main() {
    
int a[] = {1,1,2,2,5,6,9,9};
    
int b[] = {1,2,3,4,4,6,7,8,9,9,9,10};

    vector
<int> vc;

    delete_intersection(a, a 
+ sizeof(a)/sizeof(a[0]), b, b + sizeof(b)/sizeof(b[0]), back_inserter(vc));

    std::copy(a, a 
+ sizeof(a)/sizeof(a[0]), ostream_iterator<int>(cout, ",")); 
        cout 
<< endl;

    std::copy(b, b 
+ sizeof(b)/sizeof(b[0]), ostream_iterator<int>(cout, ",")); 
        cout 
<< endl;

    std::copy(vc.begin(), vc.end(), ostream_iterator
<int>(cout, ",")); 
        cout 
<< endl;

    ::system(
"PAUSE");
    
return EXIT_SUCCESS;

}
posted on 2009-03-05 18:56 许海斌 阅读(1066) 评论(4)  编辑 收藏 引用

FeedBack:
# re: 关于如何删除两个集合的交集引发的思考 2009-03-05 23:00 cdy20
我没学过stl,会用一小部分
汗,我以为stl有直接解决 题目的问题。
不用大师,一般人就可以解决。
你这个是O(n),两个集合都是有序的。
假如无序,一般可以O(nlogn)解决。
我想大师的代码,应该是重用性比较高而已。  回复  更多评论
  
# re: 关于如何删除两个集合的交集引发的思考 2009-03-05 23:00 cdy20
个人意见而已,别见怪  回复  更多评论
  
# re: 关于如何删除两个集合的交集引发的思考 2009-03-06 01:17 许海斌
@cdy20

谢谢你的意见,网络本来就是畅所欲言,百家争鸣的地方,没什么:),我只是想说明下stl有非常高的学习价值,如果你写一些程序库,涉及到算法和数据结构的话,可以套用stl的框架,那就不只是学习价值了。就上面的例子,即使没排过序,照样搬用stl框架实现,效率无损且更具通用性,代码不仅仅可以应用于数组,还可以适用于所有按照stl框架实现的容器,如vector、list、deque、set、map、hashtable等等,假设你的程序最初用的是数组,后来发现对查找有比较高的要求,要换成hashtable,那么对于算法无需做任何改动即可应用,否则的话要针对数据结构重写算法,相信是一件很不爽的事情。  回复  更多评论
  
# re: 关于如何删除两个集合的交集引发的思考 2009-03-06 01:35 许海斌
@cdy20
很多人认为stl由于通用性,因此会在效率上打些折扣,其实这是一个误解,如果不相信,可以再去看看源码,上面不排序的两个容器套用stl框架,同样可以做到o(nlogn)复杂度的实现。
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理