Solved

IndexOf an Element in a stl::vector

Posted on 2007-11-28
23
1,260 Views
Last Modified: 2008-02-01
I need a code sample  how to get the index of an element in a vector.  I made a sample with a stringList.
Version 1  does not work --> why ?,  Version 2 is OK,  Version 3  is not yet coded, should be a TEMPLATE for this task


// vec2.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
//
 
#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
 
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
 
 
{  typedef vector <string> TStringList;
   
   TStringList   SignalList;
   vector<string>::iterator viter;
   string SignalName;
 
   int   i;
   int   index;
   
   // optionally a template  as V3 
   std::size_t index_of_element( std::vector<string&>& vec, const std::string& elem );
 
 
 
 
 
   cout << "Enter some strings, followed by '0'  to stop \n";
   while ( SignalName != "0")
      {
		  getline(cin, SignalName);
          SignalList.push_back(SignalName);
      }
 
   cout << "Data Dump \n";
   for (viter=SignalList.begin(); viter!= SignalList.end(); ++viter) 
      cout << *viter << "\n ";
   cout << endl;
	
   cout << "Index of String xyz  \n ";
 
  
   // version 1  to calc the Index of a string inside the StringList
   
   
   index = index_of_element( SignalList, "xyz" );
 
   if (index < SignalList.size()) 
	   cout << "element  found  (v1):" << index;
   else
	    cout << "element not found \n";   
   
   
   // version 2  to calc the Index of a string inside the StringList
   
   index = distance(SignalList.begin(), std::find(SignalList.begin(), SignalList.end(), string("xyz")));
 
 
   if (index < SignalList.size()) 
	   cout << "element  found  (v2) :" << index;
   else
	    cout << "element not found \n";
 
   system("pause");
 
  return 0;
}

Open in new window

0
Comment
Question by:BdLm
  • 10
  • 6
  • 3
  • +2
23 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 20369664
You assume, of course, that value cannot be a duplicate or are you only after the first one you find?
0
 
LVL 40

Expert Comment

by:evilrix
ID: 20369696
>> Version 2 is OK
This is a reasonable way to do this. What is the problem you have with it?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20369746
>> Version 1  does not work --> why ?

Where did you implement the index_of_element function ?
0
PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

 
LVL 40

Accepted Solution

by:
evilrix earned 75 total points
ID: 20369843
You could hold an index in a std::map. This is just an example, but you could always encapsulate this in a class to ensure the vector and index update atomically: -
#include <vector>
#include <map>
#include <string>
 
int main()
{
	typedef std::vector<std::string> StringVector;
	StringVector sv;
	sv.push_back("qwe");
	sv.push_back("asd");
	sv.push_back("zxc");
	sv.push_back("rty");
	sv.push_back("dfg");
 
	typedef std::map<std::string, StringVector::size_type> StringVectorIndex;
	StringVectorIndex svi;
 
	for(StringVector::size_type st = 0 ; st < sv.size() ; ++st)
	{
		svi[sv[st]] = st;
	}
 
	StringVector::size_type index1 = svi["qwe"];
	StringVector::size_type index2 = svi["asd"];
	StringVector::size_type index3 = svi["zxc"];
	StringVector::size_type index4 = svi["rty"];
	StringVector::size_type index5 = svi["dfg"];
 
	return 0;
}

Open in new window

0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20372050
Maybe the following code is a little bit easier:

   
   if ((viter = find(SignalList.begin(), SignalList.end(), "xyz")) != SignalList.end())
   {
          index = viter - SignalList.begin();
          cout << "element  found  (v2) :" << index;
   }

Some remarks:

If you have 'using namespace std;' then you can omit the std:: prefix. You should do it consequently either with using clause and omitting the prefix or without using clause and with prefix. For the latter you would need std::cout as well.

There is a constructor string::string(const char*) that takes a literal. The compiler should find that constructor so that you don't need to convert the "xyz" yourself.

If the std::find  fails it returns iterator SignalList.end(). It is more straight-forward and better readable to check that than to passing the result to distance function and check for the next return value.

Regards, Alex

0
 
LVL 40

Expert Comment

by:evilrix
ID: 20372093
>> If the std::find  fails it returns iterator SignalList.end(). It is more straight-forward and better readable to check that than to passing the result to distance function and check for the next return value.

The combination of std::file with std::distance and std::find failing means distance will return an index >= the size of the vector to indicate failure. Whether this is clear or not is, of course, open to speculation.
0
 
