Solved

IndexOf an Element in a stl::vector

Posted on 2007-11-28
23
1,247 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
 
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
What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
no14 challenge 14 57
countClumps  challenge 10 90
thread-safe code in c++ 2 72
How to gracefully close the c++ 11 thread? 3 67
If you haven’t already, I encourage you to read the first article (http://www.experts-exchange.com/articles/18680/An-Introduction-to-R-Programming-and-R-Studio.html) in my series to gain a basic foundation of R and R Studio.  You will also find the …
The purpose of this article is to demonstrate how we can use conditional statements using Python.
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 goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…

744 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now