2012-04-29 20 views
13

में अद्वितीय डेटा धकेल रहा है निम्न डेटा:वेक्टर

FolioA Name1 100 
FolioA Name2 110 
FolioA Name3 100 
FolioB Name1 100 
FolioB Name3 106 
FolioC Name1 108 
FolioC Name2 102 
FolioC Name3 110 

मैं केवल

std::vector<std::string> name; 

में अद्वितीय नामों (यानी NAME1, NAME2 और NAME3, प्रत्येक एक बार) सम्मिलित करने के लिए के रूप में मैं पुनरावृति चाहते डेटा के माध्यम से।

तो, मुझे लगता है मैं एक नक्शा बुलाया परीक्षा में डेटा जहां संग्रहीत किया है निम्नलिखित कोड है:

std::map<std::string, std::map<std::string, double> >test; 
std::map<std::string, std::map<std::string, double > >::iterator it1 = test.begin(), end1 = test.end(); 
    while (it1 !=end1) { 
     std::map<std::string, double>::iterator it2 = it1->second.begin(), end2=it1->second.end(); 
     **name.push_back(it2->first);** 
     ++it2; 
    } 
    ++it1; 
} 

लेकिन वर्तमान में नाम में जिस तरह से मैं कर रहा हूँ सूचना भेजे, NAME1, 2 की 3 उदाहरण है नाम 2 का, और नाम 3 का 3, जो मेरे कोड से अपेक्षित है। मैं इसे केवल अनूठे नामों के लिए कैसे ठीक करूं?

+0

कैसे क्या आप किस उदाहरण को शामिल करना चाहते हैं? – juanchopanza

+4

क्या आपके पास नामों का 'वेक्टर' होना चाहिए? मैं इसके बजाय नामों के 'सेट' का उपयोग करने का सुझाव दूंगा। यदि आपके पास वेक्टर होना है, तो आप पहले भी एक सेट में सम्मिलित कर सकते हैं, फिर ऑब्जेक्टर्स को 'इटरेटर' लेते हुए कन्स्ट्रक्टर ओवरलोड का उपयोग करके 'वेक्टर' में ले जाएं। – Chad

+0

@juanchopanza, मैं प्रत्येक का पहला उदाहरण चुनूंगा, इसलिए यदि वेक्टर में पहले से ही (नाम 1, नाम 2, नाम 3) शामिल है, तो जब यह चौथा रिकॉर्ड हिट करता है, तो यह पहचानता है कि रिकॉर्ड पहले से मौजूद है, इसलिए यह इसे छोड़ देता है, और जाता है अगले रिकॉर्ड के लिए। – user1155299

उत्तर

23

जब से तुम किसी दिए गए नाम के लिए पहले उदाहरण रखना चाहते हैं, तो आप एक प्रदर्शन करना होगा सर्वर उद्देश्य होगा किसी बिंदु पर नाम लुकअप। एक साधारण केवल अपने वेक्टर शामिल एल्गोरिथ्म जांच कर सकते हैं करने के लिए करता है, तो प्रविष्टि पहले से std::find

std::vector<std::string> name; 

.... 
if (std::find(name.begin(), name.end(), someName) == name.end()) { 
    // someName not in name, add it 
    name.push_back(someName); 
} 

लेकिन यहाँ आप एक खोज हर बार जब आप एक तत्व सम्मिलित करना चाहते हैं प्रदर्शन कर रहे हैं का उपयोग कर मौजूद होगा, और यह (अपने आप में) है O(N) तक जटिलता, पूरे एल्गोरिदम के लिए O(N*N) दे रही है। तो आप तेजी से देखने के साथ मध्यस्थ कंटेनर का उपयोग करके ऑप्टिमाइज़ कर सकते हैं, जैसे std::set जैसा कि @ चाड द्वारा सुझाया गया है और जिसमें O(logN) लुकअप के लिए जटिलता है, O(N*logN) कुल मिलाकर, या हैश कंटेनर जैसे सी ++ 11 के std::unordered_set, निरंतर समय के करीब है, ~ ओ (एन) समग्र जटिलता दे रहा है।

std::unordered_set name_set; 
.... 

// still need to search, since you want to keep 
// the first instance of each name, and not the last. 
// But unordered_set performs the look-up at insertion, 
// only inserting if someName not already in the set 
name_set.insert(someName); 