LVL 4

Expert Comment

by:yuy2002
ID: 20372293
size_t index_of_element( vector<string>& vec, const string& elem )
{
    return distance(vec.begin(), find(vec.begin(), vec.end(), elem));
}
You should implement index_of_element function by yourself, not only declaration.
The first element of function is "vector<string>& " not "vector<string&>& ".
0
 
LVL 8

Author Comment

by:BdLm
ID: 20392648
I'm working on version nr, 3 , a template for my task

 //  the not jet working template version

template <class myList>  
size_t index_of_element2(  myList <string>& vec, const string& elem )
  {
       return distance(vec.begin(), find(vec.begin(), vec.end(), elem));
  }

what is the best code  for this task ?  Complete code attached.
//   Vector2.cpp : Defines the entry point for the console application.
//   History 
//
//   V2   :  incl.EE  answer/tips   2-12-2007
//
//
 
 
#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
 
using namespace std;
 
 
 
 // optionally a template  as V3 
 
 
 
 
size_t index_of_element( vector<string>& vec, const string& elem )
  {
       return distance(vec.begin(), find(vec.begin(), vec.end(), elem));
  }
 
 
//  the not jet working template version 
 
template <class myList>  
size_t index_of_element2(  myList <string>& vec, const string& elem )
  {
       return distance(vec.begin(), find(vec.begin(), vec.end(), elem));
  }
 
 
 
 
 
int _tmain(int argc, _TCHAR* argv[])
 
 
{  typedef vector <string> TStringList;
   
   TStringList                   SignalList;
   vector<string>::iterator  viter;
   
   string SignalName;
 
   int   i;
   int   index;
 
 
 
 
   // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
 
    cout << " Test program V3  - 02.12.2007    \n\n";
    
 
   // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
   //  read  some dummy data from the keyboard
 
   //cout << "Enter some strings, followed by '0'  to stop \n";
   //while ( SignalName != "0")
   //   {
		 // getline(cin, SignalName);
   //       SignalList.push_back(SignalName);
   //   }
 
 
  //  other dummy data
 
   
   SignalList.push_back("aaa");
   SignalList.push_back("bbb");
   SignalList.push_back("123456789");
   SignalList.push_back("xyz");
   SignalList.push_back("test");
 
 
 
   cout << "(1) Data Dump \n";
   
   i=1;
   for (viter=SignalList.begin(); viter!= SignalList.end(); ++viter) 
          {
          cout <<"(" <<  i <<")   "  <<  *viter <<   " \n ";
		  ++i;
         }
   cout << endl;
	
   
   // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   cout << "(2)  Index of String xyz  \n ";
 
  
   // version 1  to calc the Index of a string inside the StringList
   
   
    index = index_of_element( SignalList, "xyz" );
 
   if (index < SignalList.size()) 
    	   cout << "-> element  found  ( by version1):  " << index <<  "   \n"; 
   else
	      cout << "-> element not found \n"; 
   
   
 
   // version 2  to calc the Index of a string inside the StringList
   
   index = distance(SignalList.begin(), std::find(SignalList.begin(), SignalList.end(), string("xyz")));
 
   if (index < SignalList.size()) 
     	   cout << " -> element  found  (by version 2) :  " << index << "\n";
   else
	      cout << "-> element not found (version 2) \n";
 
 
   
  // version 3  to calc the Index of a string inside the StringList   
   
   
   
   // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   system("pause");
   
   return 0;
}

Open in new window

0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20393045
>>>> template <class myList>

The template type is a dummy, not a real class. For your purpose you need two template types.

template <class L, class T>
int index_of_element( L& vec, const T& elem )
{
    L::iterator pos = std::find(vec.begin(), vec.end(), elem);
    if (pos != vec.end())
        return (int)(pos - vec.begin());
    return -1;
}

Note, I changed the return type to int, so I can return -1 for failing. That's more intuitive than returning vector.size() for fail.

Regards, Alex

 
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 75 total points
ID: 20394254
Assuming you are passing the vector as your 1st parameter, you do not need to provide a 2nd template parameter since the vector itself defines value_type, which can be used for the 2nd arguments type definition.

As for returning int, well I think that's subjective; however, the default behavior for distance is return vector::size if find fails and I think the semantics of that are well understood. What I would say is that a vector's size is neither int nor size_t, rather is is vector::size_type, which is normally but not necessarily size_t. To avoid unnecessary casting (which can shadow problems) and ambiguities it is my opinion you should just stick to using the correct type and adopt the semantics employed by distance.
template <class myList>  
typename myList::size_type index_of_element2(myList const& vec, typename myList::value_type const& elem)
{
	return distance(vec.begin(), find(vec.begin(), vec.end(), elem));
}
 
