Thread: Writing my own stl container

  1. #1
    Registered User
    Join Date
    Jul 2005
    Posts
    4

    Writing my own stl container

    So for class, I'm writing this stl container similar to a map. We were given a .h file and we're supposed to write the implementation of it. The first step is to blow off iterators until we get insert, find, operator[] and a few easier methods working, then go back and replace the dummy iterator definitions with real ones.

    But I can't even get to the part of implementing anything since I can't get the setup of the .cc file correct. I was never good with templates. I keep getting an error when I try to compile. The .h file was given to us so there's something wrong with my .cc file? Or I think it has to do with

    in the .h file (editted for length):
    Code:
    class exparray_map {
      
     public:
      
      /**
       * Types: iterator, 
       *        const_iterator
       * ---------------------
       * Dummy implementations of the iterator and const_iterator
       * Once you get everything else working, you'll want to come back
       * and define this to be a real iterator--one that does the
       * right thing in response to operator*, operator++ (pre and post), 
       * operator==, operator!=, and operator->.
       */
      
      typedef pair<const Key, Value> *iterator;
      typedef const pair<const Key, Value> *const_iterator;
      
     public: 
      exparray_map();
      ~exparray_map();
    
    // BUNCH OF OTHER METHODS
      /**
       * Method: insert
       * Usage: pair<exparray_map<string, film>::iterator, bool> iter = movies.insert(make_pair(x2.title, x2));
       *        pair<exparray_map<url, vector<string> >::iterator, bool> iter = googleMap.insert(make_pair("www.apple.com", wordsVector));
       * --------------
       * Inserts the specified Key/Value pair into the receiving exparray_map *unless* the Key was previously inserted.  
       * In either case, an iterator addressing the Key/Value pair is returned as the first field of a pair
       * return value.  The second field is a boolean set to true if the insertion really took place, and false if the Key 
       * was already present, in which case the insertion request is ignored.  Note that this means that the insert
       * operation isn't exactly what you want if you're trying to *update/change* the map.  
       * 
       * @param entry the Key/Value pair being inserted (which may or may not be inserted, depending on whether or
       *               not the specified Key is already present.)
       * @return an iterator/bool pair storing a pointer to Key's entry and a bool which is false if Key was already
       *         already in the map (in which case the insertion was ignored) and true if the insertion really did
       *         take place.
       */
    
      pair<iterator, bool> insert(const pair<Key, Value>& entry);

    Then in the .cc file I put this:
    Code:
    template <typename Key, typename Value>
    pair<iterator, bool> exparray_map<Key, Value>::insert(const pair<Key, Value>& entry){
      //  implementation of insert
    }
    but the compiler keeps tripping over it saying:

    Code:
    exparray_map.cc:44: error: type/value mismatch at argument 1 in template 
       parameter list for `template<class _T1, class _T2> struct std::pair'
    exparray_map.cc:44: error:   expected a type, got `iterator'
    exparray_map.cc:44: error: ISO C++ forbids declaration of `insert' with no type
    exparray_map.cc:44: error: prototype for `int exparray_map<Key, 
       Value>::insert(const std::pair<_T1, _T2>&)' does not match any in class `
       exparray_map<Key, Value>'
    exparray_map.h:95: error: candidate is: std::pair<std::pair<const Key, Value>*, 
       bool> exparray_map<Key, Value>::insert(const std::pair<_T1, _T2>&)
    exparray_map.cc:44: error: template definition of non-template `int 
       exparray_map<Key, Value>::insert(const std::pair<_T1, _T2>&)'
    The I tried replacing iterator with what it was going to be anyway; a pointer to the key value pair:

    In the .h file:
    Code:
    pair<pair<const Key, Value>*, bool> insert(const pair<Key, Value>& entry);
    in the .cc file:
    Code:
    pair<pair<const Key, Value>*, bool> exparray_map<Key, Value>::insert(const pair<Key, Value>& entry){
      //  implementation of insert
    }
    but still there are compiler errors (which I think are related to the face that a dummy implementation of the iterators is in use and the test file, exparray_map-test.cc, expects true iterators):
    Code:
    /var/tmp//ccQkPR1c.o: In function `confirmEverythingIsThere(exparray_map<int, int> const&, int)':
    /var/tmp//ccQkPR1c.o(.text+0x3ec): undefined reference to `exparray_map<int, int>::find(int const&) const'
    /var/tmp//ccQkPR1c.o(.text+0x400): undefined reference to `exparray_map<int, int>::end() const'
    collect2: ld returned 1 exit status
    Attached are the files in their entirety along with the test code given to us.

    Use this to compile it:
    Code:
    g++ -o exparray_map-test exparray_map-test.cc

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    You can't implement templates in .cc files on most current compilers. You have to do it in headers.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User
    Join Date
    Jul 2005
    Posts
    4
    I'm don't understand what you're saying exactly. What do you mean by headers? Please clarify.

  4. #4
    Registered User
    Join Date
    Nov 2005
    Posts
    85
    I think he means .h files only

  5. #5
    Registered User
    Join Date
    Jul 2005
    Posts
    4
    I thought I was doing that. Do you mean that the implementation has to be inlined in the .h file? That doesn't sound right. I have a .h file and the .cc file. The .h file has the public and private functions and data while the .cc file holds the implementation for them.

  6. #6
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Quote Originally Posted by curos
    I thought I was doing that. Do you mean that the implementation has to be inlined in the .h file? That doesn't sound right. I have a .h file and the .cc file. The .h file has the public and private functions and data while the .cc file holds the implementation for them.
    Right or not. If the compiler doesn't allow ....
    But you have to look at it from this angle. Templates do not create code. The code is produced when you instantiate the template( when the compiler knows the parameters ). For the compiler to be able to create code all the code has to be visible when you instantiate the template. If you put some of the template-code into separate cc-files the compiler would not know where to look for that code ( you usually #include only the .h file. )

  7. #7
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    Do you mean that the implementation has to be inlined in the .h file?
    It doesn't have to be inlined--it just needs to be in the same file.

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Not even in the same file, strictly speaking. What I like to do is this:

    file.hpp
    Code:
    tempalte <...>
    class SAD
    {
      ...
    };
    
    #include file.ipp
    file.ipp
    Code:
    // implementation here
    The extension is arbitrary, though it shouldn't be cpp, C or cc, as those might be snatched up by some build tools.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  9. #9
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    Not even in the same file, strictly speaking. What I like to do is this:
    Since an include statement is replaced by the specified file, they will both be in the same file.

  10. #10
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I was referring to physical on-disk files. As in: "That stuff that makes separate windows in your IDE."
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  11. #11
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Quote Originally Posted by CornedBee
    I was referring to physical on-disk files. As in: "That stuff that makes separate windows in your IDE."
    I think what 7stud really wanted to express is that the compiler never sees more then one file ( everything is assembled into one big file by the preprocessor ). And things the compiler doesn't see it cannot process. That's the main problem with template-code split into declaration and implementation part. When compiling template-code it cannot count on the help of the linker to generate correct object code.
    Kurt

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. storing derived classes in a stl container
    By *DEAD* in forum C++ Programming
    Replies: 2
    Last Post: 10-03-2008, 07:50 PM
  2. swap function of STL container
    By George2 in forum C++ Programming
    Replies: 11
    Last Post: 03-29-2008, 02:53 AM
  3. std::map question.
    By Raigne in forum C++ Programming
    Replies: 7
    Last Post: 03-19-2008, 12:29 PM
  4. C Formatting Using STL
    By ChadJohnson in forum C++ Programming
    Replies: 4
    Last Post: 11-18-2004, 05:52 PM
  5. I/O using a STL container
    By LA Mills in forum C++ Programming
    Replies: 5
    Last Post: 04-20-2003, 12:15 PM