और फिर,

std::vector<std::string> name(names_set.begin(), name_set.end()); 

@ चाड के उदाहरण का अनुसरण करते हैं, तो आप सी ++ 11 नहीं है, तो, हैश नक्शा विकल्प boost::hash_map और tr1::hash_map हैं।

+0

आह पोस्ट कर सकते हैं, ऐसा लगता है कि ऐसा हो सकता है। क्या आप नमूना कोड पोस्ट कर सकते हैं कि मैं इसका उपयोग कैसे करूं। – user1155299

+0

@ user1155299 बस यह किया। – juanchopanza

+0

यह काम करता है। धन्यवाद! – user1155299

1

मामले में आप परवाह नहीं है जो उदाहरण आप अपने डेटा संरचना में प्रवेश करना चाहते हैं, std::set

1

शायद आपको अद्वितीय नाम रखने के लिए वेक्टर के दूसरे मानचित्र आइसटेड का उपयोग करना चाहिए।

std :: मानचित्र < std :: स्ट्रिंग, डबल> नाम;

1

नमूना कोड के लिए कहा, तो यहाँ मैं इसे कैसे किया होता है:

std::set<std::string> unique_names; 

// ... 
while (it1 !=end1) 
{ 
    // ... 
    // **name.push_back(it2->first);** 
    unique_names.insert(it2->first); 
} 

std::vector<std::string> name(unique_names.begin(), unique_names.end()); 
1

सूची .sort तो .unique() है जो आप के साथ प्रदान करेगा क्षमता() और, है।

आप इसे एक पुनरावर्तक के साथ पुन: सक्रिय कर सकते हैं और इसे प्रारंभकर्ता_सूची के साथ प्रारंभ कर सकते हैं।

कि डेटा और अधिक मेरे लिए एक struct की तरह वास्तव में दिखता है:

#include <iterator> 
#include <list> 
#include <string> 
#include <fstream> 

typedef struct NODE_S { 
    string name1, name2; 
    int n; 
} NODE_S NODE; 

bool compare_NODE (NODE first, NODE second) 
{ 
    unsigned int i=0; 
    if (first.name1 < second.name1) { 
     return true; 
    } else if (first.name2 < second.name2) { 
     return true; 
    } else if (first.n < second.n) { 
     return true; 
    } else { return false;} 
} 


bool readfile(list<NODE>& ln, string filepath) { 
    std::ifstream filein; 
    NODE n; 
    filein.open(filepath.c_str(), std::iofstream::in); 
    if (!filein.good()) { 
     filein.close(); 
     std::cerr << "ERROR: unable to open file \"" << filepath << "\" or file is zero-length." << std::endl; 
     return false; 
    } 
    do { 
     filein >> n.name1 >> n.name2 >> n.name3 >> std::skipws; 
     ln.push_back(n); 
     ln.sort(compare_NODE); 
     ln.unique(); 
     //add node to list 

    } while (!filein.good()); //can use .eof here, but if bad disk blocks... 
    filein.close(); 
    return true; 
} 


int main(int argc, char * argv[], char * envp[]) { 
    string filepath="somefile.txt"; 
    if (!readfile(filepath)) { 
     return 1; 
    } 
    list<NODE>::iterator lni; 
    for (lni = ln.begin(); lni != ln.end(); lni++) { 
     std::cout<<lni->name1<<' '<<lni->name2<<' '<<lni->n<<std::endl; 
    } 
    return 0; 
} 

http://www.cplusplus.com/reference/stl/list/sort/

http://www.cplusplus.com/reference/stl/list/unique/

+0

आप लूप के बाहर 'क्रमबद्ध' और 'अद्वितीय' कॉल को नीचे ले जाना चाहते हैं। अब उन्हें एक बार 'NODE' कहा जाता है। बीटीडब्लू, 20 साल में 'टाइपिफ स्ट्रक्चर 'चीज की आवश्यकता नहीं है। – MSalters

0

मामले में आप std :: वेक्टर उपयोग करना चाहते हैं और क्रम जटिलता के बारे में परवाह नहीं है (यह ओ (एन^2) है, यह एक और बेवकूफ तरीका है:

void add_once(std::vector<std::string>& vec, const std::string& element) { 
    std::remove(vec.begin(), vec.end(), element); 
    vec.push_back(element); 
}