index = index_of_element2( SignalList, "xyz" );

Open in new window

0
 
LVL 4

Assisted Solution

by:yuy2002
yuy2002 earned 25 total points
ID: 20394326
>>what is the best code  for this task ?
In your main function, version 1 and version 2 are rarely different. Version 1 just uses a function to encapsulate "distance" function's action.
IMHO, template isn't recommended in your code, it has no significance unless you just used it for learning.
The template is usurally used in many common libaray ,   e.g. STL.  It defines common and abstract data and actions. If you want to get familiar with template , STL source code will be recommended.
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 75 total points
ID: 20394340
>> STL source code will be recommended
Hmmm, I don't agree. Have you seen just home complex the STL code base is? Not for the faint hearted newbie! Learning the principles adopted by STL, such as concepts, abstraction and encapsulation are advisable but I certainly don't think trying to wade through the STL code base is the best way to learn about templates! You are far better off getting a good book on the subject.

Must have book for anyone serious about learning STL: -
http://www.amazon.co.uk/C%2B%2B-Standard-Library-Tutorial-Reference/dp/0201379260/ref=pd_bbs_2?ie=UTF8&s=books&qid=1196670620&sr=8-2

Must have book for anyone serious about learning templates: -
http://www.amazon.co.uk/C%2B%2B-Templates-Complete-David-Vandevoorde/dp/0201734842/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1196670620&sr=8-1

Must have book for anyone serious about learning template meta-programming: -
http://www.amazon.co.uk/C%2B%2B-Template-Metaprogramming-Concepts-Techniques/dp/0321227255/ref=pd_bbs_sr_3?ie=UTF8&s=books&qid=1196670620&sr=8-3
0
 
LVL 8

Author Comment

by:BdLm
ID: 20394442
Hello,

many thanks for for good cooments, I measured the performance of the different versions,
they all performe within a 3 % range on my PC,
screen dump : .....
(2)  Index of String xyz
 -> element  found  ( by version1):  1002
109.6 seconds data process time
 -> element  found  (by version 2) :  1002
105.3 seconds data process time
 -> element  found  (by version 3) :  1002
105.0 seconds data process time
Drücken Sie eine beliebige Taste . . .
//   Vector2.cpp : Defines the entry point for the console application.
//   History 
//
//   V2   :  incl.EE  answer/tips   3-12-2007
//
//
 
 
#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <time.h>
 
 
using namespace std;
 
 
 
 // optionally a template  as V3 
 
 
 
 
size_t index_of_element( vector<string>& vec, const string& elem )
  {
       return distance(vec.begin(), find(vec.begin(), vec.end(), elem));
  }
 
 
