Link to home
Start Free TrialLog in
Avatar of BdLm
BdLmFlag for Germany

asked on

IndexOf an Element in a stl::vector

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

Avatar of evilrix
evilrix
Flag of United Kingdom of Great Britain and Northern Ireland image

You assume, of course, that value cannot be a duplicate or are you only after the first one you find?
>> Version 2 is OK
This is a reasonable way to do this. What is the problem you have with it?
>> Version 1  does not work --> why ?

Where did you implement the index_of_element function ?
ASKER CERTIFIED SOLUTION
Avatar of evilrix
evilrix
Flag of United Kingdom of Great Britain and Northern Ireland image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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

>> 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.
Avatar of yuy2002
yuy2002

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&>& ".
Avatar of BdLm

ASKER

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

>>>> 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

 
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of BdLm

ASKER

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

>>>> 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.
>>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.
>> 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

>>>> >> 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






>> 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.
>>>> 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).
>> 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.
Avatar of BdLm

ASKER

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   https://www.experts-exchange.com/questions/22981367/BOOST-GRAPH-COMPILE-DIJSKRA-derived-from-the-sample-code.html
    or https://www.experts-exchange.com/questions/22685427/Graph-LIB-Boost-in-Delphi.html
>>  is Boost a well accepted public library?
Yes, in fact a lot of it is ear-marked for inclusion in the next C++ standard.
>>>> 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