solid AutoCAD
facet normal -9.2007829e-001 -9.0619802e-002 3.8110890e-001
outer loop
vertex 3.3409047e+000 1.2000000e+002 1.0000000e+002
vertex 5.5824765e+000 9.7240940e+001 1.0000000e+002
vertex 8.4551301e+000 9.7812346e+001 1.0707107e+002
endloop
endfacet
facet normal -9.2007829e-001 -9.0619802e-002 3.8110890e-001
outer loop
vertex 6.2698369e+000 1.2000000e+002 1.0707107e+002
vertex 3.3409047e+000 1.2000000e+002 1.0000000e+002
vertex 8.4551301e+000 9.7812346e+001 1.0707107e+002
endloop
endfacet
……
endsolid
你只需关注vertex后面的3个数值，它们是一个顶点的坐标。在该类型文件中，许多顶点具有相同的坐标值。你的程序要求任意输入一个.stl文件名，然后判断出它有多少个坐标值唯一的顶点。你可以用磁盘中附带的dat1.stl作为例子，它包含15万多不唯一的顶点坐标。
这里就不给出dat1.stl，因为格式如上。数据量很大有15万个，要求在60秒内完成否则算作失败，需要用到标准模板库。
小弟现在也在研究，希望志同道和的朋友和我探讨一下，我现在正在研究C++标准模板库的使用，以前没用过对STL很不熟悉，希望对STL比较熟悉的高手给予指教，源代码不用给我我自己可以写，只用告诉我些思路就可以了，谢谢！！！！
16 个解决方案
#1
排序
#2
你这思路也太简单了吧，只要学过算法的人都知道，不排序怎么能在60秒内完成，我想知道怎么建立数据结构，用分治法或是什么方法搜索并比较这些数据？
另外读取这个文件中的vertex后的数据怎么整，怎么知道这个数据是VEXTEX后的数据，不至于把别的数据误读进来，希望真正懂算法的高手给些思路，不懂就不要随便回帖了。
另外读取这个文件中的vertex后的数据怎么整，怎么知道这个数据是VEXTEX后的数据，不至于把别的数据误读进来，希望真正懂算法的高手给些思路，不懂就不要随便回帖了。
#3
还有STL中用那个模板比较好？set是什么？
#4
stl中map ,set 都可以。这两个模版类最后都是基于同一个数据结构：tree，据说这个tree 还是RBTree,反正效率应该是还可以的。最后排序查找都是在树中进行，整个效率应该是nlg(n).
map，set都有insert()函数，如果集合中已经有相同的元素了，会返回false
map，set都有insert()函数，如果集合中已经有相同的元素了，会返回false
#5
排序之后，相同元素一定落在相邻区域，这是最简单并有效的思路，有什么不对么？
15万数据不多啊
15万数据不多啊
#6
一怒拔剑兄，可能我说话的语气有些重，最近这个程序搞得我很心烦，请见谅
#7
你们说的排序我也想到过但我认为那对于一维数值排序还可以，但这里的坐标是三维的，那么应该定义一个数组类并重载一下operator[]或者定义一个结构体来存储坐标值，因为只有三个坐标值都相等才能算两个顶点坐标相同。那么排序按照哪个坐标进行，还有我对从文件中读取指定的内容（比如这里vertex后的三个值）的方法不太确定，怎么保证读到的是想要的坐标值，谁可以写个简单的代码演示以下从上述文件中读一个节点的三个坐标值，是通过判断是否读到vertex字符串来决定开始读取数据吗？
#8
按x排，如果x相等，再按y排，如果y也相等了，再按z排，这是基本的多value排序
就是读到字符串vertex之后，连读3个double类型的数值啊，这样就可以了
就是读到字符串vertex之后，连读3个double类型的数值啊，这样就可以了
#9
谢了，我编程试试
#10
你说的依次按x,y,z排序我认为效率不高，我还是决定定义一个类并重载运算符。
还有谁能提供一个效率更好的方法加快运算速度
还有谁能提供一个效率更好的方法加快运算速度
#11
你以为类是怎么实现啊？
类里面也是这么定义多value 排序啊！
你可以看看库里面pair的排序，先排x,后排y
加快速度，可以从排序算法上入手！
类里面也是这么定义多value 排序啊！
你可以看看库里面pair的排序，先排x,后排y
加快速度，可以从排序算法上入手！
#12
你从模板库里给我找一个能自动排序的容器类，那不是都需要重载运算符吗？
pair是哪种容器类？我怎么找不到？
你说你有什么好的排序算法？说来听听
pair是哪种容器类？我怎么找不到？
你说你有什么好的排序算法？说来听听
#13
set,map都是平衡二叉树可以自动将元素插到指定的位置，请问遇到相同元素插入时是否会返回false
#14
sort()里面可以用自己定义的函数比较两个东东的大小，用不着重载什么运算符啊
#15
请这里的朋友给我帮帮忙，提供些思路，我刚开始学习STL。有很多地方不太懂，谢谢。
#16
采用位图结构:
150000/8 = 18750Bytes;
18750/1024 = 18K
X,Y,Z都记入,最大用54K,也就是说,把所有的数据读入到内存,最大只用54K,这对于当今256M/512M,甚至更多内存的机器来说根部不算什么.
对于这个问题,你要知道你要找的唯一的点,因此,可以事先做一个估算,这样唯一的点大概有多少,再开辟合适的空间,以我估计(我不知道你这个问题的情况)大概内存不会超过10K!
这样你在读入数据后,排序自然完成,或者更直接点,你这个问题是用这种方法,更本没有排序的开销!在读入的过程中就可以消除不必要的数据.
读取vertex后的数据大概可以这样:
while(iFile.getline(Buffer,128))
{
if(Buffer[0]!='v') continue;
sscanf(Buffer,"%f,%f,%f",&x,&y,&z);
......
}
150000/8 = 18750Bytes;
18750/1024 = 18K
X,Y,Z都记入,最大用54K,也就是说,把所有的数据读入到内存,最大只用54K,这对于当今256M/512M,甚至更多内存的机器来说根部不算什么.
对于这个问题,你要知道你要找的唯一的点,因此,可以事先做一个估算,这样唯一的点大概有多少,再开辟合适的空间,以我估计(我不知道你这个问题的情况)大概内存不会超过10K!
这样你在读入数据后,排序自然完成,或者更直接点,你这个问题是用这种方法,更本没有排序的开销!在读入的过程中就可以消除不必要的数据.
读取vertex后的数据大概可以这样:
while(iFile.getline(Buffer,128))
{
if(Buffer[0]!='v') continue;
sscanf(Buffer,"%f,%f,%f",&x,&y,&z);
......
}
#1
排序
#2
你这思路也太简单了吧，只要学过算法的人都知道，不排序怎么能在60秒内完成，我想知道怎么建立数据结构，用分治法或是什么方法搜索并比较这些数据？
另外读取这个文件中的vertex后的数据怎么整，怎么知道这个数据是VEXTEX后的数据，不至于把别的数据误读进来，希望真正懂算法的高手给些思路，不懂就不要随便回帖了。
另外读取这个文件中的vertex后的数据怎么整，怎么知道这个数据是VEXTEX后的数据，不至于把别的数据误读进来，希望真正懂算法的高手给些思路，不懂就不要随便回帖了。
#3
还有STL中用那个模板比较好？set是什么？
#4
stl中map ,set 都可以。这两个模版类最后都是基于同一个数据结构：tree，据说这个tree 还是RBTree,反正效率应该是还可以的。最后排序查找都是在树中进行，整个效率应该是nlg(n).
map，set都有insert()函数，如果集合中已经有相同的元素了，会返回false
map，set都有insert()函数，如果集合中已经有相同的元素了，会返回false
#5
排序之后，相同元素一定落在相邻区域，这是最简单并有效的思路，有什么不对么？
15万数据不多啊
15万数据不多啊
#6
一怒拔剑兄，可能我说话的语气有些重，最近这个程序搞得我很心烦，请见谅
#7
你们说的排序我也想到过但我认为那对于一维数值排序还可以，但这里的坐标是三维的，那么应该定义一个数组类并重载一下operator[]或者定义一个结构体来存储坐标值，因为只有三个坐标值都相等才能算两个顶点坐标相同。那么排序按照哪个坐标进行，还有我对从文件中读取指定的内容（比如这里vertex后的三个值）的方法不太确定，怎么保证读到的是想要的坐标值，谁可以写个简单的代码演示以下从上述文件中读一个节点的三个坐标值，是通过判断是否读到vertex字符串来决定开始读取数据吗？
#8
按x排，如果x相等，再按y排，如果y也相等了，再按z排，这是基本的多value排序
就是读到字符串vertex之后，连读3个double类型的数值啊，这样就可以了
就是读到字符串vertex之后，连读3个double类型的数值啊，这样就可以了
#9
谢了，我编程试试
#10
你说的依次按x,y,z排序我认为效率不高，我还是决定定义一个类并重载运算符。
还有谁能提供一个效率更好的方法加快运算速度
还有谁能提供一个效率更好的方法加快运算速度
#11
你以为类是怎么实现啊？
类里面也是这么定义多value 排序啊！
你可以看看库里面pair的排序，先排x,后排y
加快速度，可以从排序算法上入手！
类里面也是这么定义多value 排序啊！
你可以看看库里面pair的排序，先排x,后排y
加快速度，可以从排序算法上入手！
#12
你从模板库里给我找一个能自动排序的容器类，那不是都需要重载运算符吗？
pair是哪种容器类？我怎么找不到？
你说你有什么好的排序算法？说来听听
pair是哪种容器类？我怎么找不到？
你说你有什么好的排序算法？说来听听
#13
set,map都是平衡二叉树可以自动将元素插到指定的位置，请问遇到相同元素插入时是否会返回false
#14
sort()里面可以用自己定义的函数比较两个东东的大小，用不着重载什么运算符啊
#15
请这里的朋友给我帮帮忙，提供些思路，我刚开始学习STL。有很多地方不太懂，谢谢。
#16
采用位图结构:
150000/8 = 18750Bytes;
18750/1024 = 18K
X,Y,Z都记入,最大用54K,也就是说,把所有的数据读入到内存,最大只用54K,这对于当今256M/512M,甚至更多内存的机器来说根部不算什么.
对于这个问题,你要知道你要找的唯一的点,因此,可以事先做一个估算,这样唯一的点大概有多少,再开辟合适的空间,以我估计(我不知道你这个问题的情况)大概内存不会超过10K!
这样你在读入数据后,排序自然完成,或者更直接点,你这个问题是用这种方法,更本没有排序的开销!在读入的过程中就可以消除不必要的数据.
读取vertex后的数据大概可以这样:
while(iFile.getline(Buffer,128))
{
if(Buffer[0]!='v') continue;
sscanf(Buffer,"%f,%f,%f",&x,&y,&z);
......
}
150000/8 = 18750Bytes;
18750/1024 = 18K
X,Y,Z都记入,最大用54K,也就是说,把所有的数据读入到内存,最大只用54K,这对于当今256M/512M,甚至更多内存的机器来说根部不算什么.
对于这个问题,你要知道你要找的唯一的点,因此,可以事先做一个估算,这样唯一的点大概有多少,再开辟合适的空间,以我估计(我不知道你这个问题的情况)大概内存不会超过10K!
这样你在读入数据后,排序自然完成,或者更直接点,你这个问题是用这种方法,更本没有排序的开销!在读入的过程中就可以消除不必要的数据.
读取vertex后的数据大概可以这样:
while(iFile.getline(Buffer,128))
{
if(Buffer[0]!='v') continue;
sscanf(Buffer,"%f,%f,%f",&x,&y,&z);
......
}