//  the not jet working template version 
template <class L, class T> 
int index_of_element2( L& vec, const T& elem )
{
    L::iterator pos = std::find(vec.begin(), vec.end(), elem);
    if (pos != vec.end())
        return (int)(pos - vec.begin());
    return -1;
}
 
 
 
 
 
 
int _tmain(int argc, _TCHAR* argv[])
 
 
{  typedef vector <string> TStringList;
   
   TStringList                   SignalList;
   vector<string>::iterator  viter;
   
   string SignalName;
 
 
    clock_t start1, finish1;
    double  duration1;
	clock_t start2, finish2;
    double  duration2;
	clock_t start3, finish3;
    double  duration3;
 
 
 
   int   i;
   int   index;
 
 
 
 
   // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
 
    cout << " Test program V4  - 03.12.2007  (incl. Performance evaluation)    \n\n";
    
 
   // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
   //  read  some dummy data from the keyboard
 
   //cout << "Enter some strings, followed by '0'  to stop \n";
   //while ( SignalName != "0")
   //   {
		 // getline(cin, SignalName);
   //       SignalList.push_back(SignalName);
   //   }
 
 
  //  other dummy data
 
  for (i=1; i<1000; ++i)   SignalList.push_back("dummy-before");
 
   
   SignalList.push_back("aaa");
   SignalList.push_back("bbb");
   SignalList.push_back("123456789");
   SignalList.push_back("xyz");
   SignalList.push_back("test");
 
 
     for (i=1; i<1000; ++i)   SignalList.push_back("dummy-after");
 
 
 
   cout << "(1) Data Dump \n";
   
   i=1;
   for (viter=SignalList.begin(); viter!= SignalList.end(); ++viter) 
          {
          cout <<"(" <<  i <<")   "  <<  *viter <<   " \n ";
		  ++i;
         }
   cout << endl;
	
   
   // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   cout << "(2)  Index of String xyz  \n ";
 
  
   // version 1  to calc the Index of a string inside the StringList
    start1 = clock();    //  Save the Clock -> Start Time
 
 
	for (i=0; i<100000; ++i) {
   
    index = index_of_element( SignalList, "xyz" );
	}
   if (index < SignalList.size()) 
    	   cout << "-> element  found  ( by version1):  " << index <<  "   \n"; 
   else
	      cout << "-> element not found \n"; 
	
 
    finish1 = clock();//  Save the Clock -> End Time
	
	 //     Quick and Dirty Code injection, need a rework later on .....
	 duration1 = (double)(finish1 - start1) / CLOCKS_PER_SEC;
     printf( "%2.1f seconds data process time \n", duration1 );   
 
 
 
 
 
 
 
 
 
 
 
   
   
 
   // version 2  to calc the Index of a string inside the StringList
   
 
 start2 = clock();    //  Save the Clock -> Start Time
 
 
	for (i=0; i<100000; ++i) {
 
   index = distance(SignalList.begin(), std::find(SignalList.begin(), SignalList.end(), string("xyz")));
	
	
   }
 
 
   if (index < SignalList.size()) 
     	   cout << " -> element  found  (by version 2) :  " << index << "\n";
   else
	      cout << "-> element not found (version 2) \n";
 
 
	
 
 
    finish2 = clock();//  Save the Clock -> End Time
	
	 //     Quick and Dirty Code injection, need a rework later on .....
	 duration2 = (double)(finish2 - start2) / CLOCKS_PER_SEC;
     printf( "%2.1f seconds data process time \n", duration2 );   
 
 
 
 
 
 
 
   
  // version 3  to calc the Index of a string inside the StringList   
 
 
 start3 = clock();    //  Save the Clock -> Start Time
 
	for (i=0; i<100000; ++i) {
 
index = index_of_element2( SignalList, "xyz" );
 
	}
 
 
   if (index < SignalList.size()) 
     	   cout << " -> element  found  (by version 3) :  " << index << "\n";
   else
	      cout << "-> element not found (version 3) \n";
	
 
   
    finish3 = clock();//  Save the Clock -> End Time
	
	 //     Quick and Dirty Code injection, need a rework later on .....
	 duration3 = (double)(finish3 - start3) / CLOCKS_PER_SEC;
     printf( "%2.1f seconds data process time  \n", duration3 );   
   
   // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   system("pause");
   
   return 0;
}

Open in new window

0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20394523
>>>> the default behavior for distance is return vector::size
>>>> if find fails and I think the semantics of that are well understood.
The default return for a find (position) or index_of function is -1, e. g. std::string::find returns string::npos which is -1. The semantics of distance function are irrelevant as distance was only one (of a few) possible implementations which hardly should have any impact to the interface of an index_of function. When distance returns size() of container in case of a fail (what is hard to understand for me either as a 'distance' to a non-existing item shouldn't be a valid distance value), you easily can hide that behavior in your index_of function.  

>>>> To avoid unnecessary casting (which can shadow problems)
In the code sample I provided there is no cast.  

>>>> you do not need to provide a 2nd template parameter since
>>>> the vector itself defines value_type, which can be used for the
>>>> 2nd arguments type definition.

evilrix is right. If you follow his advice, you should notice the keyword 'typename' for the second argument, which cannot omitted when doing so. Note, the prototype

template <class L, class T>
int index_of_element( L& vec, const T& elem );

may have a redundant type T but of course it is simpler to define and equivalent for the needed functionality.
0
 
LVL 4

Expert Comment

by:yuy2002
ID: 20394621
>>they all performe within a 3 % range on my PC,
>>screen dump : .....
>>(2)  Index of String xyz
 >>-> element  found  ( by version1):  1002
>>109.6 seconds data process time
 >>-> element  found  (by version 2) :  1002
>>105.3 seconds data process time
 >>-> element  found  (by version 3) :  1002
>>105.0 seconds data process time
>>Drücken Sie eine beliebige Taste . . .

If you want to see  more obvious different performance of the different versions,  input or initalize more source data will be effective.  Moreover, getting to the bottem of source code, you could refer to the assembly code and see the reason of different virsion's performances.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 20394905
>> In the code sample I provided there is no cast.  
Yes there is!

return (int)(pos - vec.begin());

If you don't like the fact it'll return vec.size() you could return ~0 instead. This is semantically the same as return -1 but will not cause signed/unsigned conversion warnings when warning level is set high.

template <class myList>  
typename myList::size_type index_of_element2(myList const& vec, typename myList::value_type const& elem)
{
	 typename myList::size_type pos = distance(vec.begin(), find(vec.begin(), vec.end(), elem));
	 return pos < vec.size() ? pos : ~0;
}

Open in new window

0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20395673
>>>> >> In the code sample I provided there is no cast.  
>>>> Yes there is!
>>>> return (int)(pos - vec.begin());

You are right. I am sorry.

The cast can be omitted and there is no warning at W2K VC6 and AIX xlC. At VC7 there is a warning 'regarding possible loss of data'. That is because the difference between two unsigned integers could be >= 2^31 what could not be stored in a signed integer.  

<OFF_TOPIC>
The compiler gives no warning if the return type was changed to unsigned int though for a < b, where a and b were both unsigned integers, the difference a - b would cause an integer overflow as the - natural - difference of two unsigned integers is a 'signed' integer. So we have the case that the compiler gives warnings for something that rarely happens and ignores a more severe potential error, e. g.

      unsigned int a = 5, b = 10;
      if (a - b < 0)      // that is never true but compiles without warning
           return 2;

</OFF_TOPIC>

If you neither want a cast nor a warning nor want to return the size() of the container as a fail condition, you could do the following:

enum { NPOS = 0xffffffff };

template <class L>
unsigned int index_of_element( L& vec, typename L::value_type const& elem )
{
    L::iterator pos = std::find(vec.begin(), vec.end(), elem);
    if (pos != vec.end())
        return (pos - vec.begin());
    return NPOS;
}

That solves both the cast and the type issue and follows the same semantic as std::string::find.

Regards, Alex






0
 
LVL 40

Expert Comment

by:evilrix
ID: 20395897
>> That solves both the cast and the type issue and follows the same semantic as std::string::find.
size_type on a x64 platform is a 64bit number, hence returning int is not ideal.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20396293
>>>> size_type on a x64 platform is a 64bit number, hence returning int is not ideal
Yes, we already discussed that. The return type of a function is not determined by the platform but by the range of values that were possible. If the above index_of_element must handle containers on a x64 platform with more than 2^32 possible elements, it should get a 64bit integer as return type (that could be 'int' as well if the int was a 64bit integer).
0
 
LVL 40

Expert Comment

by:evilrix
ID: 20396313
>> that could be 'int' as well if the int was a 64bit integer
int is 32bit on x64, hence my assertion that you should be returning size_type. There is no need to debate this. This is my view and I accept you have a different one. I point this out purely so the OP can be aware of it. If the OP choses to return an int then fine as long as the possible consequences are understood.
0
 
LVL 8

Author Comment

by:BdLm
ID: 20566447
Many Thanks to all of you !!!

a) Thanks to itsmeandnobodyelse, I failed to assign you some points, next time .-)

b) is Boost a well accepted public library?
    what about the skills on the Boost: Graph Lib inside the EE group?
    see   http://www.experts-exchange.com/Programming/Languages/CPP/Q_22981367.html
    or http://www.experts-exchange.com/Programming/Languages/Pascal/Delphi/Q_22685427.html
0
 
LVL 40

Expert Comment

by:evilrix
ID: 20566548
>>  is Boost a well accepted public library?
Yes, in fact a lot of it is ear-marked for inclusion in the next C++ standard.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20567078
>>>> Thanks to itsmeandnobodyelse, I failed to assign you some points, next time .-)
I am looking forward ...

No, it is not an issue. You have to decide which of the solutions you like better. It is a matter of taste as all solutions given were valid. I hope I'll have the better arguments next time ...

Regards, Alex
0

Featured Post

DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Problem to event 3 97
Eclipse IDE - Cannot copy/paste from console output 8 193
C++ mouse_event mouse look 7 83
Error creating a new C++ project in ,net 20 36
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
There is an easy way, in .NET, to centralize the treatment of all unexpected errors. First of all, instead of launching the application directly in a Form, you need first to write a Sub called Main, in a module. Then, set the Startup Object to th…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question